자료구조 - 더블 링크드 리스트(Doubly Linked List)

다음 노드를 가리키는 포인터만 가지고 있는 노드(링크드 리스트)에

이전 노드를 가리키는 포인터도 가지도록 하는 노드의 리스트를 더블 링크드 리스트라 한다.

단 방향 탐색인 링크드 리스트에 탐색기능을 개선하여, 양방향으로 탐색을 가능하게 하는 자료구조형이다.

 

 

typedef struct tagNode{ int Data; struct tagNode* PrevNode; //이전 노드를 가리키는 포인터 struct tagNode* NextNode; //다음 노드를 가리키는 포인터 }Node;

 

 

Node* DLL_CreatNode(int 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){ if((*Head) == NULL) *Head = NewNode; else{ Node* Tail = (*Head); while(Tail->NextNode != NULL){ Tail = Tail->NextNode; } Tail->NextNode = NewNode; NewNode->PrevNode = Tail; }

 

 

void DLL_GetNodeAt(Node* Head, int Location){ Node* Current = Head; while(Location--) Current = Current->NextNode; return Current; }

 

void DLL_RemoveNode(Node** Head, Node* Remove){ if((*Head) == Remove){ *Head = Remove->NextNode; if((*Head) == NULL){ (*Head)->PrevNode = NULL; } } else{ Node* Temp = Remove; Remove->PrevNode->NextNode = Temp->NextNode; if(Remove->NextNode != NULL){ Remove->NextNode->PrevNode = Temp->PrevNode; } } }

더블 링크드 리스트니깐 다뤄야할 포인터가 4개라는 점을 주의하면 된다.

마지막 elss문에서 삭제할 노드의 다음노드가 존재하는지 판단. 

그리고 여기 리스트에서 제거된 노드는 따로 메모리를 해제해(DLL_DestroyNode()) 주어야 한다.

 

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; } }

현재노드 뒤에 노드를 추가시키는 함수이다.

더블 링크드 리스트니깐 다뤄야할 포인터가 4개라는 점을 주의하면 된다.

입맛에 따라 코딩하면 될 듯하다. 예를 들어 인덱스를 주고 거기에 대입하는 것으로 짜도 되고

 

int DLL_CetNodeCount(Node* Head){ unsigned int Count = 0; Node* Current = Head; while(Current != NULL){ Current = Current->NextNode; Count++; } return Count; }