[C/C++] 이중 연결 리스트

뜬금없이 이중 연결 리스트.

연결 리스트는 여러 개의 노드로 구성된 리스트가 있고, 각각의 노드가 다음 노드로의 링크를 가지고 연결되어 있는 연속적인 데이터 구조이다. 보다 흔히 접하는 연속적인 데이터 구조로는 배열이 있는데, 배열의 경우에는 메모리 상에서 연속된 위치에 데이터가 위치하지만, 연결 리스트는 이러한 구조는 아니고 그저 하나의 노드가 다음 노드를 가리키는 포인터를 가지고 있을 뿐이다. 따라서 리스트의 전체 크기는 중요하지 않고, 중간에 노드를 삽입하거나 빼는 것이 용이하다.

연결리스트를 쉽게 만들기 위해서는 head라는 실제 데이터를 가지지 않는 임의의 노드를 하나 만들어 둘 수 있다. 연결 리스트의 초기화 작업에는 이 head를 준비해주면 된다. 그리고 데이터를 붙여 나갈 때는 단순히 head가 뒤에 붙는 새로운 노드를 가리키게 하면 된다. 그리고 매번 노드를 추가할 때는 맨 마지막 노드 (다음 노드로의 링크가 NULL인)를 찾아서 새로운 노드를 가리키게 할 수 있다.

이러한 연결 리스트의 단점은 특정한 위치에 있는 노드를 찾기 위해서는 맨 처음 노드에서부터 순차적으로 일일이 탐색해야 한다는 것이다. 일례로, 100개의 노드로 이뤄진 연결리스트의 99번째 노드를 삭제하기 위해서는 98번째 노드를 처음부터 탐색해, 98번째의 노드의 다음 노드 링크를 100번째 노드로 바꿔주면 된다. 덕분에 노드가 뒤쪽에 있으면 있을수록 탐색에 걸리는 시간이 늘지만(반대로 배열의 경우에는 첫번째 요소를 찾거나 백만번째 요소를 찾을 때 걸리는 시간은 항상 같다.) 중간에 새로운 노드를 삽입할 때 걸리는 시간은 위치에 상관없이 같다. (반대로 배열은 삽입 위치가 앞쪽이면 그만큼 더 많은 시간이 걸린다. 삽입 위치부터 끝까지 메모리상에서 복사해서 옮겨주는 작업을 하기 때문이다.)

만약, 이 노드의 크기가 엄청나게 커지면 탐색에 걸리는 시간이 선형적으로 증가하기 때문에 예전에나 쓰임새가 좀 있었지 요즘에는 그닥 많이 쓰는 것 같지는 않다. (예전에 이 연결리스트가 잘 쓰이던 이유는 동적으로 배열의 크기를 늘리는 것이 메모리가 부족한 상황에서는 여의치 않아서이다. 배열의 메모리를 재할당하는 작업은 그만큼 연속적으로 비어있는 공간이 많아야 쉬운데, 아주 예전 시스템에서는 그게 ‘쉬운’ 상황이 아니었다는 이야기. 그런데 반대로 요즘의 데스크톱환경, 심지어 모바일 환경에서는 몇 십만개 노드에 대해 리스트를 순차적으로 탐색한다고 한들, 그 역시 성능상에 큰 손해가 되는지도 의문이긴하다. 하지만 덩치가 큰 연결 리스트는 그만큼 메모리를 파편화하여 사용하므로 역시 추천하지는 않는다.)

연결리스트의 노드는 다음번 노드로의 링크값만을 가지고 있으므로 자신의 앞 노드를 찾기 위해서는 다시 리스트 전체를 순차적을 탐색해야 한다는 단점이 있다. 따라서 이전/다음 노드에 대한 링크를 모두 가지도록 구조를 변경하면 보다 쉽게 다룰 수 있다. (일례로 중간에 있는 특정 노드를 콕 찝어서 삭제한다거나 하는 것이 가능하다.)

아무튼 다음은 이중 연결 리스트에 대한 예시. 리스트에 개수를 세거나, 몇 번째 노드를 구하거나 하는 동작에 대해서도 함수를 만들어 두었다.

#include <stdio.h> // for printf()
#include <stdlib.h> //	for malloc()

typedef struct __node
{
	int value;
	struct __node *prev;
	struct __node *next;
} node;

node *head;

void initList()
{
	head = (node*)malloc(sizeof(node));
	head->next = NULL;
}

int countOfNodes()
{
	int count = 0;
	node *now;
	for(now=head;now->next;now=now->next,count++){;}
	return count;

}

node* nodeAtIndex(int idx)
{
	int count = countOfNodes();
	if(idx<0 || idx>count -1)
	{return NULL;}

	node *target = head;
	int i=0;

	for(i=0;i<idx+1;i++){
		target=target->next;
	}

	return target;
}

void insertBefore(node* target, node* newNode)

{
	node *new;
	new = (node*)malloc(sizeof(node));
	*new = *newNode;

	node *left;
	left = target->prev;

	left->next = new;
	new->prev= left;
	target->prev = new;
	new->next = target;

}

void insertAfter(node* target, node *newNode)
{
	node *new;
	new = (node*)malloc(sizeof(node));
	*new = *newNode;
	node *right;
	right = target->next;

	if(right){
		target->next = new;
		new->prev = target;
		right->prev = new;
		new->next = right;
	}

}

int removeNode(node *toDel)
{
	node *left, *right;
	left = toDel->prev;
	right = toDel->next;
	if(left!=NULL)
	{
		left->next = right;
		if(right!=NULL)
		{
			right->prev = left;
		}

		free(toDel);
		toDel=NULL;
		return 1;
	}

	return 0;
}

int removeNodeAt(int idx)
{
	return removeNode(nodeAtIndex(idx));
}
void addNode(node* newNode)
{
	node *new;
	new = (node*)malloc(sizeof(node));
	*new = *newNode;

	node *insp;
	int idx=0;
	insp = head;
	while(insp->next != NULL)
	{
		insp = insp->next;
		idx++;
	}

	insp->next = new;
	new->prev = insp;
	new->next = NULL;

/*	printf("idx = %d\n", idx);*/
}
void releaseList(){
	while(head->next != NULL)
	{
		removeNode(head->next);
	}

	free(head);
	head=NULL;
}

int indexOfValue(int value)
{
	int idx=0;
	node *now;
	for(now=head->next;now;now=now->next){
		if( value == now->value)
		{
			return idx;
		}
		idx++;
	}
	return -1;
}
void dumpList()
{
	/* 
	   */
	node *temp;
	for(temp=head->next;temp;temp=temp->next)
	{
		printf("%03d --> ",temp->value);
	}
	int count= countOfNodes();
	printf("\n\n\ncount : %03d", count);
}

int main(void)
{
	int i=1;
	initList();

	node *now;
	node temp;

	for(i=1;i<101;i++)
	{
		temp.value = i;
		addNode(&temp);
	}

	for(i=99;i>0;i-=9)
	{
		temp.value = 999;
		insertAfter(nodeAtIndex(i), &temp);
		insertBefore(nodeAtIndex(i), &temp);
	}

	for(i=99;i>0;i-=13)
	{
		removeNode(nodeAtIndex(i));
	}

	dumpList();
	printf("\n\n count of nodes : %d", countOfNodes());
	printf("\n value of node at 33 : %d", nodeAtIndex(33)->value);
	printf("\n index of node whose value is 99 : %d", indexOfValue(99));

	return 0;
}