리스트

리스트(List)는 목록 또는 도표를 추상화한 것으로, 여러 데이터 항목을 모아서 한꺼번에 관리할 수 있도록 한 것이다. 우리 주변의 수많은 정보들이 도표로 조직화되어 있기 때문에 리스트는 프로그램에서 가장 많이 사용하는 추상 자료형 중 하나이다. 주 작업으로는 삽입(Insertion), 삭제(Deletion), 검색(Retrieval) 등이 있다.

 

리스트는 순서가 있다는 점과 중복을 허용한다는 점에서 집합과 구별되고, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩 있다는 점에서 그래프와도 구별된다.

 

리스트의 구현은 배열을 사용하는 방법과 포인터를 사용하는 방법으로 나뉜다. 전자를 순차 리스트 또는 배열 기반 리스트(Array List)라고 하고 후자를 연결 리스트(Linked List)라고 한다.

 

배열에 의한 리스트 구현

데이터들은 서로 인접되어 저장되며 새로운 데이터가 현재 데이터의 내부에 삽입될 때에는 이동이 수반된다. 예를 들어 현재 Data[0], Data[1], Data[2],  Data[3]까지 들어가 있는 상태에서 두 번째 위치에 삽입 명령이 일어나면 현재 두 번째인 Data[1]을 포함하여 그 오른쪽 데이터가 모두 한 칸씩 오른쪽으로 이동하게 된다. 이때 주의해야 할 점은 만약 Data[1]부터 이동하게 된다면 현재의 Data[2]에 덧쓰이기 때문에 Data[3]으로 이동해야 할 Data[2]가 날아가 버린다. 따라서 반드시 오른쪽 끝부터 시작해서 왼쪽으로 가면서 이동시켜야 한다. 이를 C 코드로 나타내면 다음과 같다.

 

void insert(listType *lptr, int position, int item) {
	if(lptr->count == MAX)		// 현재 꽉 찬 리스트
    	printf("List Full");
    else if ((position > (lptr->count+1)) || position < 1)
    	printf("Position out of Range");	// 이격된 삽입위치 불허
    else {
    	for(int i = lptr->count-1; i >= position-1; i--)
        	lptr->data[i+1] = lptr->data[i];	// 끝에서부터 삽입위치까지 오른쪽으로 한 칸씩 이동
        lptr->data[position-1] = item;		// 원하는 위치에 삽입
        lptr->count +=1 ;		// 리스트 길이 늘림
    }
}

 

- 장점

 

직접 접근이 가능하다. 배열 인덱스를 사용하여 검색하려는 데이터를 단번에 찾아내기 때문에 매우 빠른 속도의 검색이 가능하다. 

 

- 단점

 

배열 크기 : 데이터의 최대 개수를 컴파일 이전에 미리 선언해야 한다. 프로그램 실행 도중 최대 개수를 넘는 추가 데이터가 들어오는 경우에 대처하지 못하며 반대로 충분히 큰 최대 개수를 예상해서 잡았는데 실행할 때 데이터가 몇 개 들어오지 않는다면 이는 메모리 공간의 낭비로 이어진다.

 

이동에 따른 시간적 부담 : 첫 번째에 삽입할 경우 뒤의 모든 데이터가 한 칸씩 이동해야 하며, 마찬가지로 중간에 하나가 삭제되면 삭제 위치의 오른쪽에 있는 모든 데이터가 한 칸씩 왼쪽으로 이동해야 한다. 

 

- 시간 복잡도

 

데이터 탐색 : O(1)

임의 접근 방식을 사용하기 때문에 인덱스를 이용해 바로 탐색할 수 있다. 

 

데이터 추가 : O(n)

배열 기반 리스트는 데이터들이 순차적으로 저장되어 있기 때문에 맨 처음이나 그 이후에 데이터를 추가하려면 그 뒤에 있는 데이터들을 전부 한 칸씩 뒤로 옮겨야 한다.

다만, 맨 뒤에 데이터를 추가할 때는 다른 데이터들의 위치를 옮길 필요가 없으므로 시간 복잡도가 O(1)이다.

 

데이터 삭제 : O(n)

삭제하려는 데이터의 위치가 맨 뒤가 아니라면 O(n)의 시간 복잡도를 가지고, 삭제하려는 데이터의 위치가 맨 뒤라면 O(1)의 시간 복잡도를 가진다.

 

 

연결 리스트에 의한 리스트 구현

연결 리스트(Linked List)에는 인덱스 개념이 없다. 앞 데이터가 다음 데이터를 가리키는 포인터를 갖고 있어 이 포인터를 따라감으로써 다음 데이터를 찾아내게 된다. 그러므로 데이터는 메모리 내에 서로 인접해 있을 필요가 없다. 메모리 200번지에 첫 데이터가 있고 900번지에 다음 데이터가 있더라도 다음 것이 900번지에 있다는 주소 값 정보만 갖고 있으면 되기 때문이다. 따라서 연결 리스트의 데이터는 데이터 필드뿐만 아니라 다음 것을 가리키는 포인터 필드를 가져야 한다. 이 두가지를 합쳐 노드(Node)라 부른다. C 연결 리스트로 구현한 리스트 함수 중 삽입 함수는 다음과 같다.

 

