LinkedList(연결리스트)

LinkedList(연결리스트) 에 대해 알아보겠습니다.

LinkedList는 각 노드들이 연결되어 있는 형태의 자료구조입니다.

배열(array)은 인덱스로 관리되는 반면에 연결리스트는 각 노드가 다음노드의 포인터를 가지는 구조로 되어있습니다.

                               

각 노드는 데이터와 주소로 이루어지고, 하나의 노드는 다음 노드의 주소를 가지고 있습니다.

마지막 노드는 다음 노드의 주소를 가질수 없기 때문에 주소값을 NULL값으로 가집니다.

연결리스트와 비교되는 배열은 위에 같은 형태를 띄고 있으며, 데이터를 가지는 위치를 index로 나타냅니다.

배열의 이름과 index를 사용하여 (ex: arr[0], arr[1]) 특정 index를 가지는 노드에 바로 접근이 가능합니다.

그렇기 때문에 배열은 특정 위치를 지정하여 검색할 때는 매우 빠른 속도를 가지지만, 특정위치의 삽입 및 삭제시 속도가 느리다는 단점이 있습니다.

특정위치에 삽입이나 삭제연산이 발생하면 해당 위치로부터 뒤에 위치하는 노드들은 모두 자리 이동이 일어나기 때문입니다.

반면, 연결리스트는 삽입과 삭제를 하기 위해서는 노드가 가르키는 다음노드의 주소만 변경해주면 되기 때문에, 삽입과 삭제가 빠르지만, 검색을 위해서는 연결된 주소를 따라서 이동하여 검색하기 때문에 상대적으로 속도가 느립니다.

또한, 배열은 실제 메모리에서도 물리적으로 연속된 주소를 가지지만, 연결리스트는 그렇지 않고 다음주소의 포인터를 가진다는 차이가 있을 수 있습니다.

다음은 연결리스트를 실제로 구현해보았습니다.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    char data;
    struct Node *next;
}Node;
 
Node *head;
 
void addFront(Node *root, int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
}
 
int search(int data) {
    Node *cur;
    for(int i=0; ; i++) {
        if(i==0) cur = head->next;
        else cur = cur->next;
        printf("cur data is %d \n", cur->data);
        if(cur->data == data) return i;
    }
}
 
void removeFront(Node *root) {
    Node *front = root->next;
    root->next = front->next;
    free(front);
}
 
void freeAll(Node *root) {
    Node *cur = head->next;
    while(cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}
 
void showAll(Node *root) {
    Node *cur = head->next;
    while(cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
}
 
int main() {
    head = (Node*) malloc(sizeof(Node));
    head->next = NULL;
    addFront(head, 2);
    addFront(head, 1);
    addFront(head, 7);
    addFront(head, 9);
    addFront(head, 8);
    printf("search index = %d\n", search(7));
    removeFront(head);
    showAll(head);
    freeAll(head);
 
    return 0;
}

head 노드는 기준점을 잡아주기위해 data없는 노드로 삽입하였고, search 함수를 살펴보면 하나하나씩 노드를 순회하며 데이터를 검색하는 것을 확인할 수 있습니다.

이상으로 연결리스트에 대해 알아보았습니다.