12. Linked List(1)

안녕하세요. 명절을 쉬고 오랜만에 포스팅합니다. 저번 알고리즘 포스팅에서도 바쁘다는 핑계를 댔었는데 저 스스로에게 미안해지려고 하네요. 오늘 주제는 Linked List입니다. 자료구조에 관한 내용은 알고리즘 카테고리에 포스팅하는 것이 처음인 것 같은데요. 자료구조는 말 그대로 자료를 저장하는 구조입니다. 자료마다 저장하기 편리한(?), 잘 들어맞는(?) 구조가 있고 그걸 알아내고 유지 관리하는 것이 DB 설계자, 관리자 분들이 하시는 일이겠죠. 

 

 

11.01. Linked List

 

Insertion, Deletion, Search

 

이 세가지 연산이 가장 중요합니다. 물론 모든 연산에 대해 속도를 내는 자료구조를 만드는 것은 쉽지 않기 때문에 각 상황이나 자주 호출되는 연산에 따라 효율적인 자료구조들이 많이 개발되어 있습니다. Stack, Queue, List는 자료구조 과목에서는 항상 셋뚜셋뚜로 배우는 것인거 다들 알고 있으실 거라 생각합니다. Stack, Queue를 배열로 구현하는 경우도 있긴 하죠. 그렇지만 결국은 linked list로 구현하는 것도 배웁니다.

 

List라는 것은 선형적으로 value를 저장하는 자료구조이고 Array와 Linked list로 나눈다고도 합니다만 Python에서 Numpy를 배우신 분들은 List와 Array의 차이를 지적하실수도 있습니다. Linked list는 value가 node를 이루고 있고 각 node는 자신의 다음 node를 가리키고 있습니다. 다음 node가 없다면 node가 가리키는 next node pointer는 NULL pointer가 됩니다.

즉, 일반적으로 node는

Value + Next node pointer

 

로 구성됩니다. 그리고 Linked list라는 구조 전체를 control하기 위해 head pointer를 사용하여 head node를 가리키고 있습니다. 이때 list의 size, 계산에 필요한 특정한 index등을 저장하여 유지, 관리를 돕습니다.

record Node
{
    data; // The data being stored in the node
    Node next // A reference to the next node, null for last node
}

 

record List
{
    Node firstNode // points to first node of list; null for empty list
}

 

 

11.02. Add Node

node addNode(node head, int value) {
    node temp, p; // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL.
    temp->data = value; // add element's value to data part of node
    if (head == NULL) {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points to NULL.
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}

다른 연산들에 대해서는 다음 포스팅과 문제풀이 포스팅에서 더 자세히 살펴보겠습니다.

 

 

11.03. Additional things to consider

11.03.1. Linked List와 Dynamic Array 비교

동적 배열은 모든 요소를 메모리에 연속적으로 할당하는 자료구조입니다. 연속적으로 할당된다는 점으로부터 얻을 수 있는 장점은 명확합니다. 일정 시간내에 index를 통한 빠른 접근이 가능하다는 것이죠. 이를 Constant-time random access라고 부릅니다. Locality of reference도 생각해볼 필요가 있겠군요. 단점은 예약한 공간을 초과하면 재할당이 필요하고 복사되는데 이 과정은 cost가 꽤 많이 필요한 작업입니다. Linked list는 동적배열의 장점을 단점으로 단점을 장점으로 가지고 있다고 생각하시면 됩니다. 또한 next node pointer만큼 추가 저장 공간이 필요한데 이것도 단점이겠네요. 이렇게 대척점에 서있는 두 개념은 항상 hybrid solution이 있기 마련입니다. Cache 성능과 memory overhead를 줄일 수 있습니다.

 

자료구조를 한눈에 비교한 좋은 자료가 있어 가져와보았습니다.(Wiki에서 가져왔다는 건 안비밀.. 읍읍 wiki를 무한 신뢰하는 것은 아니지만 그냥 한번 보고 넘기기엔 괜찮죠. 이론적으로 deep(?)하게 알아보고 싶다면 다른 자료를 더 찾아보셔야 합니다.)

 

11.03.2. Circular Linked List, Doubly Linked List

Linked list는 basic linked list에 조그마한 부분을 수정해 여러 변형 linked list를 만들 수 있습니다. 문제에 따라서 그런 변형을 요구하는 경우가 종종 있습니다.

 

Circular linked list는 마지막 node의 next node pointer가 첫번째 node를 가리키는 형태로 순환구조를 가집니다. 

 

Doubly linked list는 next node pointer와 함께 prev node pointer를 추가로 갖습니다. 물론 circular linked list와 doubly linked list의 성질을 포함하는 linked list도 만들 수 있습니다. C++에서 제공하는 list가 doubly linked list라는 사실만 알고 있어도 충분합니다. 여러 문제를 살펴보겠지만 배열을 사용해도 풀리는 문제가 분명 있습니다. C++같은 경우 vector class를 사용해보는 것도 좋겠군요. 물론 data의 size에 따라 시간제한에 걸릴 수도 있습니다. 하지만 뭐 어때요. 풀어보고 안되면 다르게 접근하면 되는거죠.

 

 

추가로 검색을 용이하게 해드리기 위해서 Linked list와 관련된 모든 글은 Linked list tag를 사용하였습니다. 도움되시길 바라겠습니다.

https://ku320121.tistory.com/tag/Linked%20List

SONGANG