양방향 연결 리스트의 동작 원리와 삽입, 삭제 방법 C로 구현하기

 

1. 양방향 연결 리스트란

 

양방향 연결 리스트는 각 노드가 머리(Head)와 꼬리(Tail)를 모두 가지는 특징이 있다. 양방향 연결 리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있다. 다음 그림을 보면 앞 노드는 prev, 뒤 노드는 next로 지칭하고 있다. 양방향 연결 리스트를 이용하면 단방향과 달리 리스트의 앞에서부터 혹은 뒤에서부터 모두 접근할 수 있다. 

 

양방향 연결 리스트의 구조

 

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

Node *head, *tail;

 

2. 연결 리스트 노드 삽입 과정

 

데이터를 오름차순으로 저장하는 양방향 연결 리스트를 구현해 보자.

 

연결 리스트 노드 삽입 원리

 

노드를 삽입할 때는, 앞쪽 노드의 next가 삽입할 노드를 가리키도록 만들고, 반대로 삽입할 노드의 prev도 앞쪽 노드를 가리키도록 한다. 마찬가지로 뒤쪽 노드의 prev가 삽입할 노드를 가리키도록 만들고, 삽입할 노드의 next가 뒤쪽 노드를 가리키도록 만들면 된다. 이 순서를 반드시 지켜야 오류 없이 안정적으로 끊김 없이 노드 삽입이 가능하다.

 

순서 정리: 앞쪽의 노드가 삽입할 노드 가리키기

-> 삽입할 노드가 앞쪽의 노드 가리키기

-> 뒤쪽의 노드가 삽입할 노드 가리키기

-> 삽입할 노드가 뒤쪽의 노드 가리키기

 

void insertNode(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* prev = cur -> prev; // 삽입할 노드의 prev를 앞쪽 노드로 잡아줌.

    prev -> next = node;
    node -> prev = prev;
    cur -> prev = node;
    node -> next = cur;
}

 

먼저 하나의 노드가 들어갈 공간을 동적 할당해준다. 그리고 그 노드의 data에 인자로 받은 int값을 넣어준다. 그리고 while문을 돌면서 현재 노드인 cur를 head부터 차근차근 오른쪽으로 이동시키면서, 삽입하고자 하는 노드의 값보다 작을 때에 한해서 cur를 살펴본다. 지금은 로직 구현 조건이 오름차순이기 때문이다. cur은 최종적으로도 그다음 노드를 가리키게 된다. 

 

while문이 끝나면, 앞쪽이 될 prev 노드를 cur의 prev로 설정한다. prev와 cur 사이에 삽입할 노드를 위치시키는 것이다. 앞서 언급된 4단계 순서대로 진행하면 된다. 

 

3. 연결 리스트 삭제 과정

 

연결 리스트 노드 삭제 원리

 

Head의 next를 삭제할 노드의 다음 노드를 가리키게 하고, 다음 노드의 prev가 Head를 가리키게 한다. 그리고 마지막으로 삭제할 노드의 메모리를 해제해 주면 성공적으로 삭제가 이루어지게 된다.

 

순서 정리: Head의 next를 삭제할 노드의 다음 노드를 가리키게 하고

-> 삭제할 노드의 다음 노드의 prev가 Head를 가리키게 한다. 

-> 삭제할 노드를 메모리 해제해 준다. 

 

void removeFront(){
    Node* node = head -> next;
    head -> next = node -> next;

    Node* next = node -> next;
    next -> prev = head;
    
    free(node);
}

 

첫 노드를 삭제한다고 가정을 한다. node를 head의 next가 가리키는 노드, 즉 삭제할 첫 노드로 설정하고, head의 next를 그 첫 node가 아닌 그다음 노드를 가리키도록 한다. 다시 반대로 그다음 노드 next의 prev를 head를 가리키도록 하고 나서, 삭제할 첫 노드를 메모리 해제해 준다.

 

4. 연결 리스트 만들어서 출력하기

 

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

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

Node *head, *tail; 

void insertNode(int data) {
    Node* node = (Node*) malloc(sizeof(Node)); 
    node -> data = data; // data값을 초기화해줌

    Node* cur; 
    cur = head -> next; 
    while (cur -> data < data && cur != tail)
    { 
        cur = cur -> next;
    }

    Node* prev = cur -> prev; 

    prev -> next = node; 
    node -> prev = prev; 
    cur -> prev = node; 
    node -> next = cur; 
}

void removeFront(){
    Node* node = head -> next;
    head -> next = node -> next; 

    Node* next = node -> next;
    next -> prev = head; 

    free(node);
}

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

int main(void) 
{
    head = (Node*) malloc(sizeof(Node)); // head와 tail의 메모리 할당을 해 준다. 
    tail = (Node*) malloc(sizeof(Node)); // 할당을 해 줘야 내부적인 변수를 활용할 수 있다. 

    head -> next = tail;
    head -> prev = head; // 끝을 NULL값이 아닌 head, tail로 판단할 것이므로 자기 자신을 가리킨다.
    tail -> next = tail;
    tail -> prev = head;

    insertNode(2);
    insertNode(7);
    insertNode(5);
    insertNode(6);
    insertNode(3);
    removeFront();
    removeFront();
    show();
}

5 6 7

 

main 함수를 보면 된다. head와 tail을 전역으로 구조체만 만들어서 선언만 해 주었기 때문에 메모리 할당을 먼저 해 준다. 그리고 head와 tail의 각각의 next와 prev가 서로를 가리키도록 하고, 각각의 prev와 next는 자기 자신을 가리키도록 한다. 함수를 실행해 보면, 오름차순 대로 2, 3, 5, 6, 7이 차례로 연결 리스트에 포함되다가 첫 노드를 두 번 지웠기 때문에 최종적으로 5, 6, 7이 남아서 출력이 된다.

 

연결 리스트는 실제 프로그램을 작성할 때 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있다. 예를 들어 더 이상 삭제할 원소가 없는데 삭제하는 경우에는 오류 메시지를 출력하고 함수의 작동을 중지시킨다던지 하는 식으로 처리해야 한다.