Linked List는 node와 link로 구성된다.

node라는거는 실제 정보를 담고 있는 하나의 단위를 말하고, link는 인접한 노드의 위치를 저장하고 있어서 Linked List의 순서를 유지할 수 있게 하는 연결고리를 말한다.

일단 Linked List는 정적인 자료구조인 배열과는 다르게 동적인 자료 구조이다.

따라서 Linked List는 필요하면 새로 할당하고, 필요가 없어지면 해제하는 식의 메모리 관리가 가능하기 때문에, 배열처럼 여분의 공간을 마련할 필요거 앖어 메모리를 절약할 수 있다는 장점이 있다.

Linked List는 동적으로 메모리를 사용하기 때문에 프로그램이 동작하는 동안에도 얼마든지 크기를 늘리고 줄이고 할 수 있다.

또 Linked List가 배열과 다른 점은 배열은 메모리의 연속된 공간을 차지하는데 비해서 Linked List는 동적으로 수시로 할당되고 해제되기 때문에 메모리의 연속된 공간을 차지하지 못한다.

그래서 Linked List의 각 요소들은 흩어져 있고 순서도 제대로 되어 있지 않고, 이런 Linked List의 순서를 유지시켜 주는것이 바로 link에 의해서 가능해진다.

개인적으로 Linked List는 배열과 다르게 서로다른 자료형의 데이터를 동시에 관리할 수 있다는게 큰 장점이라고 생각한다.

우리가 개념적으로 이해하는 Linked Likst의 모습

실제 메모리 상에 배치된 Linked Likst의 모습

Image source

우리가 머릿속에 개념적으로 상상하는 Linked List의 모습은 배열과 같이 link를 타고 타고 순서대로 나열되어 있는것을 예상하지만 실제로 메모리에 할당된 모습을 보면 그렇지 않다는걸 알 수 있다.

위에서 짧게 설명한것 처럼, 배열은 필요한 크기 만큼 연속된 메모리 공간을 할당받지만, Linked List는 그렇지 않다!

단순 연결 리스트 (Simple Linked List)

말 그대로 가장 단순한 형태임과 동시에 가장 많이 쓰이는 형태이기도 하다.

정보를 저장하는 노드(node)와 바로 다음 노드를 가리키는 링크(link) 하나로 구성이 되어있는 형태다.

위에서도 짧게 적었던것겉 같은데, 연결 리스트의 가장 큰 장점은 재배열이 용이하다라는 부분인데 데이터의 순서를 바꿔야하는 경우가 생기면 배열의 경우는 데이터를 밀거나 당겨오는 메모리 복사가 필요하지만, 연결리스트의 경우는 링크가 라키기는 방향만 바꿔주면 된다.

위 그림처럼 단순 연결 리스트는 각각이 다음의 노드를 정확히 가리키고 있지만, 제일 처음 노드는 "누가 가리켜줄 것인가??" 라는 문제 때문에 "여기가 가장 리스트의 앞부분 이다!" 라고 알려줄 head가 필요하게 된다.

일반적으로 머리(head) 노드는 전역변수로 선언되어서 모듈 내부 어느곳에서도 접근이 가능하도록 한다.

또한 동시에 연결 리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리(tail) 노드를 만들어서 가장 마지막 노드임을 확실하게 표시한다.

사실 이런식으로 head, tail을 전역변수로 만들어두면 메모리적으로 낭비가 있을것 같지만, 프로그램의 일관성을 유지함과 동시에 로직을 작성할때 보다 용이하도록 도와주기때문에 Reasonable하다고 나는 생각한다!

---

List 초기화

typedef struct _node {
    int value;
    struct _node *next;
} node;

node *head;
node *tail;

void init_list(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head -> next = tail;
    tail -> next = tail;
}

먼저 구조체를 사용해야하는데, C를 다뤄보지 않은 사람은 구조체가 뭐지...? 라고 생각할 수 있겠는데 class와 비슷하다고 생각하면 될거같다.

구조체를 이용해서 배열과 다르게 "서로 다른 데이터 타입"도 한번에 관리할 수 있고, 동시에 다른 노드를 가리키는 link인 포인터도 사용할 수 있게 된다.

다음으로 init_list() 함수가 호출되고나면 위 사진처럼 연결 리스트가 초기화된다.

malloc은 memory allocation의 줄임말로, 말 그대로 메모리를 할당받는걸 의미한다.

초기 상태는 리스트에 아무런 데이터가 저장되지 않은 상태이기 때문에 head 다음에는 바로 tail이 위치하게 되고, tail의 next는 list의 끝부분임을 확실히 명시하기 이해서 tail로 설정해 두었다.

