3. 양방향 연결 리스트 - 선언하기 / 삽입과정 / 삽입 함수/ 삭제 과정 / 삭제 함수 / 전체 출력 함수 / 사용하기 / 구현 시 주의할 점

양방향 연결 리스트

양반향 연결 리스트의 동작 원리와 구현 방법에 대해서 학습하고, 포인터에 유의하며 구현해 본다.

 

양방향 연결리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다. 양방향 연결리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있다. 

이러한 구조의 양방향 연결 노드를, 데이터를 '오름차순'으로 저장하는 형태로 구현해 보면 다음과 같다.

 

양방향 연결 리스트 선언하기

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

Node *head, *tail;

Node라고 이름지은 구조체를 만든다. 각 노드는 정수형 데이터 1개와 앞노드와 뒷노드를 가리키는 포인터를 각 2개씩 갖는다. 그후 head와 tail 노드를 만든다.

 

연결리스트 삽입 과정

 

먼저 앞쪽 노드의 next가 삽입할 노드를 가리키게하고, 삽입 노드의 prev가 앞 노드를 가리키게 한다. 그 후 뒷노드의 prev가 삽입할 노드를, 그 후 삽입할 노드의 next가 뒷 노드를 가리키게 한다. 이 순서를 철저히 지켜야 오류 없이 안정적으로 데이터를 삽입 할 수 있다.

 

양방향 연결 리스트 삽입 함수

(오름차순으로 정렬하며 삽입하는 함수 insert() 정의하기)

void insert(int data){
    Node *node = (Node*)(malloc(sizeof(Node)));
    node->data = data;
    Node *cur;
    cur = head->next;
    while(cur->data < data && cur != tail){
        cur = cur->next;
    }
    Node* front = cur->prev;
    front->next = node;
    node->prev = front;
    cur->prev = node;
    node->next = cur;
}

먼저 새로 삽입할 노드를 만들고, data값을 초기화 한후, 새로운 노드가 들어갈 위치를 정하기 위해 cur node를 만든다. 현재 노드가 자리 기준이 될 노드(cur)보다 작은 데이터를 가지고 있고, 현재 노드가 마지막 노드가 아니라면 자리 기준점(cur)노드가 다음 노드로 이동한다. 자리 기준점이 되는 cur노드의 prev가 가리키는 노드 이름을 front라고 이름짓고, 위에서 본 양방향 연결리스트의 삽입 순서에 맞게 포인터가 가리키는 노드를 지정한다.

 

연결리스트 삭제 과정

(가장 앞쪽 원소를 지우는 함수)

먼저 head의 포인터 next가 삭제할 노드의 다음노드를 가리키게한다. 그 삭제할 노드의 다음노드의 포인터 prev가 head 노드를 가리키게 한 후, 삭제할 노드의 메모리 할당을 해제하면 된다.

 

양방향 연결 리스트 삭제 함수

(가장 앞쪽 원소를 지우는 함수)

void removeFront(){
    Node *front = head->next;
    head->next = front->next;
    Node *newFront = front->next;
    newFront->prev = head;
    free(front);
}

현재, 양방향 연결 리스트를 선언하고나서 Node *head, *tail; 로써 head 노드와 tail 노드를 전역변수로 선언했기 때문에, 함수를 만들 때 head와 tail을 굳이 매개변수로 넣어줄 필요가 없다.

 

양방향 연결 리스트 전체 출력 함수

void showAll(){
    Node *cur = head->next;
    while(cur != tail){
        printf("%d ", cur->data);
        cur = cur->next;
    }
}

양방향 연결 리스트 사용하기

int main(void){
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));
    head-> next = tail;
    head-> prev = head;
    tail-> next = tail;
    tail-> prev = head;
    insert(7);
    insert(1);
    insert(9);
    insert(2);
    insert(0);
    insert(14);
    removeFront();
    showAll();
    system("pause");
    return 0;
}

1 2 7 9 14

가장 먼저 head와 tail의 메모리를 할당한다.(이미 앞에서 전역변수로서 선언은 했음) 그 후 head와 tail을 연결한다. 양방향 연결 리스트의 끝은 NULL값이 아닌 head와 tail로 표시할 것임으로, head의 포인터 prev는 head 노드를, tail의 포인터 next는 tail 노드를 가리키게 한다.

 

양방향 연결 리스트 구현에 있어서 주의할 점

위 소스코드에 덧붙여서, 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있다.[더 이상 삭제할 원소가 없는데 삭제하는 경우 등을 체크해야 한다]

 

요약

1. 양방향 연결 리스트에서는 각 노드가 앞 노드와 뒤 노드의 정보를 저장하고 있다. 포인터가 각 2개씩 이용되므로, 기존의 단방향 연결 리스트보다는 메모리 공간을 조금 더 차지한다는 단점이 있다.
2. 양방향 연결 리스트를 이용하면 리스트의 앞에서부터 혹은 뒤에서부터 모두 접근할 수 있다.