연결리스트는 차례로 연결된 노드를 표현해주는 자료구조이다.
배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없다.
linked list 장점 : Linked list의 길이를 동적으로 조절 가능, 데이터의 삽입과 삭제가 쉬움
linked list 단점 : 임의의 노드에 바로 접근할 수 없음, 다음 노드의 위치를 저장하기 위한 추가 공간이 필요함, Cache locality를 활용해 근접 데이터를 사전에 캐시에 저장하기가 어려움, 거꾸로 탐색하기 어려움
Runner 기법
Runner(부가 포인터라고도 함)는 연결리스트 문제에서 많이 활용되는 기법으로 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 하는데 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼 앞서도록 할 수도 있고, 아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있음
왜 쓰는가?
연결리스트는 중간 위치나 길이를 파악하는 것이 배열에 비해 효율적이지 않다. 따라서 앞선 포인터와 따라오는 포인터간의 step에 차이를 두어 중간 위치를 찾아냄으로써 값 비교나 뒤집기를 시도하는 문제에서 유용하게 사용된다.
면접에서 연결리스트에 대해 이야기 할 때는 단방향 연결리스트에 대한 이야기인지, 양방향 연결리스트에 대한 이야기인지 인지하고 있어야한다.
단방향 리스트 파이썬으로 구현하기
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
def __str__(self):
return str(self.data)
class SingleLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1
def __str__(self):
print_list = '[ '
node = self.head
while True:
print_list += str(node)
if node.next_node is None:
break
node = node.next_node
print_list += ', '
print_list += ' ]'
return print_list
def select_node(self, num):
if self.list_size < num: return
node = self.head
count = 0
while count < num - 1:
node = node.next_node
count += 1
print(node)
return node
def insert_head(self, data):
new_node = Node(data)
new_node.next_node = self.head if self.head is not None else None
self.head = new_node
self.list_size += 1
def insert_tail(self, data):
node = self.head
while True:
if node.next_node is None: break
node = node.next_node
new_node = Node(data)
node.next_node = new_node
self.list_size += 1
def insert_node(self, num, data):
if self.head.next_node is None or num == -1: self.insert_tail(data); return
if self.head is None or num == 0: self.insert_head(data); return
node = self.select_node(num)
new_node = Node(data)
node.next_node, new_node.next_node = new_node, node.next_node
self.list_size += 1
def delete_head(self):
node = self.head
self.head = node.next_node
del node
self.list_size -= 1
def delete_tail(self):
node = self.select_node(self.list_size - 1)
node.next_node, del_node = None, node.next_node
del del_node
self.list_size -= 1
def delete_node(self, num):
if self.list_size < 1 or self.list_size < num: return
if num == 0: self.delete_head(); return
if num == self.list_size: self.delete_tail(); return
node = self.select_node(num - 1)
node.next_node, del_node = node.next_node.next_node, node.next_node
del del_node
self.list_size -= 1
linked_list = SingleLinkedList(1)
linked_list.insert_node(-1, 5)
linked_list.insert_node(-1, 6)
print(linked_list)
linked_list.insert_node(1, 15)
linked_list.insert_node(0, 100)
print(linked_list)
linked_list.delete_node(1)
print(linked_list)
linked_list.delete_node(4)
print(linked_list)양방향 리스트 파이썬으로 구현하기
class Node:
def __init__(self, data):
self.data = data
self.prev_node = None
self.next_node = None
def __str__(self):
return str(self.data)
class DualLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1
def __str__(self):
print_list = '[ '
node = self.head
while True:
print_list += str(node)
if node.next_node is None:
break
node = node.next_node
print_list += ', '
print_list += ' ]'
return print_list
def select_node(self, num):
if self.list_size < num: return
node = self.head
count = 0
while count < num - 1:
node = node.next_node
count += 1
return node
def insert_head(self, data):
new_node = Node(data)
if self.head is not None:
self.head.prev_node, new_node.next_node = new_node, self.head
self.head = new_node
self.list_size += 1
def insert_tail(self, data):
node = self.head
while True:
if node.next_node is None: break
node = node.next_node
new_node = Node(data)
new_node.prev_node = node
node.next_node = new_node
self.list_size += 1
def insert_node(self, num, data):
if self.head.next_node is None or num == -1: self.insert_tail(data); return
if self.head is None or num == 0: self.insert_head(data); return
node = self.select_node(num)
new_node = Node(data)
new_node.prev_node, node.next_node.prev_node = node, new_node
node.next_node, new_node.next_node = new_node, node.next_node
self.list_size += 1
def delete_head(self):
node = self.head
self.head = node.next_node
self.head.prev_node = None
del node
self.list_size -= 1
def delete_tail(self):
node = self.select_node(self.list_size - 1)
node.next_node, del_node = None, node.next_node
del del_node
self.list_size -= 1
def delete_node(self, num):
if self.list_size < 1 or self.list_size < num: return
if num == 0: self.delete_head(); return
if num == self.list_size: self.delete_tail(); return
node = self.select_node(num - 1)
node.next_node, del_node = node.next_node.next_node, node.next_node
node.next_node.prev_node = node
del del_node
self.list_size -= 1💖 참고자료 💖
게일 라크만 맥도웰, [코딩 인터뷰 완전 분석], 프로그래밍 인사이트(2017)