얼렁뚱땅 개발 블로그

[자료구조] Linked List Part 3. Double Linked List 구현하기 본문

자료구조/연결리스트

[자료구조] Linked List Part 3. Double Linked List 구현하기

김경원0519 2024. 12. 4. 19:17
반응형

목차

※ 해당 게시글은 C언어로 작성되었습니다.

 

1. Doubly Linked List(양방향 연결리스트) 란?

Doubly Linked List는 Node에 이전 Node를 가리키는 Pointer와 다음 Node를 가리키고 있는 Pointer를 가지고 있는 구조입니다.

2. Node 구현

Doubly Linked List의 Node는 data와 다음 Node를 가리키는 Pointer, 이전 Node를 가리키는 Pointer로 구성됩니다.

typedef struct _Node
{
    int data;
    struct _Node *previous_node;
    struct _Node *next_node;
} Node;

3. Node 생성 및 삭제

3.1 Node 생성

매개변수

  • int data : Node의 값입니다.

설명

Node는 동적할당으로 생성을 합니다. 

생성된 Node의 data는 매개변수의 data로 넣어주며, Node의 NextNode와 PreviousNode는 NULL로 지정합니다.

 

코드

Node *create_node(int data)
{
    Node *node = (Node *)calloc(1, sizeof(Node));

    node->data = data;
    node->previous_node = NULL;
    node->next_node = NULL;

    return node;
}

3.2 Node 삭제

매개변수

  • Node *node : 삭제할 Node입니다.

설명

free를 사용하여 생성한 Node를 메모리에서 삭제합니다.

 

코드

void delete_node(Node *node)
{
    free(node);
}

4. Node 추가

매개변수

  •  Node **head : Doubly Linked List의 HeadNode입니다.
  • New *new_node : 추가할 Node입니다.

설명

NewNode를 Tail 뒤에 추가합니다.

  • Head가 NULL인 경우
    • Head를 NewNode로 지정합니다.
  • Head가 NULL이 아닌 경우
    • Tail까지 탐색합니다
    • NewNode의 PreviousNode를 Tail로 지정합니다. 
    • Tail의 NewNode의 NextNode로 지정합니다.

코드

void add_node(Node **head, Node *new_node)
{
    if (*head == NULL)
    {
        *head = new_node;
    }
    else
    {
        Node *tail = *head;

        while (tail->next_node != NULL)
        {
            tail = tail->next_node;
        }

        new_node->previous_node = tail;
        tail->next_node = new_node;
    }
}

5. Node 삽입

5.1. 특정 Node 앞에 삽입

매개변수

  • Node **head : Doubly Linked List의 HeadNode입니다.
  • Node *node : 기준 Node입니다. (이 Node 앞에 NewNode가 삽입됩니다.)
  • New *new_node : 추가할 Node 입니다.

설명

Node 앞에 NewNode를 추가합니다.

 

NewNode의 PreviousNode를 Node의 PreviousNode로 지정 및 NewNode의 NextNode를 Node로 지정합니다.

  • Node가 Head인 경우
    • Head를 NewNode로 지정합니다.
  • Node가 Head가 아닌 경우
    • Node의 PreviousNode의 NextNode를 NewNode로 지정합니다.

Node의 PreviousNode를 NewNode로 지정합니다.

코드

void insert_before_node(Node **head, Node *node, Node *new_node)
{
    new_node->previous_node = node->previous_node;
    new_node->next_node = node;

    if (*head == node)
    {
        *head = new_node;
    }
    else
    {
        node->previous_node->next_node = new_node;
    }
    
    node->previous_node = new_node;
}

5.2. 특정 Node 뒤에 삽입

매개변수

  • Node **node : 기준 Node입니다. (이 Node 뒤에 NewNode가 삽입됩니다.)
  • Node *new_node : 추가할 Node입니다.

설명

NewNode를 Node 뒤에 삽입합니다. 

 

