더블 링크드 리스트 구현 (Double Linked List)

삼성 C형 전체 링크

 

참고

- 메모리 풀 Memory Pool

- 메모리 풀 vs malloc 속도 비교

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver

- 더블 링크드 리스트 Double Linked List

- 더블 링크드 리스트 Double Linked List Tail ver

 

더블 링크드 리스트를 이용하여 도중에 삽입이 가능한 2차원 배열을 구현해보자.

 

편의상 index는 1부터 시작한다고 가정하자.

---

삽입

 

insert - index 1, hello

insert - index 2, c++

insert - index 2, world!

ㄴ 위 명령어를 실행하면 아래와 같이 저장된다.

hello
world!
c++

첫 번재에 hello를 추가하고 두 번째에 c++을, 그리고 다시 두 번째에 world!를 추가하였다.

 

구현은 다음과 같다.

NODE* insertNode(int index, const char* data)
{
	NODE* curNode = &HEAD;
	int curIndex = 1;

	while (1)
	{
		if (curIndex == index)
		{
			NODE* nd = &POOL[pcnt++];
			mystrcpy(nd->data, data);

			nd->prev = curNode;
			nd->next = curNode->next;
			if (curNode->next) nd->next->prev = nd;
			curNode->next = nd;

			return curNode->next;
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

 

삽입하려는 노드의 이전 node는 현재 노드(index가 가르키는 노드)여야 하고,

삽입하려는 노드의 다음 노드는 현재 노드가 next로 가르키는 노드다.

그리고 다음 노드의 이전 노드는 현재로 연결하고 (null이 아닌 경우)

현재 노드의 다음 노드는 삽입하려는 노드로 연결한다.

nd->prev = curNode;
nd->next = curNode->next;
if (curNode->next) nd->next->prev = nd;
curNode->next = nd;

 

복잡하지만 그림으로 보면 다음과 같다.

 

Current 다음에 반드시 Next가 있는 것이 아니므로 (curNode->next)가 null이 아닌 경우만 연결한다.

 

index가 아니라 삽입할 노드를 알고 있다면 다음과 같이 구현이 가능하다.

NODE* insertNode(NODE* curNode, const char* data)
{
	NODE* nd = &POOL[pcnt++];
	mystrcpy(nd->data, data);

	nd->prev = curNode;
	nd->next = curNode->next;
	if (curNode->next) nd->next->prev = nd;
	curNode->next = nd;

	return curNode->next;
}

 

다음과 같이 출력 함수를 만들어서 테스트해보자.

showNode는 HEAD부터 순서대로 출력하고, Reverse는 주어진 노드에서 거꾸로 출력한다.

void showNode()
{
	NODE* curNode = &HEAD;
	while(curNode->next)
	{
		printf("%s\n", curNode->next->data);
		curNode = curNode->next;
	}
	putchar('\n');
}

void showNodeReverse(NODE* node)
{
	while (node != &HEAD)
	{
		printf("%s\n", node->data);
		node = node->prev;
	}
	putchar('\n');
}

 

아래와 같이 insert를 해보자.

NODE* tmp;
	
insertNode(1, "hello");
tmp = insertNode(2, "c++");
insertNode(2, "world!");

printf("insert test 1\n");
showNode();
showNodeReverse(tmp);

 

tmp는 c++ node를 가르키고 있으므로, c++을 기준으로 거꾸로 출력하였다.

 

이 상태에서 3번재 노드에 blood, 그리고 blood 앞에 berry와 straw를 추가해보자.

printf("insert test 2\n");
tmp = insertNode(3, "blood");
insertNode(tmp, "berry");
insertNode(tmp, "straw");

showNode();

 

즉, 아래와 같이 출력되어야 한다.

hello
world!
blood         <<
straw         <<
berry         << 
c++

 

실제 출력 결과와 일치한다.

---

삭제

 

index 번째 노드를 삭제하는 함수는 다음과 같다.

curNode->next가 null인 경우가 존재하므로 (노드의 끝) 예외 처리를 한다.

NODE* deleteNode(int index)
{
	NODE* curNode = &HEAD;
	int curIndex = 1;

	// curNode가 삭제할 노드
	curNode = curNode->next;
	while (1)
	{
		if (curIndex == index)
		{
			curNode->prev->next = curNode->next;
			if(curNode->next) curNode->next->prev = curNode->prev;
			
			return curNode->prev; // 삭제 된 노드의 이전 노드
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

 

현재 노드를 저장하고 있다면 아래와 같은 방식으로 삭제할 수 있다.

이때, 삭제 된 노드의 이전 노드를 return하도록 하였다.

NODE* deleteNode(NODE* curNode)
{
	if (curNode == &HEAD || curNode == NULL) return NULL; 

	curNode->prev->next = curNode->next;
	if (curNode->next) curNode->next->prev = curNode->prev;

	return curNode->prev; // 삭제 된 노드의 이전 노드
}

 

위의 상황에서 아래의 코드를 실행해보자.

printf("delete test 1\n");
deleteNode(1);
tmp = deleteNode(3);
	
showNode();

printf("delete test 2\n");
tmp = deleteNode(tmp);

showNode();
showNodeReverse(tmp);

 

아래의 상황에서 첫 번째 노드를 지웠으므로 hello가 삭제된다.

그리고 남은 노드에서 3번째 노드를 삭제하였으므로 straw가 삭제된다.

hello
world!
blood
straw
berry
c++

 

그리고 straw의 이전 노드인 blood를 삭제하였으므로 world!, berry, c++만 남게 된다.

 

위의 상황은 반드시 삽입되거나 삭제되는 경우만 가정하였다.

조건에 따라 방어 코드를 추가해야 한다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef struct st
{
	char data[100];
	struct st* next;
	struct st* prev;
}NODE;

NODE HEAD;
NODE POOL[100];
int pcnt;

void mystrcpy(char *a, const char *b)
{
	while (*a++ = *b++);
}

NODE* insertNode(int index, const char* data)
{
	NODE* curNode = &HEAD;
	int curIndex = 1;

	while (1)
	{
		if (curIndex == index)
		{
			NODE* nd = &POOL[pcnt++];
			mystrcpy(nd->data, data);

			nd->prev = curNode;
			nd->next = curNode->next;
			if (curNode->next) nd->next->prev = nd;
			curNode->next = nd;

			return curNode->next;
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

NODE* insertNode(NODE* curNode, const char* data)
{
	NODE* nd = &POOL[pcnt++];
	mystrcpy(nd->data, data);

	nd->prev = curNode;
	nd->next = curNode->next;
	if (curNode->next) nd->next->prev = nd;
	curNode->next = nd;

	return curNode->next;
}


NODE* deleteNode(int index)
{
	NODE* curNode = &HEAD;
	int curIndex = 1;

	// curNode가 삭제할 노드
	curNode = curNode->next;
	while (1)
	{
		if (curIndex == index)
		{
			curNode->prev->next = curNode->next;
			if(curNode->next) curNode->next->prev = curNode->prev;
			
			return curNode->prev; // 삭제 된 노드의 이전 노드
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

NODE* deleteNode(NODE* curNode)
{
	if (curNode == &HEAD || curNode == NULL) return NULL; 

	curNode->prev->next = curNode->next;
	if (curNode->next) curNode->next->prev = curNode->prev;

	return curNode->prev; // 삭제 된 노드의 이전 노드
}

void showNode()
{
	NODE* curNode = &HEAD;
	while(curNode->next)
	{
		printf("%s\n", curNode->next->data);
		curNode = curNode->next;
	}
	putchar('\n');
}

void showNodeReverse(NODE* node)
{
	if (node == NULL) return;

	while (node != &HEAD)
	{
		printf("%s\n", node->data);
		node = node->prev;
	}
	putchar('\n');
}

int main()
{
	NODE* tmp;
	
	insertNode(1, "hello");
	tmp = insertNode(2, "c++");
	insertNode(2, "world!");

	printf("insert test 1\n");
	showNode();
	showNodeReverse(tmp);

	printf("insert test 2\n");
	tmp = insertNode(3, "blood");
	insertNode(tmp, "berry");
	insertNode(tmp, "straw");

	showNode();

	printf("delete test 1\n");
	deleteNode(1);
	tmp = deleteNode(3);
	
	showNode();

	printf("delete test 2\n");
	tmp = deleteNode(tmp);

	showNode();
	showNodeReverse(tmp);

	return 0;
}