list를 순회할때 node = node -> next; 와 같은 형태로 순화하게 될탠데, tail이 NULL이나 기타 엉뚱한곳을 next로 가리키고 있으면 메모리가 어디를 가리키는지 제대로 알 수 없게된다.
이는 나아가서 프로그램이 잘못된 메모리를 참조하면서 다운될수도 있는 일을 야기하므로 좋지 못함!!

---

Insert Behind

Linked List에 다른 Node를 삽입하는 함수인 insert_behind 함수를 만들어 보자.

해당 함수는 먼저 정수인 value와 node형의 포인터 target을 함수 인자로 전달 받는다.

말 그대로 target의 뒤에다가 value를 값으로 가지는 새로운 node를 추가하는 함수다.

왜 target의 뒤에다가 새로운 노드를 추가하는거냐???
왜냐하면 simple linked list는 어떤 node의 next는 알아도 previous는 모르기 때문!
(다음에 Double Linked List를 배워보자)
따라서 어떠한 node의 next link만 조작할 수 있기때문에, target의 뒤쪽에 새로운 node를 삽입할 수 밖에 없다.

node *insert_behind(int value, node *target) {
    node *new;
    
    new = (node *)malloc(sizeof(node));
    new -> value = value;
    new -> next = target -> next;
    target -> next = new;
    
    return new;
}

value를 값으로 갖는 새로운 node인 New를 만들었을때의 상태

new -> next = target -> next 실행 후

target -> next = new 실행 후

코드만 보면 잘 이해가 되지 않을 수 있는 개념이지만, 코드를 보고 그림을 한번 더 보면 이해하기가 더 수월하다!

그리고 실제로도 C언어를 다뤄본적이 없다한들, 그렇게 어려운 개념은 아니라고 생각한다 :)

그보다 그림 하나하나 그리는게 진짜 코드짜는거 보다 더 힘드네? 😞

---

Delete Next

이번에는 target이 가리키는 노드의 다음노드(next)를 삭제하는 함수인 delete_next 함수를 만들어 보자!

target이 가리키는 노드를 삭제하지 않고, target -> next를 삭제하려는 이유는 위에서 언급한것과 정확히 동일한 이유이다.

즉 target을 삭제하려면 target의 previous node의 link를 조작해야하는데, target의 previous를 접근할 수 없다.

int delete_next(node *target) {
    node *t;
    
    // can't delete tail node
    if(target -> next == tail) {
        return 0;
    }
    
    t = target -> next;
    target -> next = target -> next -> next;
    free(t);
    
    return 1;
}

먼저 delete_next 함수는 노드를 삭제하기 이전에 target의 next가 tail인지 확인하는데, tail node를 삭제해버리면 head로 시작해서 tail로 끝나는 Linked List의 구조 자체가 깨져버리기 때문에 조심해야 한다.

만약 target의 next가 tail이 아니라면 정상적으로 삭제하는 작업을 진행한다.

그리고 target의 next를 삭제하려면 target -> next는 target -> next -> next로 링크를 재조정해주면 간단하게 해결할 수 있다.

삭제하기 이전의 원래 List의 상태

target -> next가 꼬리가 아니라면, t = target->next 실행 후

target->next = target->next->next 실행 후

free(t) 실행 후

여기서 중요한 포인트는, 삭제하려고 하는 node를 꼭 free를 통해서 메모리를 해제시켜줘야 한다는거다.

놀랍게도! free를 하지 않고 link만 재조정해도 liked list를 출력해보면 정상적으로 잘 보인다.

하지만, free를 하지 않으면 더 이상 사용하지 않는 node들이 memory 반환을 하지 않게되고 이는 memory leak을 의미하며 전체적은 Performance에 좋지않은 영향을 주게되므로 잘 챙겨줘야 한다!

---

Delete Node

이번에는 Target으로 하는 노드의 다음이 아닌, Target으로하는 노드를 삭제하는 함수를 만들어 보려고 한다.

아니, 방금 전까지는 previous node의 link를 조작할 수 없어서, 내가 원하는 노드를 삭제할 수 없다더니 무슨소리냐??? 라고 할 수 있는데!

다른 포인터를 하나 더 만들어서 마치 내가 원하는 타겟의 앞노드를 알고있는것 같은 방법을 사용해볼건데, 눈여겨볼 기법이다.

int delete_node(int value) {
    node *find;
    node *prev;
    
    prev = head;
    find = prev -> next;
    
    while(find -> value != value && find != tail) {
        prev = prev -> next;
        find = prev -> next;
    }
    
    if(find != tail) {
        prev -> next = find -> next;
        free(find);
        return 1;
    } else {
        return 0;
    }
}