NewNode의 PreviousNode를 Node로 지정 및 NewNode의 NextNode를 Node의 NextNode로 지정합니다.

  • Node의 NextNode가 NULL이 아닐 때
    • Node의 NextNode의 PreviousNode를 NewNode로 지정합니다.

Node의 NextNode를 NewNode로 지정합니다.

코드

void insert_after_node(Node **node, Node *new_node)
{
    new_node->previous_node = *node;
    new_node->next_node = (*node)->next_node;

    if ((*node)->next_node != NULL)
    {
        (*node)->next_node->previous_node = new_node;
    }

    (*node)->next_node = new_node;
}

 

6. Node 제거

매개변수

  • Node **head : Doubly Linked List의 HeadNode입니다.
  • Node *node : Doubly Linked LIst에서 제거 Node입니다.

설명

 

Doubly Linked List에서 Node를 제거합니다. 

제거된 Node는 메모리에 남아있어 동적할당 해제를 따로 해줘야 합니다.

 

  • 제거할 Node가 Head인 경우
    • Head를 Node의 NextNode로 지정합니다.
    • Head(Node의 NextNode)의 PreviousNode를 NULL로 지정합니다.
  • 제거할 Node가 Head가 아닌 경우
    • Node의 PreviousNode의 NextNode를 Node의 NextNode로 지정합니다.
    • Node의 NextNode가 NULL이 아닌 경우 Node의 NextNode의 PreviousNode를 Node의 PreviousNode로 지정합니다.

코드

void remove_node(Node **head, Node *node)
{
    if (*head == node)
    {
        *head = node->next_node;
        (*head)->previous_node = NULL;
    }
    else
    {
        node->previous_node->next_node = node->next_node;

        if (node->next_node != NULL)
        {
            node->next_node->previous_node = node->previous_node;
        }
    }
}

7. Node 탐색

Single Linked List의 탐색 알고리즘과 동일합니다.

8. Doubly Linked List 길이 계산

Single Linked List의 길이 계산 알고리즘과 동일합니다.

9. 전체 코드

main.c

더보기 
#include <stdio.h>
#include "doubly_linked_list.h"

