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

삼성 C형 전체 링크

 

참고

- 메모리 풀 Memory Pool

- 메모리 풀 vs malloc 속도 비교

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver 

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

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

 

더블 링크드 리스트에 TAIL이 추가되면 구현이 편하고 성능도 나아진다.

 

HEAD의 next에 TAIL을 연결하고 TAIL의 prev에 HEAD를 연결하자. (초기화)

HEAD.next = &TAIL;
TAIL.prev = &HEAD;

 

TAIL이 존재하기 때문에 curNode->next가 NULL이 되지 않는다.

따라서 if문이 삭제된다.

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

 

다른 코드도 마찬가지다. (최종 코드 참고)

 

showNode도 node를 받은 후 TAIL까지만 출력하도록 수정한다.

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

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

 

사용법은 다음과 같다.

HEAD외에 다른 노드를 넣어도 된다.

그러면 해당 노드부터 순서대로 출력한다.

showNode(&HEAD);

 

전체 코드는 다음과 같다.

#include <stdio.h>

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

NODE HEAD, TAIL;
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;
			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;
	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;
			curNode->next->prev = curNode->prev;
			
			return curNode->prev; // 삭제 된 노드의 이전 노드
		}

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

	return NULL;
}

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

	curNode->prev->next = curNode->next;
	curNode->next->prev = curNode->prev;

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

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

	while(node->next != &TAIL)
	{
		printf("%s\n", node->next->data);
		node = node->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()
{
	HEAD.next = &TAIL;
	TAIL.prev = &HEAD;

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

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

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

	showNode(&HEAD);

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

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

	showNode(&HEAD);
	showNodeReverse(tmp);

	return 0;
}