이중 연결 리스트 (Doubly Linked List)

연결 리스트(Linked List)에 대한 설명은 이미 포스팅 되어 있으므로 자세한 설명은 생략하겠다.

이중 연결 리스트는 아래 그림을 보면 이해하기 쉬울 것이다.

<그림 1> 연결 리스트

<그림 2> 이중 연결 리스트

이중 연결 리스트(Doubly Linked List)는 연결 리스트의 탐색 기능을 개선한 자료구조이다.

연결 리스트는 노드를 찾으려면 HEAD에서 TAIL 방향으로만 탐색을 할 수 있는데 반해

이중 연결 리스트는 양방향으로 탐색이 가능하다.

구조체로 표현하면 아래와 같다.

typedef struct tagNode {

int Data;

Struct tagNode* PrevNode;

Struct tagNode* NextNode;

} Node;

간단히 설명하면 PrevNode는 자신 Node 앞 Node를 가리키고 NextNode는 자신 Node의 뒤 Node를 가리키는 것이다.

이중 연결 리스트의 주요 연산은 연결 리스트와 동일하다.

• 노드 생성

Node* createNode(int Data) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->Data = Data;

newNode->PrevNode = NULL;

newNode->NextNode = NULL;

return newNode;

}

• 노드 소멸

 - 노드 소멸은 연결 리스트와 동일하다.

• 노드 추가

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

}

}

이중 연결 리스트도 연결 리스트와 마찬가지로 노트 탐색, 삽입, 삭제는 생략하겠다.