문과생이 이해한 이중 연결리스트

출처 : 깃 허브

 

github.com/Shinsungjun/VScodecommit/blob/master/DataStructure/LinkedList/DoublyLinkedList1.c

Shinsungjun/VScodecommit

 

 이 코드를 가지고 공부햇다. 본 코드는 뒤에서만 추가가 가능하길래 앞에서도 추가할 수 있는 코드를 추가했다.

 

 

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

typedef struct NODE {   //여기에 NODE안 써줘면 에러
    struct NODE* llink;
    int data;
    struct NODE* rlink;
}NODE;

NODE* head;
NODE* tail;

//노드 생성 함수
NODE* makenode(int value) {
    NODE* node = (NODE*)malloc(sizeof(NODE));
    node->llink = NULL;
    node->data = value;
    node->rlink = NULL;
    return node;
}

//출력 함수
void print() {
    NODE* p = head->rlink;
    while (p->rlink != tail) {
        printf("%d-->", p->data);
        p = p->rlink;
    }
    printf("%d\n\n", p->data);
}

void init() {
    head = (NODE*)malloc(sizeof(NODE));
    tail = (NODE*)malloc(sizeof(NODE));
    head->data = 0;
    tail->data = 0;

    head->rlink = tail;
    head->llink = NULL;
    tail->rlink = NULL;
    tail->llink = head;
}

//tail 앞
void push_back(int value) {
    NODE* newnode = makenode(value);
    tail->llink->rlink = newnode;
    newnode->llink = tail->llink;
    tail->llink = newnode;
    newnode->rlink = tail;
}


//head 뒤
void push_front(int value) {
    NODE* newnode = makenode(value);
    newnode->llink = head;
    newnode->rlink = head->rlink;
    head->rlink = newnode;
    head->rlink->llink = newnode;
}


void removenode(int value) {
    NODE* p = head->rlink;

    while (p->rlink != tail) {
        if (p->data == value) {
            p->rlink->llink = p->llink;
            p->llink->rlink = p->rlink;
            free(p);
            return;
        }
        p = p->rlink;
    }
}

int main() {
    init();
    printf("----before----\n\n");
    push_back(10);
    push_back(30);
    push_back(50);
    push_front(70);
    print();
    printf("----after----\n\n");
    removenode(30);
    print();
    return 0;
}

 

 

#init()

 

 

 

---

 

 

#push_back(10)

 

  요로코롬 새로운 노드의 llink와 rlink, head의 rlink와 tail의 link 총 4번의 링크 필드를 수정해주면 새로운 노드 추가가 가능하다!

 

 

 

---

 

#push_front(70)

 일단 push_back을 10/30/50까지 넣었다고 하면 현재 연결리스트이 상태는 위 그림과 같다. 

 

 

 

 makenode 함수를 통해서 newnode를 초기화 해주고 push_back과 똑같은 연산을 해주면 된다!

 

 

 

 

---

 

 

#removenode(30)

 

 너무 길어서 저렇게 옹졸하게 넣어놨다.... 

 

 

removenode는 간단하다. 삭제할 값을 value에 저장하고 순회용 포인터를 만든 다음에, 현재 포인터가 가리키는 노드의 data와 value값이 일치하는 지 확인한다. 일치하면 일단 해당 노드를 가리키고 있는 양 옆 노드- 왼쪽에 있으면 rlink를 오른쪽에 있으면 llink를-의 링크 필드를 수정하고, 해당 노드를 free()해준다. 

 

 이 작업은 push와 유사하다. 

 

 

 

---

#print

 

 대망의 print. print는 어떤 연결 리스트든 비슷한 것 같다. 차이점이라면 이중연결리스트는 NULL이 아니라 tail이 아닐때까지 반복한다는 거. 

 

 그림의 초록색은 removenode 연산을 하면서 바뀐 양옆 노드의 링크 필드이다!