Prologue

어디선가 '이런 게 있다' 정도만 알았지 실제로 어떻게 구현하고 어디에 쓰이나 생각해본 적이 없다. 그래서 자료구조를 공부하면서 어떻게 쓰일지 생각해보는 겸사겸사 시리즈. 첫번째로 linked list

Problem of array

파이썬은 자료형을 쓸 때 메모리를 할당할 일이 없지만 C는 그렇지 않다.

#include <stdio.h>

int main(){
    int num[4] = {1, 2, 3, 4};
}

이렇게 작성하면 연속한 메모리공간을 아래와 같이 쓰게 된다.

당연히 코드로도 확인할 수 있다.

int main(){
... code ...
    int *p = num;
    double sizeArray = sizeof(num);
    double sizeInt = sizeof(int);
    double len = (int)(sizeArray / sizeInt);
    for (int i = 0; i < len; i++){
        printf("%i ", *(p+i));
    }
}

$ ./a.out
1 2 3 4

이렇게 정한 공간은 내가 원하면 언제든 늘리고 줄일 수 있는 게 아니라서 신중하게 설계해서 최대한 효율적으로 써야 한다. 물론 늘리고 줄이고 하려면 할 수 있지만 복잡해진다. 그래서 머리 좋은 사람들은 생각했다. 메모리공간을 동적으로 쓰는 방법이 없을까?

Linked list

이런 고민으로부터 만들어낸 것이 linked list.

Node는 data를 저장하고, 다음 node를 가리키는 2가지 특성을 가진다.

class Node:
    def __init__(self, data, pointer=None) -> None:
        self.data = data
        self.pointer = pointer

이미지에서도 잘 표현하고 있듯이 linked list는 data를 서로 떨어진 메모리공간에 저장하면서 서로 연결한다. array가 진입지점을 가진 것처럼 linked list의 시작과 끝이라는 단서를 달아줄 거다. 그래야 한 쪽 끝을 잡으면 비엔나 소세지처럼 엮여서 data를 조회할 수 있다.

class LinkedList:
    def __init(self) -> None:
        self.head = None
        self.tail = None
    
    def print_all(self) -> None:
        data = ''
        node = self.head
        if node is None:
            print(None)
        while node:
            data += f'{node.data} -> '
            node = node.pointer
        data += 'None'
        print(data)

잘 되나 보자.

Llist = LinkedList()
node1 = Node(1, None)
node2 = Node(2, node1)
node3 = Node(3, node2)
node4 = Node(4, node3)
Llist.head = node4
Llist.print_all()

# result
4 -> 3 -> 2 -> 1 -> None

array와 달리 느슨하게 연결되어있기 때문에 필요할 때 얼마든지 data를 추가할 수 있다. 일반적으로 새 node를 만들어 head나 tail로 지정하고 기존의 node와 연결하지만 중간에 집어넣어도 새 node와 앞뒤 node를 연결해주는 방법으로 array보다 메모리공간을 동적으로 쓸 수 있게 됐다.

class LinkedList:
..code..
    def insert_at_heaed(self, data):
        if self.head is None:
            self.head = Node(data, None)
            self.tail = self.head
        self.head = Node(data, self.head)

    def insert_at_tail(self, data):
        if self.head is None:
            self.insert_at_heaed(data)  
        self.tail.pointer = Node(data, None)
        self.tail = self.tail.pointer
..code..

Epilogue

• 여기에서는 Single linked list만 알아봤지만 이렇게 생긴 것 말고도 앞뒤로 왔다갔다하는 Double linked list, 순환하는 Circular linked list도 있다.
• Double linked list가 앞뒤로 왔다갔다 할 수 있다고 생각하면 신경망을 구현할 때 list대신 쓰면 좋을 것 같다.
• 구현은 파이썬으로 했지만 좀더 공부하면 C로도 구현할 수 있을 것 같다.