[Data Structure] 연결 리스트(linked list)

---

연결 리스트

 

 

연결 리스트는 노드(node)로 구현된 리스트이다. 기존 배열을 통해 리스트를 사용하는 방식은 데이터 값을 연속적인 형태로 저장하기에 접근이 용이하다는 장점이 있었지만, 삽입과 삭제는 어렵다는 단점이 있었다. 즉 배열에서 접근은 임의접근이 가능하기 때문에 $ \mathcal{O}(1) $ 의 시간복잡도를 가졌지만, 삽입과 삭제는 최대 $ \mathcal{O}(n) $ 의 시간복잡도를 가졌다. 그러나 노드로 연결 리스트를 구현한다면 접근은 어렵다는 단점이 있지만, 삽입과 삭제가 상대적으로 쉽고, 고정된 크기를 가지지 않기에 유연하게 크기를 설정할 수 있다는 장점이 있다. 즉 접근에는 최대 $ \mathcal{O}(n) $ 의 시간복잡도를 가지지만, 삽입과 삭제는 $ \mathcal{O}(1) $ 의 시간복잡도를 가진다.

연결 리스트에서 노드는 데이터와 링크를 가지는 자료구조로 링크는 그 다음 노드를 가리킨다. 노드를 설정하는 방식에 따라 원형 연결 리스트, 이중 연결 리스트 등으로 연결 리스트를 구현할 수 있다. 트리와 그래프를 만들 때도 노드가 사용된다.

추가로 스택이나 큐, 덱을 구현할 때 배열을 사용했듯이 연결 리스트를 사용할 수도 있다.

 

---

ADT

 

객체 (Object)

• 0 개 이상의 노드들로 구성된 순서 있는 모임

연산 (Operation)

• init() ::= 리스트를 초기화한다.
• is_empty() ::= 리스트의 원소 개수가 0 이라면 true 를, 아니라면 false 를 반환한다.
• insert(pos, item) ::= 리스트의 pos 위치에 item 을 추가한다.
• insert_last(item) ::= 리스트의 맨 뒤에 item 을 추가한다.
• insert_first(item) ::= 리스트의 맨 앞에 item 을 추가한다.
• delete(pos) ::= 리스트의 pos 위치에 요소가 존재한다면 리스트의 pos 위치의 요소를 제거한다.
• delete_last() ::= 리스트가 비어있지 않다면 리스트의 맨 뒤의 요소를 제거한다.
• delete_first() ::= 리스트가 비어있지 않다면 리스트의 맨 앞의 요소를 제거한다.
• get_entry(pos) ::= 리스트의 pos 위치에 요소가 존재한다면 리스트의 pos 위치의 요소를 반환한다.
• get_length() ::= 리스트의 원소 개수를 반환한다.

 

---

연산

 

연결 리스트의 삽입, 삭제는 간단히 말하면 각 노드를 끊고 연결해주는 것이다. 예를 들어 연결 리스트를 아래 그림을 통해 다시 보면 노드의 링크가 다음 노드를 가리키고 있는 형태이다.

이제 삽입을 하려면 새로운 노드를 만들고, 그 노드를 삽입하려는 위치에 넣으면 된다. 위치에 넣는다는 것은 중간 연결을 끊고, 앞 노드의 링크가 삽입하려는 노드를 가리키게 만들고, 삽입하려는 노드의 링크가 뒷 노드를 가리키게 만든다는 것이다. 즉 다음과 같다.

삭제를 하려면 기존 노드의 연결을 해제하는 것이다. 즉 삭제하려는 노드의 앞 노드의 링크가 원래 삭제하려는 노드를 가리키고 있었던 것을 삭제하려는 노드의 링크가 가리키는 노드, 즉 삭제하려는 노드의 다음 노드를 가리키게 만드는 것이다. 이때 각 노드들은 동적 할당을 통해 생성되었기 때문에 C 에서는 free 를 통해 동적 할당을 해제하면 노드가 삭제된다.

 

---

구현 | C

 

C 를 통해 구현하였다. 먼저 노드를 구조체로 정의하였고, 그 후 연결 리스트를 구현하였다. 아래 코드는 main 함수를 제외한 연결 리스트 선언과 연결 리스트를 관리하는 함수이다. element 는 임의로 int 로 설정하였고, get_entry 에서 오류가 발생하면 임의로 -1 을 반환하도록 하였다.

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

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

typedef struct {
    Node* head;
    int length;
} LinkedList;

void init(LinkedList* L) {
    L->head = NULL;
    L->length = 0;
}

int is_empty(LinkedList* L) {
    return L->length == 0;
}

void insert(LinkedList* L, int pos, element item) {
    if (pos < 0 || pos > L->length) {
        printf("Invalid location\n");
        return L;
    }
    Node* node = (Node*)calloc(1, sizeof(Node));
    node->data = item;
    if (pos == 0) {
        node->link = L->head;
        L->head = node;
    } else {
        Node* pre = L->head;
        for (int i = 0; i < pos - 1; i++) {
            pre = pre->link;
        }
        node->link = pre->link;
        pre->link = node;
    }
    L->length++;
}

void insert_first(LinkedList* L, element item) {
    insert(L, 0, item);
}

void insert_last(LinkedList* L, element item) {
    insert(L, L->length, item);
}

void delete(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return L;
    }
    Node* removed;
    if (pos == 0) {
        removed = L->head;
        L->head = L->head->link;
    } else {
        Node* pre = L->head;
        for (int i = 0; i < pos - 1; i++) {
            pre = pre->link;
        }
        removed = pre->link;
        pre->link = removed->link;
    }
    free(removed);
    L->length--;
}

void delete_first(LinkedList* L) {
    delete(L, 0);
}

void delete_last(LinkedList* L) {
    delete(L, L->length - 1);
}

element get_entry(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return -1;
    } else {
        Node* current = L->head;
        for (int i = 0; i < pos; i++) {
            current = current->link;
        }
        return current->data;
    }
}

int get_length(LinkedList* L) {
    return L->length;
}

void print_list(LinkedList* L) {
    for (Node* current = L->head; current != NULL; current = current->link) {
        printf("%d -> ", current->data);
    }
    printf("NULL\n");
}

연결 리스트는 배열을 이용한 리스트와 큰 차이가 없으므로 main 함수를 통한 입출력은 생략한다.

 

C 에서는 따로 라이브러리가 없지만, 라이브러리로 구현되어 있는 언어도 많으므로 사용하려는 언어에 맞게 찾아보면 좋다.

백준의 구체적인 연결 리스트 연습 문제는 없지만 요세푸스 문제(링크)를 통해서 연결 리스트를 연습해볼 수 있겠다.