자료구조 > 선형구조 > 리스트 > 선형리스트
선형리스트(Linear List),
순서리스트(Ordered List)라고도 하는 선형리스트는, 리스트(List)의 두가지 종류중 하나입니다.
(리스트의) 크기가 처음부터 정적으로 정해져서, 데이터의 개수도 제한(고정)되있습니다.
주로 (고정되어있는 크기의) 배열로 구현하는데요.
그렇기에 원소 간에 순서가 있고, 각각의 요소에 인덱스를 사용할 수 있습니다.
따라서 원소 검색에서 효율적이지만, (인덱스로 바로 참조) 원소의 삽입과 삭제에서는 비효율적입니다. (하나의 삭제, 삽입에서 최악의 경우 기존의 모든 데이터를 이동해줘야 합니다)
선형리스트의 삽입에서는 두가지 경우가 있습니다.
삽입할 위치(인덱스)에 이미 값이 있냐 없냐인데요. 삽입할 위치가 값이없는, 빈공간이면 바로 원소를 삽입하면 되지만,
삽입할 위치에 이미 다른값이 있으면, 원래있는 값을 유지시키면서, 새로운 값을 삽입하도록 원래있는 값을 한칸 뒤로 밀어줘야합니다. (기존 인덱스의 바로 다음 인덱스로 값을 옮기는 것이죠)
그런데 옮길 위치에도 이미 다른값이 존재한다면? 그렇기에 삽입할 위치로부터 마지막 원소까지 한칸씩 밀려쓴것처럼 해줘야 됩니다.
선형리스트에서 삭제는 반대인데요,
맨 끝의 원소를 삭제하는 것은 괜찮지만, 맨끝 원소가 아니라면, 삭제후에 리스트 중간에 빈공간이 생깁니다.
그렇게되면...
그 빈공간을 다시 매꿀수 있게, 삭제할 인덱스 뒤의 있는 원소들을 앞으로 한칸씩 옮겨줘야 됩니다.
흔히 선형리스트의 삽입과 삭제는 차례대로 열을 맞춰서 서있는 것을 생각하면 쉽습니다.
윗단의 설명이 너무 많아서 그렇지, 직접 코드를 이해한다면 쉽게 이해할성 싶습니다.
워낙에 기초적인 구조라 아래에 자료구조의 삽입, 삭제연산을 수행하는 코드를 구현해봤습니다.
#include<stdio.h>
int arr[10] = {1, 2, 3, 4, 5, 0, 0, 0, 0, 0}, n, arri;
void arr_insert(){
int i;
printf("삽입할 원소의 인덱스와 그 값을 입력하세요: ");
scanf("%d %d", &arri, &n);
if(arri>=sizeof(arr)/sizeof(int)){
printf("인덱스 범위가 큽니다!\n\n");
return;
}
for(i = sizeof(arr)/sizeof(int)-1; i>arri; i--)
if(arr[i]==0)
break;
if(arr[i]!=0 && arr[i-1]!=0){
printf("배열이 모두 꽉찼습니다!\n\n");
return;
}
for( ; i>=arri; i--)
arr[i]=arr[i-1];
arr[arri] = n;
}
void arr_remove(){
printf("삭제할 원소의 인덱스를 입력하세요: ");
scanf("%d", &arri);
if(arri>=sizeof(arr)/sizeof(int)){
printf("인덱스 범위가 큽니다!\n\n");
return;
}else if(arr[arri]==0){
printf("이미 없는 원소 입니다!\n\n");
return;
}
for(int i = arri+1; i<sizeof(arr)/sizeof(int); i++)
arr[i-1] = arr[i];
arr[sizeof(arr)/sizeof(int) -1] = 0;
}
void main(){
while(1){
int cho;
for(int i = 0; i<sizeof(arr)/sizeof(int); i++)
printf("%d번 인덱스 값: %d\n", i, arr[i]);
printf("\n하실 연산을 입력하세요. (1 -> 삽입, 2 -> 삭제, 3 -> 종료)\n");
scanf("%d", &cho);
switch(cho){
case 1: arr_insert(); break;
case 2: arr_remove(); break;
case 3: return; break;
default: printf("제대로된 숫자를 입력해 주십시오. /n"); break;
}
}
}그러면 다음포스팅에서는 리스트의 두가지 종류종 나머지인, 연결리스트를 알아보겠습니다.
