이중 연결 리스트 (Double Linked-List)

#include <stdio.h>
#include <malloc.h>


typedef struct _SNode
{
	int data;

	struct _SNode* pPrev;
	struct _SNode* pNext;
} SNode;


SNode g_head = { 0, NULL, NULL };
SNode g_tail = { 0, NULL, NULL };


SNode* CreateNode(int, SNode*, SNode*);

void PushFront(SNode* _pNewNode);
void PushBack(SNode* _pNewNode);
void Insert(int _idx, SNode* _pNewNode);

void RemoveFront();
void RemoveBack();
void Remove(int _idx);
void Clear();

void PrintAll();
void PrintAllRecursive(SNode* _pNode, int* _pCnt);
void PrintAllReverse();

int Count();


void main()
{
	// Double Linked-List(이중 연결 목록)
	g_head.pPrev = NULL;
	g_head.pNext = &g_tail;

	g_tail.pPrev = &g_head;
	g_tail.pNext = NULL;


	PrintAll();
	PushFront(CreateNode(10, NULL, NULL));
	PushFront(CreateNode(20, NULL, NULL));
	PrintAll();

	printf("\n");

	PushBack(CreateNode(100, NULL, NULL));
	PushBack(CreateNode(200, NULL, NULL));
	PrintAll();
	PrintAllReverse();
	printf("Count: %d\n", Count());

	printf("\n");
	Insert(0, CreateNode(88, NULL, NULL));
	Insert(Count() - 1, CreateNode(99, NULL, NULL));
	PrintAll();
	Insert(3, CreateNode(777, NULL, NULL));
	PrintAll();

	SNode* pNewNode = CreateNode(123, NULL, NULL);
	pNewNode->data = 456;
	Insert(-100, pNewNode);
	pNewNode->data = 789;

	//if (Insert(-100, pNewNode) == -1)
	//{
	//	free(pNewNode);
	//}

	printf("\n");

	RemoveFront();
	PrintAll();
	RemoveBack();
	PrintAll();
	Remove(3);
	PrintAll();

	printf("\n");

	Clear();
	PrintAll();
	PushBack(CreateNode(1000, NULL, NULL));
	PrintAll();
	Clear();
}


SNode* CreateNode(
	int _data, SNode* _pPrev, SNode* _pNext)
{
	SNode* pNewNode =
		(SNode*)malloc(sizeof(SNode));

	pNewNode->data = _data;
	pNewNode->pPrev = _pPrev;
	pNewNode->pNext = _pNext;

	return pNewNode;
}

void PushFront(SNode* _pNewNode)
{
	if (_pNewNode == NULL) return;

	_pNewNode->pNext = g_head.pNext;
	g_head.pNext = _pNewNode;

	_pNewNode->pPrev = &g_head;
	_pNewNode->pNext->pPrev = _pNewNode;
}

void PushBack(SNode* _pNewNode)
{
	if (_pNewNode == NULL) return;

	_pNewNode->pPrev = g_tail.pPrev;
	_pNewNode->pNext = &g_tail;

	g_tail.pPrev = _pNewNode;
	_pNewNode->pPrev->pNext = _pNewNode;
}

void Insert(int _idx, SNode* _pNewNode)
{
	if (_idx < 0 || _idx >= Count())
	{
		printf("ERROR] Out of index!\n");
		return;
	}

	int curIdx = 0;
	SNode* pCurNode = g_head.pNext;
	while (pCurNode != &g_tail)
	{
		if (curIdx == _idx) {
			_pNewNode->pPrev = pCurNode->pPrev;
			_pNewNode->pNext = pCurNode;

			pCurNode->pPrev = _pNewNode;
			_pNewNode->pPrev->pNext = _pNewNode;
			break;
		}

		pCurNode = pCurNode->pNext;
		++curIdx;
	}

	printf("Insert [%d]: %d\n", curIdx, _pNewNode->data);
}

void RemoveFront()
{
	if (g_head.pNext == &g_tail) return;

	SNode* pDelNode = g_head.pNext;
	g_head.pNext = pDelNode->pNext;
	pDelNode->pNext->pPrev = &g_head;

	if (pDelNode != NULL)
	{
		free(pDelNode);
		pDelNode = NULL;
	}

	//Remove(0);
}

void RemoveBack()
{
	Remove(Count() - 1);
}

void Remove(int _idx)
{
	if (g_head.pNext == &g_tail) return;

	SNode* pDelNode = g_head.pNext;
	for (int i = 0; i < _idx; ++i)
		pDelNode = pDelNode->pNext;

	pDelNode->pPrev->pNext = pDelNode->pNext;
	pDelNode->pNext->pPrev = pDelNode->pPrev;

	if (pDelNode != NULL)
	{
		free(pDelNode);
		pDelNode = NULL;
	}
}

void Clear()
{
	if (g_head.pNext == &g_tail) return;

	SNode* pCurNode = g_head.pNext->pNext;
	do {
		if (pCurNode->pPrev != NULL)
		{
			printf("Clear: %d\n",
				pCurNode->pPrev->data);
			free(pCurNode->pPrev);
			pCurNode->pPrev = NULL;
		}

		pCurNode = pCurNode->pNext;
	} while (pCurNode != NULL);

	g_head.pNext = &g_tail;
	g_tail.pPrev = &g_head;
}

void PrintAll()
{
	if (g_head.pNext == &g_tail) {
		printf("List is empty!\n");
		return;
	}

	int cnt = 0;
	PrintAllRecursive(g_head.pNext, &cnt);
	//while (pNode != &g_tail)
	printf("(%d)\n", cnt);
}

void PrintAllRecursive(SNode* _pNode, int* _pCnt)
{
	if (_pNode == &g_tail) return;

	// Before
	printf("[%d]-", _pNode->data);

	PrintAllRecursive(_pNode->pNext, _pCnt);

	// After
	++(*_pCnt);
}

void PrintAllReverse()
{
	int cnt = 0;
	// 1. 테일 전 노드에서 시작
	SNode* pCurNode = g_tail.pPrev;
	// 2. 현재 노드가 헤드면 종료
	while (pCurNode != &g_head)
	{
		printf("[%d]-", pCurNode->data);
		pCurNode = pCurNode->pPrev;
		++cnt;
	}
	printf("(%d)\n", cnt);
}

int Count()
{
	int cnt = 0;
	SNode* pCurNode = g_head.pNext;
	while (pCurNode != &g_tail)
	{
		pCurNode = pCurNode->pNext;
		++cnt;
	}

	return cnt;
}

<이중 연결 리스트>(Double Linked-List)

 각 노드가 두 개의 링크를 가지고 있는 연결 리스트입니다. 하나는 이전 노드를 가리키고, 다른 하나는 다음 노드를 가리킵니다. 이 구조는 양방향으로 리스트를 순회할 수 있습니다.

이중 연결 리스트 구조 예시

• 데이터(Data): 노드가 저장하는 정보
• 이전 포인터(Prev): 현재 노드의 이전 노드를 가리킵니다.
• 다음 포인터(Next): 현재 노드의 다음 노드를 가리킵니다.
• 헤드 노드(head): 리스트의 시작을 가리키는 포인터로, 리스트의 첫 번째 노드를 가리킵니다.
• 테일 노드(tail): 리스트의 끝을 가리키는 포인터로, 리스트의 마지막 노드를 가리킵니다.