링크드 리스트 (Linked List) (3)
마찬가지로 앞서 알아본 링크드 리스트(Linked List)에 대해 더 깊이 알아보겠다.
링크드 리스트의 가장 큰 단점은, 어떤 데이터를 찾든 반드시 맨 앞에 있는 노드(헤드)의 데이터를 찾아서 거기에서 주소를 가지고 원하는 데이터로 이동을 해야 한다는 것이다.
만약 노드가 10,000개이고, 내가 찾는 데이터가 8,000번째 노드에 있다고 하면, 0~9,999번까지 sorting 되어 있다고 할 때 0번부터 8,000번까지 찾아야 한다.
이에 반해 아예 맨 뒤에서부터 검색하면 상대적으로 9,999번에서 8,000번까지 찾아가는 것은 훨씬 검색량이 적어서 효율적이다. 더 빠르게 원하는 데이터를 찾을 수 있는 것이다.
그래서 나타난 것이 더블 링크드 리스트(Double Linked List)이다.
더블 링크드 리스트 (Double Linked List)
이중 연결 리스트라고도 하고, 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능하다는 장점을 지닌다.
일반적인 링크드 리스트에는 노드에 데이터와 다음 노드의 주솟값을 가지고 있는 반면, 더블 링크드 리스트는 앞에 하나를 더 추가해서 해당 노드의 앞 노드의 주소를 저장하는 공간을 마련했다. 그래서 'double linked list'이다.
즉, 기존 링크드 리스트의 단점인 '항상 앞에서부터 검색을 해야 한다'는 것을 보완하는 것이다.
더블 링크드 리스트를 코드로 구현해보면,
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head # 처음에 노드가 하나라면 head나 tail이나 해당 노드를 가리키고 있기 때문
def insert(self, data): # 특정 데이터를 더블 링크드 리스트의 맨 뒤에 추가하는 함수
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node # 더블 링크드 리스트의 조건을 충족하기 위해 새로운 노드가 직전 노드를 가리키게 한다.
self.tail = new
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
이렇게 된다. 기존의 링크드 리스트와는 달리 next만 있는 것이 아니라 prev가 있고, head만 있는 것이 아니라 tail이 있다. 앞뒤로 서로 연결하기 위함이다.
머리(head)에서부터 탐색, 꼬리(tail)에서부터 탐색을 코드로 구현하면 다음과 같다.
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
def search_from_head(self, data): # head에서부터 탐색
if self.head == None: # 노드가 존재하지 않는 경우
return False
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
return False
def search_from_tail(self, data): # tail에서부터 탐색
if self.head == None: # 노드가 존재하지 않는 경우
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
이렇게 된다. 인스턴스를 한 번 생성해보고 탐색을 실행해보면,
doubleLinkedList1 = NodeMgmt(0)
for i in range(1, 10):
doubleLinkedList1.insert(i)
searchHead = doubleLinkedList1.search_from_head(100)
print(searchHead)
searchTail = doubleLinkedList1.search_from_tail(5)
print(searchTail)
100은 해당 더블 링크드 리스트에 존재하지 않으므로 False, 5는 해당 링크드 리스트에 존재하므로 노드의 객체가 콘솔에 표시된다.
나아가 더블 링크드 리스트의 특징을 살려서, tail에서부터 앞으로 이동하면서 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들면 다음과 같다.
def insert_before(self, data, before_data):
if self.head == None: # 노드가 비어 있을 때 새로운 데이터 그냥 노드에 추가
self.head = Node(data)
return True
else:
node = self.tail # tail에서 시작
while node.data != before_data: # 찾고자 하는 노드의 값이 안 나온다면 계속 반복문 실행
node = node.prev
if node == None: # 제일 앞(head)까지 왔는데 결국 못 찾아서 None이 된 경우
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new
return True
이렇게 된다.
한편, head에서부터 다음으로 이동하면서 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수를 만들면 다음과 같다.
def insert_after(self, data, after_data):
if self.head == None: # 노드가 비어있는 경우 그냥 데이터 추가
self.head = Node(data)
return True
else:
node = self.head # head에서부터 시작
while node.data != after_data: # 찾고자 하는 노드 안 나오면 계속 반복문 실행
node = node.next
if node == None:
return False
new = Node(data)
after_new = node.next
new.next = after_new
new.prev = node
node.next = new
if new.next == None: # tail 값 재지정
self.tail = new
return True
결국, insert_before, insert_after 함수 두 개를 모두 합친 NodeMgmt 클래스를 정리하자면,
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def search_from_head(self, data):
if self.head == None:
return False
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
return False
def search_from_tail(self, data):
if self.head == None:
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
def insert_before(self, data, before_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new
return True
def insert_after(self, data, after_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.head
while node.data != after_data:
node = node.next
if node == None:
return False
new = Node(data)
after_new = node.next
new.next = after_new
new.prev = node
node.next = new
if new.next == None:
self.tail = new
return True
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
이렇게 된다.
insert_before 함수를 한 번 실행해보면, 가령 데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가한다고 할 때,
doubleLinkedList1 = NodeMgmt(0)
for i in range(1, 10):
doubleLinkedList1.insert(i)
node3 = doubleLinkedList1.insert_before(1.5, 2)
doubleLinkedList1.desc()
이렇게 잘 출력되는 것을 알 수 있다.
[참고자료]
패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료