(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입...

(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입...

더블 링크드리스트에 대해 알아보자.

>> 이전 글에서 싱글 리스트 구현법에 대해 알아보았다. 아래 글 참고!!

[REAL Code] - (C/C++) 단방향 연결리스트 [Single Linked List] (삽입, 삭제)

더블 링크드리스트는 양방향성을 갖는 리스트로

필자와 C언어 기반으로 구현해가며

초기화, 삽입, 삭제, 탐색 순서대로 함께 알아보자.

1) 초기화

싱글 리스트에 비해 포인터가 하나더 추가되지만 원리를 이해하면 간단하다.

Node *prev는 Tail으로부터의 방향성을

Node *next는 Head로 부터의 방향이라 생각하면 된다.

struct Node { int data; Node* prev; Node* next; } node[MAXNODE];

그리고 지난 싱글리스트 구현에서 사용한 myalloc()함수를 추가해준다.

노드를 추가할때 사용하는 함수인데 일반적으로 getNode 라는 이름으로 많이 사용하기도 한다.

Node* myalloc() { return &node;[arr_idx++]; }

더블 리스트에서 초기화 상태는 head의 포인타가 tail을 향하도록

tail의 포인터가 head를 향하도록 초기화 해준다.

초기화 상태가 리스트에 노드가 비어있음을 의미하며

if(head->next == tail) 를 만족하면 노드가 비어있는 상태이다.

void init() { arr_idx = 0; head = myalloc(); tail = myalloc(); head->next = tail; tail->prev = head; }

더블리스트 초기화

2) 삽입

더블 리스트의 삽입은

head쪽으로 삽입하는 방법과 tail쪽으로 삽입하는 2가지 방법이 있는데,

순서대로 모두 알아보도록 하자.

- head쪽으로 삽입

순서 0. 노드 생성

: 임의의 노드를 생성하여 값을 할당해준다.

Node* pp = myalloc();

pp->data = data;

순서 1.

: 노드의 next 포인터를 head next로 가져온다.

노드삽입 순서 1

pp->next = head->next;

순서 2.

: head의 next는 노드 (pp)를 가리키도록 한다.

head->next = pp;

노드삽입 순서2

순서 3.

: 노드(pp)의 prev 는 tail를 head를 향하는 포인터로 카피한다.

pp->prev = pp->next->prev;

노드삽입 순서3

순서 4.

마지막으로 tail를 노드(pp) 향도록하면 노드 삽입이 마무리 된다.

노드삽입 순서4

void addtoHead(int data) { Node* pp = myalloc(); // 순서0 pp->data = data; pp->next = head->next; // 순서1 head->next = pp; // 순서2 pp->prev = pp->next->prev; // 순서3 pp->next->prev = pp; // 순서4 }

- tail쪽으로 삽입

tail쪽으로의 삽입도 head쪽으로 삽입과 크게 다르지 않다.

next와 prev의 방향만 반대로 해주면 모든 순서가 같음을 알 수 있다.

노드삽입 순서1 노드삽입 순서2 노드삽입 순서3 노드삽입 순서4

tail방향 삽입 소스코드

void addtoTail(int data) { Node* pp = myalloc(); // 순서0 pp->data = data; pp->prev = tail->prev; // 순서1 tail->prev = pp; // 순서2 pp->next = pp->prev->next; // 순서3 pp->prev->next = pp; // 순서4 }

3) 삭제

삭제는 오히려 싱글 리스트보다 단순해서

싱글 리스트보다 더블 리스트를 선호하는 분들이 있는 편이다.

리스트가 아래와 같이 연결되어 있을때

pp 노드를 삭제하고자 한다면,

초기 리스트

순서 1.

pp->next->prev = pp->prev 를 통해

tail이 head를 가리도록 해주고

노드삭제 순서1

순서 2.

pp->prev->next = pp->next 를 통해

head가 tail을 가리키도록 하면 삭제가 마무리 된다.

노드삭제 순서2

pp가 남아 있는듯 보일 수 있지만, 삭제와 동시에 리스트에서 접근할 수 있는 방법이 없기 때문에

알고리즘을 구현하고 공부할때 전혀 문제가 없다.

삭제시 순서1과 순서2의 순서는 상관없다.

void delNode(int data) { for (Node* pp = head->next; pp != tail; pp = pp->next) { if (pp->data == data) { pp->next->prev = pp->prev; // 순서 1 pp->prev->next = pp->next; // 순서 2 break; } } }

4) 탐색

이중 리스트의 탐색에서 싱글리스트와 다른점은

head에서부터 탐색할때는 tail이 아닐때까지,

tail에서부터 탐색할대는 head가 아닐때까지 만 유의해주면 된다.

아래 코드는 head에서부터 탐색할때 코드이고

for (Node* pp = head->next; pp != tail; pp = pp->next) 부분만

for (Node* pp = tail->prev; pp != head; pp = pp->prev) 로 바꾸면 tail에서부터의 탐색이 된다.

void search(int data) { for (Node* pp = head->next; pp != tail; pp = pp->next) { if (pp->data == data) { printf("find : %d

", data); break; } } }

다음은 전체 소스코드 공유 ~!

#include #define MAXNODE 100 struct Node { int data; Node* prev; Node* next; } node[MAXNODE]; int arr_idx; Node* head, * tail; Node* myalloc() { return &node;[arr_idx++]; } void init() { arr_idx = 0; head = myalloc(); tail = myalloc(); head->next = tail; tail->prev = head; } void addtoHead(int data) { Node* pp = myalloc(); pp->data = data; pp->next = head->next; head->next = pp; pp->prev = pp->next->prev; pp->next->prev = pp; } void addtoTail(int data) { Node* pp = myalloc(); pp->data = data; pp->prev = tail->prev; tail->prev = pp; pp->next = pp->prev->next; pp->prev->next = pp; } void search(int data) { for (Node* pp = head->next; pp != tail; pp = pp->next) { if (pp->data == data) { printf("find : %d

", data); break; } } } void delNode(int data) { for (Node* pp = head->next; pp != tail; pp = pp->next) { if (pp->data == data) { pp->next->prev = pp->prev; pp->prev->next = pp->next; break; } } } void print_all() { for (Node* pp = head->next; pp != tail; pp = pp->next) { printf("%d ", pp->data); } printf("

"); } int main(void) { init(); addtoHead(10); addtoHead(20); addtoHead(30); addtoHead(40); print_all(); addtoTail(100); addtoTail(200); print_all(); delNode(20); delNode(100); print_all(); return 0; }

그리고 실행결과

소스코드는 제가 즉흥적으로 작성한 코드입니다.

공부할때 도움이 됐으면 좋겠네요~!

감사합니다.

(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입, 삭제, 탐색)

레알북 : https://real-book.tistory.com

from http://real-book.tistory.com/411 by ccl(A) rewrite - 2021-08-22 03:26:20