void insert(listType *lptr, int position, int item) {
	if(position > (lptr->count+1) || position < 1)
    	printf("Position out of Range");	// 이격된 삽입위치 불허
    else {
    	nptr p = (node *)malloc(sizeof(node));	// 삽입될 노드의 공간 확보
        p->data = item;		// 데이터 값 복사
        if(position == 1) {		// 첫 위치에 삽입할 경우
        	p->next = lptr->head;	// 삽입노드가 현재 첫 노드를 가리킴
            lptr->head = p;			// 헤드가 삽입노드를 가리키게
        }
        else {		// 첫 위치가 아닐 경우
        	nptr temp = lptr->head;		// 헤드 포인터를 temp로 복사
            for (int i = 1; i < position-1; i++)
            	temp = temp->next;		// temp가 삽입직전 노드를 가리키게
            p->next = temp->next;		// 삽입노드의 next 설정
            temp->next = p;		// 직전노드가 삽입된 노드를 가리키게
        }
        lptr->count += 1;		// 리스트 길이를 늘림
    }
}

 

 

삭제 함수는 다음과 같다.

delete(listType *lptr, int item) {
	nptr prev = NULL;		// prev는 널로 초기화
    nptr temp = lptr->head;		// temp는 헤드로 초기화
    while((temp != null) && (temp->data != item)) {
    	prev = temp;		// prev가 temp 가리키게
        temp = temp->next;	// temp는 다음 노드로 전진
    }
    if(prev == NULL) {		// temp가 한번도 전진하지 않았음
    	if(temp == NULL)	// 처음부터 빈 리스트
        	printf("No Nodes to Delete");	
        else {				// 삭제 대상이 첫 노드
        	lptr->head = lptr->head->next;
            free(temp);
            lptr->count -= 1;
        }
    }
    else {					// temp가 전진했음
    	if(temp == NULL)	// 리스트 끝까지 삭제 대상이 없음
        	printf("No Such Nodes");
        else {				// 삭제 대상이 내부에 있음
        	prev->next = temp->next;	// 직전노드가 삭제될 다음 노드를 가리킴
            free(temp);		// 공간 반납
            lptr->count -= 1;		// 리스트 길이 줄임
        }
    }
}

 

 

 

지금까지 설명한 연결 리스트를 단순 연결 리스트(Singly-Linked List)라고 한다. 변형으로 이중 연결 리스트(Doubly-Linked List)가 있는데 모든 노드에 대해 직전 노드로 가는 연결을 추가한 것으로, 정렬된 연결 리스트의 삽입, 삭제에 있어 이전 노드로 되돌아가기가 쉬워진다. 리스트의 마지막 노드를 가리키는 포인터인 테일 포인터(Tail Pointer)를 하나 더 두고, 새로운 노드를 삽입하려면 현재의 테일이 가리키는 노드의 next가 새 노드를 가리키게 한 후 원래 테일을 이동시켜 새 노드를 가리키게 하면 된다. 하지만 프로그래머 입장에서 삽입, 삭제 시 항상 prev 포인터에 대한 처리까지 해주어야 한다는 것과 노드 하나에 포인터 두 개를 둠으로써 포인터 변수 자체가 차지하는 메모리 공간이 늘어난다는 단점이 있다. 이중 연결에 의해 찾아가는 시간이 줄면 공간은 늘어나고 역으로 단순 연결에 의해 찾아가는 시간이 늘면 공간은 줄어드는 시간과 공간이라는 트레이드 오프(Trade Off)가 발생하게 된다. 

 

마지막 노드의 next 필드가 다시 첫 노드를 가리키며 모든 노드가 서로 붙잡고 돌아가는 모습을 하는 리스트를 원형 연결 리스트(Circular Linked List)라고 한다. 이중 연결과 원형 연결의 장점을 모두 필요로 할 경우에는 원형 이중 연결 리스트(Circular Doubly-Linked List)를 생각할 수도 있다. 여기서 테일 포인터가 불필요한 이유는 첫 노드의 prev 포인터가 마지막 노드를 가리키기 때문이다. 

 

 

 

 

정리하자면, 일단 최대 아이템 수를 예측할 수 있다면 배열을 생각해볼 수 있다. 그러나 이 경우에도 검색이 많을 때에는 배열이 좋으나, 삽입이나 삭제 위주라면 연결 리스트가 오히려 유리하다. 물론 아이템 수가 예측 불가라면 당연히 연결 리스트를 사용할 수 밖에 없다. 응용프로그램에서 어떤 자료구조를 선택할 것인지는 이처럼 데이터 크기의 예측 가능성이나 가해지는 작업의 특성을 충분히 고려하여 결정해야 한다.