[c/c++] 이중 연결 리스트 ( Doubly Linked List )

< 이전 내용 >

• 단순 연결 리스트 ( Singly Linked List )
• 원형 연결 리스트 ( Circular Linked List )

 

안녕하세요 ! 우디입니다.🌞

오늘은 이중 연결 리스트 ( Doubly Linked List )에 대해 알아봅시다 !

---

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

특정 노드에서 양방향으로 자유롭게 움직일 수 있는 연결리스트다.

➤ 단순 연결 리스트 ( Singly Linked List ) 와 원형 연결 리스트 ( Circular Linked List )는 한 방향으로만 노드에서 노드를 움직일 수 있었지만 , 이중 연결 리스트는 양방향으로 갈 수 있다. 👈👉

 

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

p == p -> rlink -> llink == p -> llink -> rlink // 항상 성립한다.

x
typedef int element;// 나중에 형변환 할 때 유용하다.
typedef struct ListNode{
    element data;//데이터 필드
    struct ListNode *llink;//  왼쪽 링크 필드
    struct ListNode *rlink;//오른쪽 링크 필드
}ListNode;

 

헤드 노드 ( head node )

이중 연결 리스트 ( Doubly Linked List )는 헤드 노드 라는 특별한 노드를 추가하는 경우가 많다.

헤드 노드 ( head node )는 데이터를 가지고 있지 않고 , 헤드 포인터 ( head pointer ) 와는 구별하여야 한다.

 

삽입 ( 순서가 매우 매우 매우 중요하다 )

(1). 맨 앞쪽에 삽입하는 경우

x
void d_insert(ListNode *p, ListNode *new_node)

• p : 삽입될 위치의 선행 노드
• new_node : 삽입될 노드

 

❓❓❓ 1번 부터 4번 까지의 위치가 꼬이면 노드는 어떻게 연결될까 생각해보자 !!!

🙉 : 저는 신나게 막 코딩하다가 위치가 꼬일 수도 있다는 걸 늦게 알아서 고생 좀 했슈 ㅎㅎ

 

< Total >

x
void d_insert(ListNode *p, ListNode *new_node)
{
    new_node->llink = p;
    new_node->rlink = p->rlink;
    p->rlink->llink = new_node;
    p->rlink = new_node;
}

 

삭제

x
void d_delete(ListNode *head_node, ListNode *removed);

• head_node : 헤드 노드의 주소가 담김
• removed : 삭제될 노드를 가르키는 포인터 ( ❗❗ 노드를 동적할당 받았으면 반드시 삭제할 노드는 연결리스트 변경 후 메모리 해제시켜주기❗❗ )

 

 

< Total >

x
void d_delete(ListNode *head_node, ListNode *removed)
{
    if (head_node == removed) return;//head_node를 삭제하면 노드에 접근 X
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

 

초기화

x
void d_init(ListNode *head_node)
{
    head_node->llink = head_node;
    head_node->rlink = head_node;
}

 

출력

x
void d_display(ListNode *head_node)
{
    ListNode *p=head_node;
    for (p = head_node->rlink; p != head_node; p = p->rlink)
    {
        printf("%d -> ", p->data);
    }
}

 

---

노드 동적 생성 , 삽입, 삭제 , 초기화 , 출력

x
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
​
typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *llink;
    struct ListNode *rlink;
}ListNode;
​
//노드 동적 생성
ListNode *d_create(element data, ListNode *rlink,ListNode *llink)
{
    ListNode *new_node;
    new_node = (ListNode *)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->rlink = new_node;
    new_node->llink = new_node;
    return new_node;
}
​
// 삽입
void d_insert(ListNode *p, ListNode *new_node)
{
    new_node->llink = p;
    new_node->rlink = p->rlink;
    p->rlink->llink = new_node;
    p->rlink = new_node;
}
​
//삭제
void d_delete(ListNode *head_node, ListNode *removed)
{
    if (head_node == removed) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}
​
//초기화
void d_init(ListNode *head_node)
{
    head_node->llink = head_node;
    head_node->rlink = head_node;
}
​
//출력
void d_display(ListNode *head_node)
{
    ListNode *p=head_node;
    for (p = head_node->rlink; p != head_node; p = p->rlink)
    {
        printf("%d -> ", p->data);
    }
}
​
ListNode *d_search(ListNode *head_node,int x)
{
    ListNode *p = head_node;
    do
    {
        if (p->data == x) return (p);
        p = p->rlink;
    } while (p != head_node);
}
​
//역순은 없음
​
int main()
{
    ListNode head;
    
    ListNode *p[10];
​
    d_init(&head);//헤드 노드 초기화
    for (int i = 0; i < 5; i++)
    {
        p[i] = (ListNode*)malloc(sizeof(ListNode));
        p[i]->data = i;//노드 생성 후 데이터 넣어줌
        d_insert(&head, p[i]);//리스트 연결
    }
    d_delete(&head, p[4]);
​
    printf("탐색 성공 %d \n", (d_search(&head, 2))->data);//탐색 성공 2
​
    d_display(&head);//3->2->1->0->
​
    printf("\n");
    ListNode *list1;
    ListNode head1;
    d_init(&head1);
    d_insert(&head1, d_create(10, NULL, NULL));
    d_insert(&head1, d_create(20, NULL, NULL));
​
    d_delete(&head1, d_search(&head1,10));
​
    d_display(&head1);//20->
}