바로 내가 원하는 값을 가지고 있는 node를 찾는 find라는 포인터와, 이 find라는 포인터의 앞을 가리킬 prev라는 포인터 2개를 이용하면 된다.

잘 기억해보면, 연결리스트를 처음에 설계할때 head -> tail 구조로 되어있고 데이터들은 모두 head와 tail 사이에 위치하게 된다.

그 말은 즉, list의 가장 맨앞은 data가 아니라 head라는 의미이고, 이것을 이용하면 target node의 앞 노드의 링크를 건들일 수 있게 된다.

---

이 외에 다른 코드들은 위에서 말한 원리에 몇가지 조건만 더 확인하는 개념들이라 굳이 그림을 그려가면서 설명할 필요는 없을것 같다!

---

전체 코드

//
//  main.c
//  LinkedList
//
//  Created by 박재현 on 2024/05/04.
//

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

typedef struct _node {
    int value;
    struct _node *next;
} node;

node *head;
node *tail;

void init_list(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head -> next = tail;
    tail -> next = tail;
}

void print_list(node *n) {
    printf("\n");
    while(n != tail) {
        printf("%-8d", n -> value);
        n = n -> next;
    }
    printf("\n");
}

node *insert_behind(int value, node *target) {
    node *new;
    
    new = (node *)malloc(sizeof(node));
    new -> value = value;
    new -> next = target -> next;
    target -> next = new;
    
    return new;
}

node *insert_front(int value, int target) {
    node *find;
    node *prev;
    node *new;
    
    prev = head;
    find = prev -> next;
    while(find -> value != target && find != tail) {
        prev = prev -> next;
        find = prev -> next;
    }
    
    if(find != tail) {
        new = (node *)malloc(sizeof(node));
        new -> value = value;
        prev -> next = new;
        new -> next = find;
    }
    return prev -> next;
}

node *find_node(int value) {
    node *t;
    
    t = head -> next;
    while(t -> value != value && t != tail) {
        t = t -> next;
    }
    return t;
}

node *ordered_insert(int value) {
    node *find;
    node *prev;
    node *new;
    
    prev = head;
    find = prev -> next;
    while(find -> value <= value && find != tail) {
        prev = prev -> next;
        find = prev -> next;
    }
    
    new = (node *)malloc(sizeof(node));
    new -> value = value;
    prev -> next = new;
    new -> next = find;
    return new;
}

node *delete_all(void) {
    node *temp;
    node *target;
    
    target = head -> next;
    while(target != tail) {
        temp = target;
        target = target -> next;
        free(temp);
    }
    head -> next = tail;
    return head;
}

int delete_next(node *target) {
    node *t;
    
    // can't delete tail node
    if(target -> next == tail) {
        return 0;
    }
    
    t = target -> next;
    target -> next = target -> next -> next;
    free(t);
    
    return 1;
}

int delete_node(int value) {
    node *find;
    node *prev;
    
    prev = head;
    find = prev -> next;
    
    while(find -> value != value && find != tail) {
        prev = prev -> next;
        find = prev -> next;
    }
    
    if(find != tail) {
        prev -> next = find -> next;
        free(find);
        return 1;
    } else {
        return 0;
    }
}



int main(int argc, const char * argv[]) {
    node *t;
    
    init_list();
    
    ordered_insert(10);
    ordered_insert(5);
    ordered_insert(8);
    ordered_insert(3);
    ordered_insert(1);
    ordered_insert(7);
    ordered_insert(8);
    
    printf("\nInitial Linked list status as below");
    print_list(head -> next);
    
    printf("\nFinding 4 is %ssuccessful\n", find_node(4) == tail ? "un" : "");
    
    t = find_node(5);
    printf("\nFindind 5 is %ssuccessful\n", t == tail ? "un" : "");
    
    printf("\nInserting 9 after 5");
    insert_behind(9, t);
    print_list(head -> next);
    
    t = find_node(10);
    printf("\nDeleting next last node");
    delete_next(t);
    print_list(head -> next);
    
    t = find_node(3);
    printf("\nDeleting next 3");
    delete_next(t);
    print_list(head -> next);
    
    printf("\nInsert node 2 before 3");
    insert_front(2, 3);
    print_list(head -> next);
    
    printf("\nDeleting node 2");
    if(!delete_node(2)) {
        printf("\nDelete 2 is fail");
    }
    print_list(head -> next);
    
    printf("\nDeleting node 1");
    delete_node(1);
    print_list(head -> next);
    
    printf("\nDeleting all node");
    delete_all();
    print_list(head -> next);
}

실행 결과