[자료구조] Linked List Part 2. Singly Linked List 구현하기

목차

1. Singly Linked List(단방향 연결리스트) 란?

2. Node 구현

3. Node 생성 및 삭제

4. Node 추가

5. Node 삽입

6. Node 제거

7. Node 탐색

8. Singly Linked List 길이 계산

9. 전체 코드

---

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

 

1. Singly Linked List(단방향 연결리스트) 란?

Singly Linked List는 Node의 Pointer가 다음 Node를 가리키고 있는 구조입니다.

---

2. Node 구현

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

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

---

3. Node 생성 및 삭제

3.1 Node 생성

매개변수

• int data : Node의 값입니다.

설명

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

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

 

코드

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

    node->data = data;
    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 : Singly Linked List의 HeadNode입니다.
• New *new_node : 추가할 Node입니다.

설명

NewNode를 Tail 뒤에 추가합니다.

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

코드

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

        tail->next_node = new_node;
    }
}

---

5. Node 삽입

5.1. 특정 Node 앞에 삽입

매개변수

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

설명

Node 앞에 NewNode를 추가합니다.

• Node가 Head와 동일한 경우
  • NewNode의 NextNode를 Node로 지정한 뒤, Head를 NewNode로 지정합니다.
• Node가 Head가 아닌 경우
  • 기준 Node의 이전 Node(이하. PreviousNode)까지 탐색을 합니다. NewNode의 NextNode를 Node로 지정한 뒤, PreviousNode의 NextNode를 NewNode로 지정합니다.

코드

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

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

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

5.2. 특정 Node 뒤에 삽입

매개변수

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

설명

NewNode를 Node 뒤에 삽입합니다. 

 

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

코드

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

 

---

6. Node 제거

매개변수

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

설명

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

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

 

• 제거할 Node가 Head인 경우
  • Head를 Node의 NextNode로 지정합니다.
• 제거할 Node가 Head가 아닌 경우
  • Node의 이전 Node(이하. PreviousNode)까지 탐색을 합니다. 
  • PreviousNode의 NextNode를 Node의 NextNode로 지정합니다.

코드

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

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

        previous_node->next_node = node->next_node;
    }
}

---

7. Node 탐색

매개변수

• Node *head : Singly Linked List의 HeadNode입니다.
• int index : 가져올 Node의 index입니다.

설명

• index가 0보다 작을 경우
  • NULL을 반환합니다.
• index가 0보다 클 경우
  • 반복문을 Index 만큼 돌리면서 CurrentNode가 NULL이 아닌 경우 Current를 Current의 NextNode로 지정합니다. 
  • 반복문을 빠져나가면 CurrentNode를 반환합니다.

코드

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

---

8. Singly Linked List 길이 계산

매개변수

• Node *head : Singly Linked List의 HeadNode입니다.

설명

CurrentNode를 head로 지정합니다. 그 후 CurrentNode가 NULL이 아닐 때까지 반복문을 돌리면서 CurrentNode를 CurrentNode의 NextNode로 지정합니다. 해당 과정을 반복할 때마다 Length을 증가시켜주며, 반복문을 빠져나갈 경우 Length를 반환합니다.

코드

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

---

9. 전체 코드

main.c

#include <stdio.h>
#include "singly_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;
}

singly_linked_list.h

#ifndef __SINGLY_LINKED_LIST_H__
#define __SINGLY_LINKED_LIST_H__

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

typedef struct _Node
{
    int data;
    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

singly_linked_list.c

#include "singly_linked_list.h"

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

    node->data = data;
    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;
        }

        tail->next_node = new_node;
    }
}

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

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

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

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

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

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

        previous_node->next_node = node->next_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\nnext_node : %p\n\n", node, node->data, 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