[Data Structure] #1-2 연결 리스트

연결리스트 (LinkedList)

 연결리스트의 가장 큰 특징은 데이터를 저장할 공간이 필요할 때마다 '동적'으로 공간을 만들어서 쉽게 추가가 가능하다는 점이다. 이전에 다뤘던 배열 리스트와 큰 차이점을 나타낸다. 삽입, 삭제시에 배열리스트보다 부담이 적다. 

 연결리스트 또한 어려운게 별로 없으므로 자세한 설명은 생략한다. 코드는 아래와 같다. 아래 코드에서 reverse만 자세하게 다시 보도록 하자.

#include <stdio.h>

#include <stdlib.h>

typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node){
    if(*phead == NULL) { // 리스트에 아무것도 없는 경우
        new_node->link = NULL;
        *phead = new_node;
    }else if(p == NULL){ // 넣고자하는 위치 값이 없는 경우 가장 첫번째 노드로 삽입한다
        new_node->link = *phead;
        *phead = new_node;
    }else { // p 노드의 뒤로 삽입한다
        new_node->link = p->link;
        p->link = new_node;
    }
}

void remove_node(ListNode **phead, ListNode *p, ListNode *remove_node){
    if (p == NULL) // 여기서 p는 삭제할 노드의 앞 노드를 의미한다
        *phead = (*phead)->link;
    else // 삭제할 노드(remove_node)가 분명히 있고 그 앞의 노드(p)도 알 때
        p->link = remove_node->link;
    free(remove_node);
}

void display(ListNode *head){
    ListNode *p = head;
    while (p != NULL) {
        printf("%d->",p->data);
        p = p->link;
    }
    printf("\n");
}

void display_recur(ListNode *head){
    ListNode *p = head;
    if(p == NULL) return;
    printf("%d->",p->data);
    display_recur(p->link);
}

ListNode* create_node(element item){
    ListNode* new_node = (ListNode*) malloc(sizeof(ListNode));
    new_node->link = NULL;
    new_node->data = item;
    return new_node;
}

ListNode* search(ListNode *head, int x){
    ListNode *p;
    p = head;
    while (p != NULL) {
        if(p->data == x) return p;
        p = p->link;
    }
    return NULL;
}

ListNode *concat(ListNode *head1, ListNode *head2){
    ListNode *p;
    p = head1;
    while (p->link != NULL) {
        p = p->link;
    }
    p->link = head2;
    return head1;
}

ListNode *reverse (ListNode *head){
    ListNode *p; // 제일 앞에서 나아가는 노드
    ListNode *q; // p를 따라간다
    ListNode *r; // q를 따라간다
    
    p = head;
    q = NULL; // 밑에서 쓰이기 때문에 q를 미리 null로 만든다
    
    while (p != NULL) {
        r = q;
        q = p;
        p = p->link; // 나아간다
        q->link = r; // 여기서 중간 노드가 이전의 노드를 가리키게 된다
    }
    return q; // p는 null이 되었으므로 q가 가장 앞에 존재하는 노드
}

여기서 reverse는 3개의 포인터로 움직인다. 3개의 포인터는 모두 나란하게 움직이는데 p는 계속 한칸씩 나아가는 형태이고 q,r이 그 뒤를 따른다. 그러다 중간 노드 역할인 q가 자신이 가리키는 노드를 r로 바꿔버린다. 반대 방향으로 화살표를 돌리는 것이다. 그럼으로써 reverse 를 만들어간다.