List, Linked List
30 Sep 2017 | algorithm
이번 글에서는 리스트(List)와 연결리스트(Linked List) 개념에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 기본으로 하되 조금 수정하였습니다. 그럼 시작하겠습니다.
리스트
리스트란 같은 값이 한번 이상 존재할 수 있고 순서가 있는 일련의 값이 모여있는 추상적 자료형(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) 등과 같이 메모리 효율성이 중요한 디바이스에서 널리 사용되고 있다고 합니다.
이번 글에서는 리스트(List)와 연결리스트(Linked List) 개념에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 기본으로 하되 조금 수정하였습니다. 그럼 시작하겠습니다.
리스트
리스트란 같은 값이 한번 이상 존재할 수 있고 순서가 있는 일련의 값이 모여있는 추상적 자료형(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) 등과 같이 메모리 효율성이 중요한 디바이스에서 널리 사용되고 있다고 합니다.
Comments