03. 양방향 연결 리스트

양방향 연결 리스트의 특징

• 머리(Head)와 꼬리(Tail)을 모두 가짐
• 각 노드는 앞 노드와 뒤 노드의 정보를 모두 가짐

양방향 연결 리스트의 구조

삽입 과정

삭제 과정

코드 구현

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

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

Node* head, *tail;

// 삽입
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* 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));
    tail = (Node*)malloc(sizeof(Node));
    head->next = tail;
    head->prev = head;
    tail->next = tail;
    tail->prev = head;
    insert(2);
    insert(1);
    insert(3);
    insert(9);
    insert(7);
    removeFront();
    show();
    system("pause");
    return 0;
}

주의사항

• 예외사항 처리 필요
• 더이상 삭제할 원소가 없는 경우 등

정리

• 양방향 연결 리스트에서는 각 노드가 앞 노드와 뒤 노드의 정보를 저장
• 리스트의 앞, 뒤에서 모두 접근 가능
• 단방향 연결 리스트 보다는 메모리 사용량이 더 많음