int main(int argc, char *argv[])
{
    Node *linked_list = NULL;
    Node *new_node = NULL;
    Node *node = NULL;

    printf("===[INITIALIZED LINKED LIST]===\n");

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[ADD NEW NODES(5)]===\n");

    for (int i = 0; i < 5; i++)
    {
        new_node = create_node(i);

        add_node(&linked_list, new_node);
    }

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT BEFORE HEAD]===\n");

    new_node = create_node(10);

    insert_before_node(&linked_list, linked_list, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT BEFORE MIDDLE NODE]===\n");

    new_node = create_node(11);
    node = get_node_at(linked_list, get_size(linked_list) / 2 - 1);

    insert_before_node(&linked_list, node, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT BEFORE TAIL]===\n");

    new_node = create_node(12);
    node = get_node_at(linked_list, get_size(linked_list) - 1);

    insert_before_node(&linked_list, node, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT AFTER HEAD]===\n");

    new_node = create_node(20);

    insert_after_node(&linked_list, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT AFTER MIDDLE NODE]===\n");

    new_node = create_node(21);
    node = get_node_at(linked_list, get_size(linked_list) / 2 - 1);

    insert_after_node(&node, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[INSERT AFTER TAIL]===\n");

    new_node = create_node(22);
    node = get_node_at(linked_list, get_size(linked_list) - 1);

    insert_after_node(&node, new_node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n");

    printf("===[REMOVE HEAD]===\n");

    remove_node(&linked_list, linked_list);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[REMOVE MIDDLE NODE]===\n");

    node = get_node_at(linked_list, get_size(linked_list) / 2 - 1);

    remove_node(&linked_list, node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    printf("===[REMOVE TAIL]===\n");

    node = get_node_at(linked_list, get_size(linked_list) - 1);

    remove_node(&linked_list, node);

    print_linked_list_information(linked_list);

    printf("===[END]===\n\n");

    return 0;
}

doubly_linked_list.h

더보기 
#ifndef __DOUBLY_LINKED_LIST_H__
#define __DOUBLY_LINKED_LIST_H__

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

typedef struct _Node
{
    int data;
    struct _Node *previous_node;
    struct _Node *next_node;
} Node;

Node *create_node(int data);
void delete_node(Node *node);
void add_node(Node **head, Node *new_node);
void insert_before_node(Node **head, Node *node, Node *new_node);
void insert_after_node(Node **node, Node *new_node);
void remove_node(Node **head, Node *node);
Node *get_node_at(Node *head, int index);
int get_size(Node *head);

void print_node_information(Node *node);
void print_all_node(Node *head);
void print_linked_list_information(Node *head);

#endif

doubly_linked_list.c

더보기 
#include "doubly_linked_list.h"

Node *create_node(int data)
{
    Node *node = (Node *)calloc(1, sizeof(Node));

    node->data = data;
    node->previous_node = NULL;
    node->next_node = NULL;

    return node;
}

void delete_node(Node *node)
{
    free(node);
}

void add_node(Node **head, Node *new_node)
{
    if (*head == NULL)
    {
        *head = new_node;
    }
    else
    {
        Node *tail = *head;

        while (tail->next_node != NULL)
        {
            tail = tail->next_node;
        }

        new_node->previous_node = tail;
        tail->next_node = new_node;
    }
}

void insert_before_node(Node **head, Node *node, Node *new_node)
{
    new_node->previous_node = node->previous_node;
    new_node->next_node = node;

    if (*head == node)
    {
        *head = new_node;
    }
    else
    {
        node->previous_node->next_node = new_node;
    }

    node->previous_node = new_node;
}

void insert_after_node(Node **node, Node *new_node)
{
    new_node->previous_node = *node;
    new_node->next_node = (*node)->next_node;

    if ((*node)->next_node != NULL)
    {
        (*node)->next_node->previous_node = new_node;
    }

    (*node)->next_node = new_node;
}

void remove_node(Node **head, Node *node)
{
    if (*head == node)
    {
        *head = node->next_node;
        (*head)->previous_node = NULL;
    }
    else
    {
        node->previous_node->next_node = node->next_node;

        if (node->next_node != NULL)
        {
            node->next_node->previous_node = node->previous_node;
        }
    }
}

Node *get_node_at(Node *head, int index)
{
    if (index < 0)
    {
        return NULL;
    }

    Node *current_node = head;

    while (current_node != NULL && --index >= 0)
    {
        current_node = current_node->next_node;
    }

    return current_node;
}

int get_size(Node *head)
{
    int length = 0;
    Node *current_node = head;

    while (current_node != NULL)
    {
        current_node = current_node->next_node;

        length++;
    }

    return length;
}

void print_node_information(Node *node)
{
    printf("address : %p\ndata : %d\nprevious_node : %p\nnext_node : %p\n\n", node, node->data, node->previous_node, node->next_node);
}

void print_all_node(Node *head)
{
    while (head != NULL)
    {
        print_node_information(head);

        head = head->next_node;
    }
}

void print_linked_list_information(Node *head)
{
    printf("[show linked list information]\n");

    print_all_node(head);

    int length = get_size(head);

    printf("\nlinked list size : %d\n", length);
}

github

양방향 연결리스트 소스코드

 

data-structure-with-c/연결리스트/양방향_연결리스트 at master · KimKyungWon0519/data-structure-with-c

Contribute to KimKyungWon0519/data-structure-with-c development by creating an account on GitHub.

github.com

반응형

'자료구조 > 연결리스트' 카테고리의 다른 글

[자료구조] Linked List Part 2. Singly Linked List 구현하기  (0) 2024.11.27
[자료구조] Linked List(연결 리스트) Part 1. Linked List(연결리스트)란?  (0) 2024.11.05
'자료구조/연결리스트' Related Articles more
Comments