[C] 이중 연결리스트 Double Linked List

1. 이중 연결 리스트란?

이중 연결 리스트(Doubly Linked List)는 각 노드가 앞 노드와 뒤 노드를 모두 가리키는 포인터를 가지고 있는 자료구조예요.
단일 연결 리스트(Singly Linked List)와 다르게 양방향으로 이동이 가능해서 활용도가 더 높아요.

이제 직접 이중 연결 리스트를 C 언어로 구현해볼게요.

⸻

2. 이중 연결 리스트의 노드 구조

이중 연결 리스트의 각 노드는 이전 노드(prev)와 다음 노드(next)를 가리키는 두 개의 포인터를 가지고 있어요.
이를 struct로 정의하면 다음과 같아요.

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

// 이중 연결 리스트 노드 구조
typedef struct Node {
    int data;          // 데이터 저장
    struct Node* prev; // 이전 노드를 가리키는 포인터
    struct Node* next; // 다음 노드를 가리키는 포인터
} Node;

⸻

3. 노드 생성 및 추가

새로운 노드를 생성하는 함수부터 만들어볼게요.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 메모리 할당
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

연결 리스트의 끝에 노드 추가하기

void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) { // 리스트가 비어 있다면 첫 번째 노드로 설정
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) { // 마지막 노드까지 이동
        temp = temp->next;
    }

    temp->next = newNode; // 새 노드를 마지막에 연결
    newNode->prev = temp; // 새 노드의 prev를 이전 노드로 설정
}

⸻

4. 연결 리스트 출력

이중 연결 리스트는 앞에서부터 출력하는 방법과 뒤에서부터 출력하는 방법이 있어요.

// 앞에서부터 출력
void printListForward(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 뒤에서부터 출력
void printListBackward(Node* tail) {
    Node* temp = tail;
    while (temp != NULL) {
        printf("%d <- ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

테스트 코드

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);

    printf("앞에서부터 출력: ");
    printListForward(head);  // 출력: 10 -> 20 -> 30 -> NULL

    // 마지막 노드 찾기
    Node* tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    printf("뒤에서부터 출력: ");
    printListBackward(tail);  // 출력: 30 <- 20 <- 10 <- NULL

    return 0;
}

⸻

5. 특정 위치에 노드 삽입

리스트의 가운데나 특정 위치에 노드를 삽입하는 방법도 알아볼게요.

void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("이전 노드가 NULL이에요.\n");
        return;
    }

    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
    newNode->prev = prevNode;

    if (newNode->next != NULL) {
        newNode->next->prev = newNode;
    }
}

테스트 코드:

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 30);

    printf("기존 리스트: ");
    printListForward(head);  // 출력: 10 -> 30 -> NULL

    insertAfter(head, 20); // 10과 30 사이에 20 삽입

    printf("삽입 후 리스트: ");
    printListForward(head);  // 출력: 10 -> 20 -> 30 -> NULL

    return 0;
}

⸻

6. 노드 삭제

특정 값을 가진 노드를 삭제하는 방법도 알아볼게요.

void deleteNode(Node** head, int key) {
    Node* temp = *head;

    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    if (temp == NULL) return; // 찾는 값이 없으면 종료

    if (*head == temp) { // 삭제할 노드가 첫 번째 노드라면
        *head = temp->next;
    }

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    free(temp);
}

테스트 코드:

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);
    printListForward(head);  // 출력: 10 -> 20 -> 30 -> NULL

    deleteNode(&head, 20);
    printListForward(head);  // 출력: 10 -> 30 -> NULL

    return 0;
}

⸻

7. 이중 연결 리스트의 활용과 한계

✅ 장점:
• 양방향 이동이 가능해서 탐색이 편리해요.
• 삽입/삭제가 단일 연결 리스트보다 효율적이에요.

❌ 단점:
• prev 포인터 때문에 메모리를 더 사용해요.
• 포인터를 관리해야 해서 코드가 더 복잡해질 수 있어요.

⸻

정리
1. 이중 연결 리스트는 앞뒤로 이동할 수 있는 자료구조예요.
2. prev 포인터를 이용해서 삽입/삭제가 더 효율적이에요.
3. C 언어에서 struct와 malloc을 사용해서 구현해요.
4. 단일 연결 리스트보다 더 많은 메모리를 사용하지만 활용성이 높아요.

⸻

이제 이중 연결 리스트를 완벽하게 정리했어요!
다음으로 원형 연결 리스트(Circular Linked List) 를 다뤄볼까요?