더블 링크드 리스트(Doubly Linked List)
더블 링크드 리스트(Doubly Linked List)란?
더블 링크드 리스트(Doubly Linked List)는 링크드 리스트의 탐색 기능을 개선한 자료구조입니다. 링크드 리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색을 할 수 있는 반면에, 더블 링크드는 양방향으로 탐색이 가능하다는 것입니다.
양방향 탐색이 가능한 것은 구조가 변경된 덕분입니다. 링크드 리스트의 노드가 다음 노드를 가리키는 포인터만을 가졌던 데 비해, 더블 링크드 리스트의 노드는 자신의 앞에 있는 노드를 가리키는 포인터도 가지고 있습니다. 그래서 더블 링크드 리스트의 노드는 뒤로 이동할 수 있을 뿐만 아니라 앞으로도 이동할 수 있습니다.
이것을 구조체로 표현하면 다음과 같이 선언할 수 있습니다.
typedef struct tagNode
{
int Data; /* 데이터 필드 */
struct tagNode* PrevNode /* 이전 노드를 가리키는 포인터 */
struct tagNode* NextNode /* 다음 노드를 가리키는 포인터 */
} Node;그리고 이 노드를 주렁주렁 엮으면 더블 링크드 리스트가 되는 것입니다.
더블 링크드 리스트의 주요 연산
더블 링크드 리스트의 주요 연산이라고 하더라도 링크드 리스트와 비슷합니다. '이전 노드'를 처리하기 위한 구현이 더 추가될 뿐입니다. 링크드 리스트를 이해했다면 더블 링크드 리스트 역시 쉽게 이해될 것입니다.
노드 생성/소멸
방금 전에 이야기했듯이 더블 링크드 리스트의 노드를 만들고 소멸시키는 과정은 링크드 리스트와 별 차이가 없습니다. 우선 노드를 생성하는 DLL_CreateNode() 함수를 보면 링크드 리스트의 버전과 비교했을 때에 생성한 노드의 PrevNode에 NULL을 대입하여 초기화하는 부분만이 추가됐을 뿐인 것을 알 수 있습니다.
/* 노드 생성/소멸 */
Node* DLL_CreateNode(ElementType NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}노드를 자유 저장소에서 제거하는 DLL_DestoryNode() 함수는 아예 링크드 리스트의 버전과 동일합니다. free()를 호출하는 것 뿐입니다.
/* 노드 소멸 */
void DLL_DestroyNode(Node* Node)
{
free(Node);
}노드 추가
링크드 리스트에서 SLL_AppendNode() 함수는 기존 테일의 NextNode 포인터가 새로 추가된 테일을 가리키도록 하면 끝났지만 더블 링크드 리스트에서는 새로운 테일의 PrevNode 포인터 또한 기존 테일의 주소를 가리키게 해야 합니다.
더블링크드 리스트의 DLL_AppendNode() 함수는 다음과 같습니다. SLL_AppendNode() 와 다른 부분은 모두 같고, 새로 추가된 노드의 PrevNode 포인터가 기존에 테일이었던 노드를 가리키게 하는 코드가 더 추가되었습니다.
/* 노드 추가 */
void DLL_AppendNode( Node** Head, Node* NewNode )
{
/* 헤드 노드가 NULL이라면 새로운 노드가 Head */
if ( (*Head) == NULL )
{
*Head = NewNode;
}
else
{
/* 테일을 찾아 NewNode를 연결한다. */
Node* Tail = (*Head);
while ( Tail->NextNode != NULL )
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNodw;
NewNodw->PrevNode = Tail; /* 기존의 테일을 새로운 테일의 PrevNode가 가리킨다. */
}
}DLL_AppendNode() 함수는 다음과 같이 사용할 수 있습니다.
Node* List = NULL;
DLL_AppendNode( &List, DLL_CreateNode( 117 ) );
DLL_AppendNode( &List, DLL_CreateNode( 119 ) );노드 탐색
노드 탐색을 하는 DLL_GetNodeAt() 함수도 링크드 리스트 버전을 그대로 사용하면 됩니다.
Node* DLL_GetNodeAt(Node* Head, int Location)
{
Node* Current = Head;
while ( Current != NULL && (--Location) >= 0 )
{
Current = Current->NextNode;
}
return Current;
}노드 삭제
더블 링크드 리스트의 노드를 삭제해 보도록 하겠습니다. 노드 삭제는 앞에서 봤던 연산들과는 달리 약간 복잡합니다. 삭제할 노드의 양쪽 포인터 두 개, 이전 노드의 NextNode 포인터, 이후 노드의 PrevNode 포인터 등 모두 4개의 포인터를 다루어야 하기 때문입니다.
삭제할 노드의 NextNode 포인터가 가리키고 있던 노드를 앞 노드의 NextNode 포인터가 가릴키고 있던 노드를 앞 노드의 NextNode 포인터가 가리키게 바꾸고, 또 삭제할 노드의 PrevNode 포인터가 가리키고 있던 노드를 뒷 노드의 PrevNode 포인터가 가리키도록 바꿉니다. 그리고 삭제할 노드의 NextNode와 PrevNode는 NULL로 초기화합니다.
더블 링크드 리스트의 DLL_RemoveNode() 함수는 다음과 같이 구현합니다.
/* 노드 제거 */
void DLL_RemoveNode( Node** Head, Node* Remove )
{
if ( *Head == Remove )
{
*Head = Remove->NextNode;
if ( (*Head) != NULL )
(*Head)->PrevNode = NULL;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
else
{
Node* Temp = Remove;
Remove->PrevNode->NextNode = Temp->NextNode;
if ( Remove->NextNode != NULL )
Remove->NextNode->PrevNode = Temp->PrevNode;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
}노드 삽입
노드를 삭제할 때 일어나는 포인터 교환이 복잡하게 느껴질 수 있습니다. 노드 삽입 연산 또한 그 과정이 복잡하지만 삭제 연산에 비해서는 간단합니다.
새로운 노드는 PrevNode 포인터로는 앞 노드를, NextNode 포인터로는 뒷 노드를 가리킵니다. 그리고 앞 노드의 NextNode 포인터와 뒷 노드의 PrevNode 포인터는 새 노드를 가리킵니다. 이렇게 해서 노드 삽입이 이루어지는 것입니다.
이러한 내용의 DLL_InsertAfter() 함수는 다음과 같이 구현합니다.
/* 노드 삽입 */
void DLL_InsertAfter( Node* Current, Node* NewNode )
{
NewNode->NextNode = Current->NextNode;
NewNode->PrevNode = Current;
if ( Current->NextNode != NULL )
{
Current->NextNode->PrevNode = NewNode;
Current->NextNode = NewNode;
}
}노드 개수 세기
더블 링크드 리스트의 노드 수를 세는 DLL_GetNodeCount() 는 링크드 리스트의 SLL_GetNdeCount()와 이름만 제외하고 같습니다.
/* 노드 수 세기 */
int DLL_GetNodeCount(Node* Head)
{
unsigned int Count = 0;
Node* Current = Head;
while ( Current != NULL )
{
Current = Current->NextNode;
Count++;
}
return Count;
}더블 링크드 리스트 예제 프로그램
세 개의 파일로 구성되어 있습니다. 하나는 링크드 리스트의 기본 연산을 수행하는 함수를 선언하고 구현하는 DoublyLinkedList.h와 DoublyLinkedList.c, 그리고 또 다른 하나는 이들 함수를 테스트하는 Test_DoublyLinkedList.c 입니다.
/**********************/
/* DoublyLinkedList.h */
/**********************/
#ifndef DOUBLY_LINKEDLIST_H
#define DOUBLY_LINKEDLIST_H
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagNode
{
ElementType Data;
struct tagNode* PrevNode;
struct tagNode* NextNode;
} Node;
/* 함수 원형 선언 */
Node* DLL_CreateNode( ElementType NewData );
void DLL_DestroyNode( Node* Node);
void DLL_AppendNode( Node** Head, Node* NewNode );
void DLL_InsertAfter( Node* Current, Node* NewNode );
void DLL_RemoveNode( Node** Head, Node* Remove );
Node* DLL_GetNodeAt( Node* Head, int Location );
int DLL_GetNodeCount( Node* Head );
#endif DOUBLY_LINKEDLIST_H/**********************/
/* DoublyLinkedList.c */
/**********************/
#include "DoublyLinkedList.h"
/* 노드 생성 */
Node* DLL_CreateNode( ElementType NewData )
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}
/* 노드 소멸 */
void DLL_DestroyNode( Node* Node )
{
free(Node);
}
/* 노드 추가 */
void DLL_AppendNode( Node** Head, Node* NewNode )
{
/* 헤드 노드가 NULL이라면 새로운 노드가 Head */
if ( (*Head) == NULL )
{
*Head = NewNode;
}
else
{
/* 테일을 찾아 NewNode를 연결한다. */
Node* Tail = (*Head);
while ( Tail->NextNode != NULL )
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
NewNode->PrevNode = Tail; /* 기존의 테일을 새 테일의 PrevNode가 가리킨다. */
}
}
/* 노드 삽입 */
void DLL_InsertAfter( Node* Current, Node* NewNode )
{
NewNode->NextNode = Current->NextNode;
NewNode->PrevNode = Current;
if ( Current->NextNode != NULL )
{
Current->NextNode->PrevNode = NewNode;
Current->NextNode = NewNode;
}
}
/* 노드 제거 */
void DLL_RemoveNode( Node** Head, Node* Remove )
{
if ( *Head == Remove )
{
*Head = Remove->NextNode;
if ( (*Head) != NULL )
(*Head)->PrevNode = NULL;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
else
{
Node* Temp = Remove;
if ( Remove->PrevNode != NULL )
Remove->PrevNode->NextNode = Temp->NextNode;
if ( Remove->NextNode != NULL )
Remove->NextNode->PrevNode = Temp->PrevNode;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
}
/* 노드 탐색 */
Node* DLL_GetNodeAt( Node* Head, int Location )
{
Node* Current = Head;
while ( Current != NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
/* 노드 수 세기 */
int DLL_GetNodeCount( Node* Head )
{
unsigned int Count = 0;
Node* Current = Head;
while ( Current != NULL )
{
Current = Current->NextNode;
Count++;
}
return Count;
}
void PrintNode( Node* _Node )
{
if ( _Node->PrevNode == NULL )
printf("Prev: NULL");
else
printf("Prev: %d", _Node->PrevNode->Data);
printf(" Current: %d ", _Node->Data);
if ( _Node->NextNode == NULL )
printf("Next: NULL\n");
else
printf("Next: %d\n", _Node->NextNode->Data);
}/***************************/
/* Test_DoublyLinkedList.c */
/***************************/
#include "DoublyLinkedList.h"
int main( void )
{
int i = 0;
int Count = 0;
Node* List = NULL;
Node* NewNode = NULL;
Node* Current = NULL;
/* 노드 5개 추가 */
for ( i = 0; i<5; i++ )
{
NewNode = DLL_CreateNode( i );
DLL_AppendNode( &List, NewNode );
}
/* 리스트 출력 */
Count = DLL_GetNodeCount( List );
for ( i = 0; i<Count; i++ )
{
Current = DLL_GetNodeAt( List, i );
printf( "List[%d] : %d\n", i, Current->Data );
}
/* 리스트의 세 번째 칸 뒤에 노드 삽입 */
printf( "\nInserting 3000 After [2]...\n\n" );
Current = DLL_GetNodeAt( List, 2 );
NewNode = DLL_CreateNode( 3000 );
DLL_InsertAfter( Current, NewNode );
/* 리스트 출력 */
Count = DLL_GetNodeCount( List );
for ( i = 0; i<Count; i++ )
{
Current = DLL_GetNodeAt( List, i );
printf( "List[%d] : %d\n", i, Current->Data );
}
/* 모든 노드를 메모리에서 제거 */
printf( "\nDestroying List...\n" );
Count = DLL_GetNodeCount(List);
for ( i = 0; i<Count; i++ )
{
Current = DLL_GetNodeAt( List, 0 );
if ( Current != NULL )
{
DLL_RemoveNode( &List, Current );
DLL_DestroyNode( Current );
}
}
return 0;
}'IT > 알고리즘' 카테고리의 다른 글
| 스택(Stack)의 개념 및 배열로 구현하는 스택 (0) | 2020.06.26 |
|---|---|
| 환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List) (0) | 2020.06.25 |
| 링크드 리스트의 주요 연산 - 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입 (0) | 2020.06.22 |
| 링크드 리스트의 주요 연산 - 노드의 생성과 소멸 (0) | 2020.06.21 |
| 링크드리스트(Linked List) (0) | 2020.06.20 |
