ysw's blog

List, Linked List

05 Jan 2019 | DataStructure

포스팅

리스트

리스트란 같은 값이 한번 이상 존재할 수 있고 순서가 있는 일련의 값이 모여있는 추상적 자료형(Abstract Data Type)입니다. 예컨대 리스트 (C, Y, R)은 (Y, C, R)과 다릅니다. 리스트에는 Add, Delete, Access(read/change) 연산이 있습니다.

Insert

주어진 리스트의 첫번째 위치에 한 요소를 추가하는 연산의 계산복잡성은 리스트가 $n$개 요소로 구성돼 있을 때 $O(n)$이 됩니다. $n$개 요소 각각의 위치를 오른쪽으로 한 칸씩 모두 옮겨야 하기 때문입니다. $k$번째 위치에 새로운 요소를 추가할 경우 계산복잡성은 $O(n−k)=O(n)$입니다. 한편 주어진 리스트 마지막 위치에 요소를 추가하는 연산은 $O(1)$입니다. 파이썬은 내장함수로 리스트 추가 연산을 제공하는데요. 다음과 같습니다.

a = [1, 2, 3]
a.insert(0, 4)
# [4, 1, 2, 3]

Delete

주어진 리스트의 첫번째 위치에 한 요소를 삭제하는 연산의 계산복잡성은 리스트가 $n$개 요소로 구성돼 있을 때 $O(n)$이 됩니다. $n−1$개 요소 각각의 위치를 왼쪽으로 한 칸씩 모두 옮겨야 하기 때문입니다. $k$번째 위치에 있는 요소를 삭제할 경우 계산복잡성은 $O(n−k)=O(n)$입니다. 한편 주어진 리스트 마지막 위치의 요소를 삭제하는 연산은 $O(1)$입니다. 파이썬은 내장함수로 리스트 삭제 연산을 제공하는데요. 다음과 같습니다.

a = [1, 2, 3]
del a[0]
#[2, 3]

Access

주어진 리스트의 특정 위치에 있는 요소값을 읽거나 바꾸는 $Access$ 연산의 계산복잡성은 $O(1)$입니다. 파이썬은 내장함수로 리스트 $Access$ 연산을 제공하는데요. 다음과 같습니다.

a = [1, 2, 3]
a[0] # 1
a[1] = 4 # [1, 4, 3]

Scalability issue

리스트라는 자료형의 단점은 요소의 최대 개수를 사전에 정해야 하고, 그 개수를 넘어서는 요소들을 입력할 수 없다는 점입니다. 이를 scalability issue라고 합니다. 실제로 파이썬에서 다음과 같은 명령어를 입력했을 때 에러가 납니다. 앞으로 설명할 연결리스트는 이 단점을 극복한 자료구조입니다.

a = [1, 2, 3]
a[3] = 1 # IndexError: list assignment index out of range

연결리스트

연결리스트란 각 노드가 연결되어 있는 방식으로 데이터가 저장돼 있는 추상적 자료형입니다. 한 노드는 해당 노드의 실제값(value)과 다음 노드의 주소값이 담긴 포인터(pointer)로 구성돼 있습니다. 마지막 노드의 포인터는 $Null$값을 갖습니다. 다음과 같습니다.

<내용>

연결리스트는 포인터의 존재 덕분에 리스트의 길이를 사전에 정할 필요가 없습니다. 포인터만 조금 바꿔주면 리스트 요소의 추가가 얼마든지 가능하기 때문입니다.

위의 각 노드를 파이썬으로 구현한 코드는 다음과 같습니다. 각 노드는 개별 클래스로 구성되며 각 노드(클래스)는 실제값(변수명 data에 저장)과 포인터(변수명 next_node에 저장)로 구성됩니다.

class Node(object):
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node
    def set_next(self, new_next):
        self.next_node = new_next

Insert

주어진 연결리스트의 첫번째 위치에 한 요소를 추가하는 연산의 계산복잡성은 리스트가 $n$개 요소로 구성돼 있을 때 $O(1)$이 됩니다. 전체 요소의 인덱스를 변경할 필요 없이 추가할 노드가 가리키는 다음 위치(포인터)를 기존 연결리스트의 첫번째 요소(head)에 연결하고, 추가할 새로운 노드를 기존 연결리스트의 첫번째 요소로 정의하기만 하면 되기 때문입니다. 다음과 같습니다.

class LinkedList(object):

    def __init__(self, head=None):
        self.head = head

    def insert(self, data):
        new_node = Node(data)
        # 추가 노드의 다음 위치를 기존 head에 연결
        new_node.set_next(self.head)
        # 추가 노드를 새로운 head로 정의
        self.head = new_node

Delete

주어진 연결리스트의 첫번째 위치의 요소(head)를 삭제하는 연산의 계산복잡성은 리스트가 $n$개 요소로 구성돼 있을 때 $O(1)$이 됩니다. 전체 요소의 인덱스를 변경할 필요 없이 기존 head의 다음 다음번 노드의 위치를 저장해 두었다가(new_head_next_node), 기존 head의 다음 노드의 값을 새로운 head의 값으로 하고 new_head_next_node를 새로운 head의 포인터로 하는 새로운 head를 재정의해주기만 하면 되기 때문입니다. 다음과 같습니다.

    def delete(self):
        new_head_next_node = self.head.next_node.next_node
        self.head = Node(self.head.next_node.data)
        self.head.next_node = new_head_next_node

Access

주어진 연결리스트의 특정 위치에 있는 요소값을 읽거나 바꾸는 $Access$ 연산의 계산복잡성은 $O(n)$입니다. 예컨대 $k$번째 위치에 있는 값을 읽으려면 $k$개의 요소를 읽어들여야 하기 때문입니다. $idx$번째 요소에 $Access$하는 파이썬 코드는 다음과 같습니다.

    def access(self, idx):
        current = self.head
        i = 0
        while i < idx:
            i += 1
            current = current.next_node
        return current.data

실행

구체적인 실행 결과는 다음과 같습니다.

a = LinkedList()
a.insert(1) 
a.insert(2) 
a.insert(3)
a.access(0) # 3
a.delete()
a.access(0) # 2

여러 가지 연결리스트

지금까지 설명해드린 연결리스트는 엄밀히 말해 단일연결리스트(singly linked list)입니다. 그런데 다음과 같은 변형이 존재합니다. 각각 이중연결리스트(doubly linked list), 원형연결리스트(circular linked list)입니다.

이중연결리스트는 Head와 Tail 모두 움직일 수 있어 $Access$ 연산시 계산복잡성을 줄일 수 있습니다. 원형연결리스트는 링 버퍼(ring buffer) 등과 같이 메모리 효율성이 중요한 디바이스에서 널리 사용되고 있다고 합니다.
<그림 2.>

가져온곳: URL