배열과 연결리스트는 모양이 비슷해 보이지만 차이가 있다.
배열의 경우는 연속적으로 메모리를 할당받지만, 연결리스트는 생성될 때마다 메모리를 할당받는다.
배열의 경우 인덱스를 이용해서 접근을 할 수 있기 때문에 시간 복잡도는 0(1)상수이다.
하지만 연결리스트의 경우 인덱스를 이용한 접근이 아닌 처음부터 시작해서 해당 값이 있는 노드까지 이동을 해야하기 때문에 O(n)이 된다.
요소에 대한 접근은 배열이 연결리스트에 보다 빠르게 동작할 수 있다는 장점이 있다.
하지만 요소를 추가, 삭제하는 경우는 반대가 된다.
배열의 경우 추가, 삭제하기 위해서는 먼저 해당 요소가 추가되거나 삭제되는 인덱스에 해당하는 위치로 이동한다. 그 후 추가/삭제 작업을 한 뒤 추가된 경우라면 해당 위치로 부터 오른쪽의 모든 요소를 오른쪽으로 한칸씩 뒤 이동시키고, 삭제하는 경우는 왼쪽으로 한칸씩 앞으로 이동시켜야 한다.
그러므로 시간복잡도는 O(n)이 된다.
반대로 연결리스트의 경우는 해당 요소의 앞과 뒤의 위치를 안다는 가정하에서는 앞과 뒤의 요소를 연결하는 링크만 변경해주면 되기 때문에 시간 복잡도가 O(1)이 된다.
Linked List
Linked List에는 Singly Linked List와 Doubly Linked List가 있다.
뜻 그대로 한방향으로만 연결된 리스트와 양방향으로 연결된 리스트이다.
Singly Linked List
단방향 연결리스트의 경우는 한쪽으로만 연결되어있기 때문에 다음 요소의 주소값은 가지나, 앞에 어떤 요소가 있는지는 알 수 없다.
각 요소는 Node라고 하며 Node는 key(해당 노드의 value)와 next(다음 요소의 주소)를 가진다.
class Node:
def __init__(self,key):
self.key = key
self.next = None
def __str__(self):
return str(self.key)
class SinglyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def pushfront(self, key):
new_node = Node(key)
if self.size == 0:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
self.size += 1
def pushback(self, key):
new_tail = Node(key)
if self.size == 0:
self.head = new_tail
else:
tail = self.head
while tail.next != None:
tail = tail.next
tail.next = new_tail
self.size += 1
def popfront(self):
if self.size == 0:
return None
else:
curr_head = self.head
return_value = curr_head.key
self.head = curr_head.next
self.size -= 1
del curr_head
return return_value
def popback(self):
if self.size == 0:
return None
else:
pre_tail, curr_tail = None, self.head
while curr_tail.next != None:
pre_tail = curr_tail
curr_tail = curr_tail.next
if self.size == 1:
self.head = None
else:
pre_tail.next = curr_tail.next
return_value = curr_tail.key
del curr_tail
self.size -= 1
return return_value
탐색과 제너레이터
def search(self, key):
search_node = self.head
while search_node != None:
if search_node.key == key:
return search_node
search_node = search_node.next
return None
def __iter__(self):
node = self.head
while node != None:
yield node.key
node = node.next
return StopIteration
lst = SinglyLinkedList()
lst.pushfront(10)
lst.pushfront(20)
lst.pushfront(30)
lst.pushfront(40)
lst.pushfront(50)
lst.pushfront(60)
lst.pushfront(70)
#70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10
for i in lst:
print(i)연결리스트의 경우 순차적인 자료구조이지만 for문을 사용할 수가 없다.
for문을 사용하기 위해서는 __iter__ 메서드를 정의해주어야 한다.
참고
https://www.youtube.com/watch?v=sMpsvA5O0xU&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=12
https://www.youtube.com/watch?v=kGZoEShMcSQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=13
https://www.youtube.com/watch?v=aCHwXmpuAkY&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=14
