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

---

이중 연결 리스트는 각 노드가 데이터와 두 개의 포인터(이전 노드와 다음 노드)를 가지는 자료 구조입니다. 이를 통해 양방향 탐색이 가능하며, 이는 단일 연결 리스트와의 주요 차이점입니다.

구현

---

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

void insertAfter(Node* prevNode, int data) {
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    if (prevNode->next) prevNode->next->prev = newNode;
    prevNode->next = newNode;
}

void deleteNode(Node** head, Node* del) {
    if (*head == del) *head = del->next;
    if (del->next) del->next->prev = del->prev;
    if (del->prev) del->prev->next = del->next;
    free(del);
}

성능 평가

•	탐색: O(n)
•	삽입/삭제: O(1) (노드 위치가 주어진 경우)

이중 연결 리스트는 삽입/삭제 시 노드의 포인터만 수정하면 되므로 효율적입니다.

장점

•	양방향 탐색이 가능해 특정 위치 접근이 유리합니다.
•	노드의 삽입/삭제가 빠르게 수행됩니다.

단점

•	추가 포인터로 인해 메모리 사용량이 증가합니다.
•	포인터 관리가 복잡해질 수 있습니다.

정리

이중 연결 리스트는 양방향 탐색이 필요하거나 삽입/삭제 작업이 빈번한 경우 유용한 자료 구조입니다. 하지만 포인터 관리의 복잡성과 메모리 오버헤드가 단점이 될 수 있습니다.