[ 자료구조 ] 4. 이중 연결 리스트(Double Linked List)

  이번 시간에는 이중 연결 리스트(Double Linked List)에 대해서 알아보도록 하겠습니다. 이중 연결 리스트는 말 그대로 모든 노드가 이전 노드와 다음 노드에 대한 정보를 모두 저장하고 있는 리스트를 의미합니다. 표현해보면 다음과 같이 표현할 수 있습니다.

※ 선언하기 ※

------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer prev;

NodePointer next;

} Node;

NodePointer head, tail;

------------------------------------------------------------

※ 삽입 함수 ※

  삽입이 이루어질 때는 기본적으로 자신이 들어갈 위치를 찾습니다. 저는 data를 기준으로 오름차순 정렬이 이루어지도록 삽입 함수를 작성했습니다. 이 때 i라는 별도의 변수가 사용됩니다. 결과적으로 i는 삽입될 직전의 위치를 알려주는 역할을 수행합니다. 이후에 총 4번 링크를 수행해 새로운 변수를 삽입하게 됩니다. 그 형태는 다음과 같습니다.

------------------------------------------------------------

void insert(int data) {

NodePointer i, element;

i = head->next;

while(i->data <= data && i != tail)

i = i->next;

element = (NodePointer) malloc (sizeof(Node));

element->data = data;

i->prev->next = element;

element->prev = i->prev;

i->prev = element;

element->next = i;

}

------------------------------------------------------------

※ 출력하기 ※

  출력할 때는 head의 next부터 하나씩 tail에 도달하기 전까지 노드를 방문해 출력하면 됩니다.

------------------------------------------------------------

void show() {

NodePointer i;

i = head->next;

while(i != tail) {

printf("%d ", i->data);

i = i->next;

}

}

------------------------------------------------------------

※ 실제로 사용하기 ※

  초기 상태를 다음과 같이 설정해주어야 한다는 것만 잊지 않으시면 됩니다.

------------------------------------------------------------

int main(void) {

head = (NodePointer) malloc (sizeof(Node));

tail = (NodePointer) malloc (sizeof(Node));

head->next = tail;

head->prev = head;

tail->next = tail;

tail->prev = head;

insert(7);

insert(1);

insert(8);

show();

return 0;

}

------------------------------------------------------------

  실행 결과는 다음과 같습니다.