지난 시간에는 단순연결리스트를 만들어보았습니다.
이번에는 연결이 이중으로 된 이중연결리스트를 만들어보겠습니다.
이중연결리스트의 노드는 자신을 기준으로 다음에 있는 노드가 next 노드, 이전을 prev 노드라고 하겠습니다.
이를 그림으로 그려보면 다음과 같습니다.
head node와 tail node 부분을 보면 None이 있는데 head node의 이전이 없어서 None이며, tail node도 다음이 없어서 None으로 표시한 것입니다.
각 노드를 보면 data와 next, prev 총 3가지 속성이 있는 것을 알 수 있습니다. 그래서 Node class에는 3개의 인스턴스 변수가 들어가게 됩니다. 코드로 알아보면 다음과 같습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 노드의 reference
self.prev = None # 이전 노드의 reference
이중연결리스트의 인스턴스 변수를 정하겠습니다. head 노드, tail 노드, 노드의 개수 총 3개로 정하겠습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 노드의 reference
self.prev = None # 이전 노드의 reference
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
오늘 작성해볼 코드는 추가 연산과 탐색 연산입니다.
추가 연산은 연결리스트 맨 뒤에 계속 추가하는 것입니다. 그림으로 알아보면 다음과 같습니다.
연결리스트에 추가 할 때 두 가지의 경우를 알아볼 수 있습니다.
1. 연결리스트에 아무것도 없는 경우
2. 연결리스트에 한 개 이상의 노드가 있는 경우
1번의 경우 연결리스트에 아무것도 없음을 파악할 수 있어야 합니다. count 인스턴스 변수를 통해서 해결이 가능합니다.
나머지 2번의 경우는 일반적인 경우이므로 tail 뒤에 이어붙여줍니다.
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def append(self, val):
"""연결리스트에 추가하는 연산"""
new_node = Node(val) # 일딴 노드를 만들어야 하니까 새로 생성해준다.
if self.count == 0: # 0이라는 말은 연결리스트가 비어있다는 의미!
self.head = new_node
self.tail = new_node
else: # 그 외에는 일반적인 경우
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.count += 1 # 노드가 늘어났으니까 1개 더해준다.연결리스트는 실제로 그림을 그리면서 공부하면 도움이 될 것입니다.
이번에는 탐색 연산입니다. 리스트의 인덱스 번호처럼 내가 원하는 부분을 이야기하면 그 부분에 대해서 알려주는 것입니다.
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def append(self, val):
"""연결리스트에 추가하는 연산"""
new_node = Node(val) # 일딴 노드를 만들어야 하니까 새로 생성해준다.
if self.count == 0: # 0이라는 말은 연결리스트가 비어있다는 의미!
self.head = new_node
self.tail = new_node
else: # 그 외에는 일반적인 경우
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.count += 1 # 노드가 늘어났으니까 1개 더해준다.
def find(self, index):
"""연결리스트의 원하는 노드를 찾아준다."""
i = self.head
for _ in range(index):
i = i.next
return i.data
추가로 이중연결리스트를 한 번에 볼 수 있도록 __str__ 메소드도 만들어주겠습니다.
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def append(self, val):
"""연결리스트에 추가하는 연산"""
new_node = Node(val) # 일딴 노드를 만들어야 하니까 새로 생성해준다.
if self.count == 0: # 0이라는 말은 연결리스트가 비어있다는 의미!
self.head = new_node
self.tail = new_node
else: # 그 외에는 일반적인 경우
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.count += 1 # 노드가 늘어났으니까 1개 더해준다.
def find(self, index):
"""연결리스트의 원하는 노드를 찾아준다."""
i = self.head
for _ in range(index):
i = i.next
return i.data
def __str__(self):
i = self.head
result = str(i.data)
for _ in range(self.count - 1):
i = i.next
result += " <-> " + str(i.data)
return result이렇게 간단히 추가 연산과 탐색 연산을 만들어보았습니다.
각각의 시간복잡도를 알아보면
추가 연산의 경우 tail뒤에 계속 추가하므로 O(1)이라 할 수 있고
탐색의 경우 맨 앞을 탐색할 경우 O(1), 일반적인 경우 O(n)의 시간이 걸린다고 할 수 있습니다.
끝으로 전체 코드입니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 노드의 reference
self.prev = None # 이전 노드의 reference
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def append(self, val):
"""연결리스트에 추가하는 연산"""
new_node = Node(val) # 일딴 노드를 만들어야 하니까 새로 생성해준다.
if self.count == 0: # 0이라는 말은 연결리스트가 비어있다는 의미!
self.head = new_node
self.tail = new_node
else: # 그 외에는 일반적인 경우
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.count += 1 # 노드가 늘어났으니까 1개 더해준다.
def find(self, index):
"""연결리스트의 원하는 노드를 찾아준다."""
i = self.head
for _ in range(index):
i = i.next
return i.data
def __str__(self):
i = self.head
result = str(i.data)
for _ in range(self.count - 1):
i = i.next
result += " <-> " + str(i.data)
return result
test = DoublyLinkedList()
test.append(1)
test.append(2)
test.append(3)
test.append(4)
print(test.find(3))
print(test)
댓글