리스트(List), 배열(Array), 연결 리스트(Linked List)

리스트는 선형적으로(순서가 존재한다는 뜻) 값들을 가지고 있는 자료구조이며, 흔히 배열(array)과 연결 리스트 (linked list)로 나눌 수 있다. 먼저 배열을 살펴보자.

배열(Array)

언어 공부를 할 때 배열의 경우 많이 사용해 보았을 것이다. 예를 들어 숫자 1부터 5까지를 저장하고 싶다면, c언어의 경우 아래와 같이 배열을 선언 할 수 있다.

int array[5] = {1, 2, 3, 4, 5}

그렇다면 배열이란 무엇일까? 자료구조에서 배열은 다음과 같이 말 할 수 있다.

메모리 상에 원소를 연속하게 배치한 자료구조

아래 그림을 보면 위 말이 무엇인지 상상할 수 있을 것이다.

배열의 이름은 배열이 저장된 시작 주소를 가르킨다고 보면 된다.

 

때문에 배열의 인덱스로 데이터를 접근하면 해당 배열이 저장된 시작주소에서 인덱스만큼 떨어진 곳에 저장된 데이터를 가져오게 된다.

 

그리고 배열은 메모리 상에 원소를 연속으로 배치했기에 다음과 같은 특성을 가진다.

 

위에서 설명한대로, 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이라서 k번째 원소의 위치를 바로 계산할 수 있다. 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문에 k번째 원소를 O(1)에 확인하거나 변경할 수 있다.

 

그리고 배열은 선언한 길이만큼 메모리에 할당해주기 때문에 추가적으로 소모되는 메모리의 양이 거의 없다. 하지만 메모리상에 연속한 구간을 잡아야 해서 할당에 제약이 걸릴 수 있다.

 

데이터 삽입, 삭제, 조회

배열과 리스트를 비교 할 때 극명하게 차이가 나는부분이 데이터를 저장, 삭제하는 연산이다.

배열은 임의의 위치에 있는 원소를 확인, 또는 변경할 때 인덱스로 원소에 바로 접근할 수 있기에, O(1)의 시간복잡도를 가진다.

// 변경
arry[1] = 3

// 확인
arry[1] // 3반환

하지만 임의의 위치에 원소를 추가, 삭제할 때는 삽입, 삭제한 위치 이후에 나머지 원소들을 뒤로 밀거나 앞으로 땡겨줘야하기에, O(N)의 시간복잡도를 가진다.

---

연결 리스트(Linked List)

배열이 메모리에 원소를 연속되게 저장했다면 연결리스트는 조금 다르다.

 

연결리스트는 원소를 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조다.

때문에 원소가 꼭 메모리에 연속적으로 저장돼있지 않다. 아래 그림을 보면 원소 1, 2, 3, 4, 5가 연속적으로 저장돼있지 않은 모습을 볼 수 있다.

대신 1번 원소가 2번째 원소를 가르키고 3번 원소가 4번원소를 가르키고 있는 구조이다.

각 원소를 저장하고 있는 덩어리를 흔히 노드(Node) 라고 부른다.

노드는 자신이 보존 중인 값과 다음 노드를 가르키는 포인터 이 두가지를 가지고 있다.

 

포괄적인 연결 리스트에서, 연결 리스트의 시작점을 헤드라 부르고 끝부분을 테일이라고 부른다. 머리와 꼬리 알기 쉽지 않은가 ㅎㅎ

 

데이터 삽입, 삭제, 조회

배열과 차이를 극명하게 보이는 부분이 바로 삽입, 삭제, 조회 연산이다. 원소를 삽일할 때 값이 저장된 ‘주소를 안다면’ O(1)의 시간 복잡도를 가질 수 있다. 하지만 배열은 값을 삽입하고 원소들의 인덱스를 뒤로 한칸씩 밀어줘야 하기에 O(N)을 가진다.

 

삽입

위 그림에서 볼 수 있듯이, 77과 6사이 연결을 끊고 77의 포인터가 80을, 80의 포인터가 6을 가르키게만 해주면 삽입연산은 끝이다. 배열을 밀어주거나 하는 추가적인 동작이 없다.

데이터 삭제의 경우도 마찬가지다. 노드의 주소만 안다면 O(1)의 시간복잡도 내에서 할 수 있다.

삭제

77에서 80으로의 연결을 끊고 77은 다시 6을 가르키기만 하면 끝이다.

 

하지만 데이터를 조회할 때는 조금 이야기가 다르다. 연결 리스트의 순회는 단순히 헤드부터 매 노드를 반복문으로 순회해가며 원소를 찾아야 하기 때문에 N번째 요소를 찾기위해서는 O(N)이 걸릴 수 밖에 없다.

 

이 정도로 배열과 연결 리스트의 차이점이 존재한다. 때문에 사용되는 부분도 그 장점에 따라 다르다.

 

연결리스트의 삽입/삭제 연산의 용이함은 후에 스택, 큐, 덱 등의 기본적인 자료구조를 구현하는 데 많은 도움을 준다. 그러나 랜덤 엑세스가 필요할 때에는 배열이 적합하다고 볼 수 있다.

---

이제 코드를 통해 연결 리스트를 한 번 구현해보자.

 

연결 리스트

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init

        self.cur = None
        self.size = 0
    
    # 연결 리스트 사이즈 반환
    def __len__(self):
        return self.size

    # tail에 데이터를 삽입하고 tail을 new_node로 바꿔준다.
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node
        self.size += 1
    
    # 양방향 연결리스트가 아니므로 이전 노드를 알 수 없어서 순회가 필요하다.
    def pop(self):
        last_value = self.tail.data
        cur_node = self.head

        for i in range(self.size):
            if cur_node.next is self.tail:
                self.tail = cur_node
                break
            cur_node = cur_node.next
        self.size -= 1
        return last_value

    # 찾을 시 데이터의 인덱스를 반환, 아니면 -1을 반환
    def find(self, data):
        idx = -1
        cur_node = self.head

        for i in range(self.size+1):
            if cur_node.data == data:
                return idx
            idx += 1
            cur_node = cur_node.next
        return -1

연결 리스트는 여러 가지 변형도 존재한다.

마지막 노드의 next가 다시 첫 번째 노드를 가리키는 형태의 순환 구조를 갖는 원형 연결 리스트(circular linked list) 각 노드가 next 포인터뿐 아니라, 자신의 이전 노드를 가리키는 prev 포인터를 추가로 갖는 이중 연결 리스트(doubly linked list) 들도 존재한다!