[C언어 포인터 기반 리스트 알고리즘] 양방향 연결리스트 특정 원소 오름차순 삽입 및 삭제하기

💡 산넘어 산이라는 뜻이 이런 것을 말하는 것인가.. 너무 너무 어렵다..

문제

💡 배열 [1, 2, 3, 7, 9]에서 배열 [2, 3, 7, 9]로 변경하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;    
} Node;

Node *head, *tail;

void insert(int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    Node* cur;
    cur = head->next;
    while(cur->data < data && cur != tail) {
        cur = cur->next;
    }
    Node* prev = cur->prev;
    prev->next = node;
    node->prev = prev;
    cur->prev = node;
    node->next = cur;
}

void removeFront() {
    Node* node = head->next;
    head->next = node->next;
    Node* next = node->next;
    next->prev = head;
    free(node);
}

void show() {
    Node* cur = head->next;
    while (cur != tail) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
}

int main(void) {
    head = (Node*) malloc(sizeof(Node));
    tail = (Node*) malloc(sizeof(Node));
    head->next = tail;
    head->prev = head;
    tail->next = tail;
    tail->prev = head;
    insert(2);
    insert(1);
    insert(3);
    insert(9);
    insert(7);
    removeFront();
    show();
    
    return 0;
}

설명

일단 함수마다 설명이 필요할 것 같아서 함수별로 설명을 적어보겠다.

내가 이해하기 어려웠던 이유가 ‘양방향’이라는 것을 잘 이해를 못해서 이해하기 더 어려웠다.

main 함수

prevnext↔prevnext

head

tail

main 함수에서 insert 함수를 호출하기 전에는 위와 같은 모양인 것이다.

head->next = tail;  // head의 next는 tail이다.
head->prev = head;  // head의 prev값은 head 자신이다.
tail->next = tail;  // tail의 next는 tail이다. tail은 next가 없다.
tail->prev = head;  // tail의 prev는 양방향이므로 head이다.

insert 함수

이번에는 오름차순으로 노드를 삽입해보려고 한다.

void insert(int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;  // node의 데이터를 매개변수로 받아온 data로 초기화 한다.
    Node* cur;  // cur 변수를 초기화 해준다.
    cur = head->next;  // head의 next가 첫번째 원소이다.

    while(cur->data < data && cur != tail) {
				/* 오름차순으로 정렬하기 위해 cur의 현재 data가 들어온 data보다 작고
				   cur이 tail이 아니여야 cur의 next를 다음 next로 이동해준다. 
					 예) cur->data = 5이고 삽입할 data가 6이라면 정렬하지 않는다.
					 예) cur->data = 5이고 삽입할 data가 4라면 정렬한다. */
        cur = cur->next;
    }

    Node* prev = cur->prev;  // prev를 삽입할 노드의 바로 앞쪽 노드로 자리를 잡아준다.
    prev->next = node;  // 현재 삽입할 노드
    node->prev = prev;  // 현재 삽입할 노드의 앞쪽에 있는 노드
    cur->prev = node;  // 뒤쪽에 있는 노드가 prev
    node->next = cur;  // 삽입할 노드에 바로 뒤에 들어갈 노드
}

아.. 포스팅을 하기는 하지만 백프로 이해가 가지는 않는다. (∘⁼̴⃙̀˘︷˘⁼̴⃙́∘)

강의에서도 빨리 넘어가고.. 일단 주석으로 설명은 다 써 놓았으니 계속 읽어보며 이해하는 방법밖에 없는 것 같다.

remove함수

이번에는 첫번째 노드를 삭제해 보려고 한다.

void removeFront() {
    Node* node = head->next;  // node는 head의 next가 될 수 있게 한다.
    head->next = node->next;  // head의 next는 node의 next가 되게 하여 다음 노드를 가리킬 수 있게 한다.
    Node* next = node->next;  // next는 node의 next가 되게 한다.
    next->prev = head;  // next의 prev는 head가 되게 한다.
    free(node);  // node의 메모리 할당을 해제시켜준다.
}

아 정말 어렵다..

---

마치며..

정말 8분짜리 강의를 여섯시간 넘게 이해하려고 하면서 계속 돌려봤는데 이렇게 이해가 되지 않는 것은 나의 문제인 것인가..껄껄

선생님… 너무 빠르고 설명이 부족해요..