양방향 연결 리스트

양방향 연결 리스트

- 양방향 연결 리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다는 특징이 있음

- 양방향 연결 리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있음

 

prev next(Head) ↔ prev next(일반 노드)  ↔ prev next(일반 노드) ↔ prev next(Tail)

 

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

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

Node *head, *tail;

 

연결 리스트 삽입 과정

- 순서를 철저히 지켜야 오류가 발생하지 않음

prev next(Head) ↔ prev next(일반 노드)  ↔ prev next(일반 노드) ↔ prev next(Tail)

prev next(일반 노드 사이에 삽입할 노드)

 

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

void insert(int data) {
    Node* node = (Node*) malloc(sizeof(Node)); // 하나의 node가 들어갈수 있는 공간을 할당
    node->data = data; // 데이터 값 초기화
    Node* cur; // node가 들어갈 위치 정해주기
    cur = head->next; // 첫번째 원소
    while (cur->data < data && cur != tail) {
        cur = cur->next;
    }
    Node* prev = cur->prev; // 삽입할 node에 바로 앞쪽 node를 prev로 잡아줌
    prev->next = node;
    node->prev = prev;
    cur->prev = node;
    node->next = cur;
}

 

연결 리스트 삭제 과정

prev next(Head) < prev next(삭제할 노드) > prev next(일반 노드) ↔ prev next(Tail)

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;
    }
}

 

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

#define _CRT_SECURE_NO_WARNINGS
#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가 들어갈수 있는 공간을 할당
    node->data = data; // 데이터 값 초기화
    Node* cur; // node가 들어갈 위치 정해주기
    cur = head->next; // 첫번째 원소
    while (cur->data < data && cur != tail) {
        cur = cur->next;
    }
    Node* prev = cur->prev; // 삽입할 node에 바로 앞쪽 node를 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;
}

 

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

- 위 소스코드에 덧붙여서 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있음

- 더 이상 삭제할 원소가 없는데 삭제하는 경우 등을 체크해야 함

 

 

- 양방향 연결 리스트에서는 각 노드가 앞 노드와 뒤 노드의 정보를 저장하고 있음

- 양방향 연결 리스트를 이용하면 리스트의 앞에서부터 혹은 뒤에서부터 모두 접근할 수 있음