이중 연결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다
단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다
단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다
이중 연결리스트는 단순 연결리스트와 다르게 이전 노드에 접근이 가능하다는 장점이 있다
이전 노드에 접근할 수 있다는 말은 특정 노드 이전의 값을 삭제하거나 역으로 출력하는 등 추가적인 연산이 가능하다
구현하려는 이중 연결리스트의 추상 데이터 타입은 다음과 같다
- empty(): 리스트가 비었다면 True, 아닐 경우 False를 반환
- append(data): 리스트의 맨 뒤에 data를 추가
- appendleft(data): 리스트의 처음에 data를 추가
- insert_before(next_data, new_data): next_data 앞에 new_data를 추가
- insert_after(prev_data, new_data): prev_data 뒤에 new_data를 추가
- pop(): 리스트의 맨 뒤의 data를 반환, 반환할 값이 없는 경우 IndexError 발생
- popleft(): 리스트의 맨 처음 data를 반환, 반환할 값이 없는 경우 IndexError 발생
- __str__(): 출력 함수
- __len__(): 크기 반환 함수
1. 노드
단순 연결리스트와 마찬가지로 이중 연결리스트를 구현하기에 앞서 노드를 구현해보자
class Node(object):
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.next = next
self.data = data
노드는 이전 값을 나타내는 prev와 다음 값을 나타내는 next를 갖는다
2. 연결리스트
class DoubleLinkedList(object):
def __init__(self):
self.head = None
self.tail = self.head
이중 연결리스트는 연결리스트의 시작을 나타내는 head와 끝을 나타내는 tail을 갖는다
head는 리스트의 첫 번째 원소를, tail은 리스트의 마지막 원소를 나타낸다
1) empty()
def empty(self):
return not bool(self.head)
head가 None이 아닌 값을 갖는 경우 False를, None을 갖는 경우 True를 반환한다
2) append(data)
def append(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
node = self.tail
new_node = Node(data, prev=node)
node.next = new_node
self.tail = new_node
head에 노드가 없는 경우 새로운 노드를 만들고 만들어진 노드가 리스트의 head가 된다
이미 head가 있는 경우 리스트의 마지막에 값을 추가한다
기존 리스트의 마지막 값(self.tail)의 next가 new_node를 가리키게 하고 new_node의 prev가 기존 리스트의 마지막 값을 가리키도록 한다
3) appendleft(data)
def appendleft(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
new_node = Node(data, next=node)
node.prev = new_node
self.head = new_node
head에 노드가 없는 경우 새로운 노드를 만들고 만들어진 노드가 리스트의 head가 된다
이미 head가 있는 경우 리스트의 처음에 값을 추가한다
기존 head의 prev가 new_node를 가리키게 하고 new_node의 next가 기존 리스트의 첫 번째 값을 가리키게 한다
4) insert_before(next_data, new_data)
def insert_before(self, next_data, new_data):
if self.head is None:
self.head = Node(new_data)
self.tail = self.head
else:
node = self.tail
while node.data != next_data:
node = node.prev
if node is None:
return False
prev_node = node.prev
new_node = Node(new_data, prev=prev_node, next=node)
if prev_node:
prev_node.next = new_node
else:
self.head = new_node
node.prev = new_node
return True
- 이중 연결리스트를 사용하면 이전 노드의 값을 참조할 수 있기 때문에 특정 노드 이전에 노드를 추가할 수 있다
- 단순 연결리스트를 사용해도 다음 노드가 가리키는 값을 먼저 참조해 특정 노드 이전에 노드를 추가할 수 있지만 이중 연결리스트를 사용하면 훨씬 자연스럽게 구현할 수 있다
- 위에 append, appendleft 메소드처럼 head가 없는 경우 새로 삽입하는 노드가 리스트의 head가 된다
- 리스트를 역으로 순회하며 찾으려는 값(next_data)을 찾고, next_data를 찾았다면 next_data를 포함한 노드의 prev가 새로운 값을 포함하는 노드(new_node)를 가리키도록하고 new_node의 next가 next_data를 포함한 노드(next_node)를 가리키도록 한다
5) insert_after(prev_data, new_data)
def insert_after(self, prev_data, new_data):
if self.head is None:
self.head = Node(new_data)
self.tail = self.head
else:
node = self.head
while node.data != prev_data:
node = node.next
if node is None:
return False
next_node = node.next
new_node = Node(new_data, prev=node, next=next_node)
if next_node:
next_node.prev = node
else:
self.tail = new_node
node.next = new_node
- head가 없는 경우 새로 삽입하는 노드가 리스트의 head가 된다
- head에서부터 리스트를 순회하면서 before_data를 찾는다면 다음 노드에 새로운 데이터를 추가한다
- prev_data를 찾았다면 prev_data를 포함한 노드의 next가 새로운 노드(new_node)를 가리키도록하고 new_node의 prev가 prev_data를 포함한 노드(prev_node)를 가리키도록 한다
6) pop()
def pop(self):
if self.head is None:
raise IndexError('LinkedList is empty')
item = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return item
리스트의 마지막 값을 반환한다, 리스트가 비었을 경우 IndexError를 일으킨다
7) popleft()
def popleft(self):
if self.head is None:
raise IndexError('LinkedList is empty')
item = self.head.data
self.head = self.head.next
self.head.prev = None
return item
리스트의 첫번째 값을 반환한다, 리스트가 비었을 경우 IndexError를 일으킨다
8) __str__()
def __str__(self):
node = self.head
result = ""
while node is not None:
result = result + str(node.data) + " "
node = node.next
return result
출력함수로 리스트의 저장된 값을 string으로 받아 result에 저장한다
string 타입인 result를 반환한다
9) __len__()
def __len__(self):
node = self.head
cnt = 0
while node is not None:
cnt += 1
node = node.next
return cnt
리스트의 길이를 반환하는 함수로, 리스트를 순환하면서 노드 당 cnt값을 하나씩 증가시키고 cnt값을 반환한다
3. 예제코드
if __name__ == '__main__':
DL = DoubleLinkedList()
DL.append(1); DL.append(3); DL.append(5); print(DL)
DL.appendleft(100); print(DL)
DL.insert_after(1, 2); print(DL)
DL.insert_before(5, 4); print(DL); print(len(DL))
DL.pop(); print(DL)
DL.popleft(); print(DL)
print(len(DL))
1 3 5
100 1 3 5
100 1 2 3 5
100 1 2 3 4 5
6
100 1 2 3 4
1 2 3 4
4
4. 전체코드
class Node(object):
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.next = next
self.data = data
class DoubleLinkedList(object):
def __init__(self):
self.head = None
self.tail = self.head
def empty(self):
return not bool(self.head)
def append(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
node = self.tail
new_node = Node(data, prev=node)
node.next = new_node
self.tail = new_node
def appendleft(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
new_node = Node(data, next=node)
node.prev = new_node
self.head = new_node
def insert_before(self, next_data, new_data):
if self.head is None:
self.head = Node(new_data)
self.tail = self.head
else:
node = self.tail
while node.data != next_data:
node = node.prev
if node is None:
return False
prev_node = node.prev
new_node = Node(new_data, prev=prev_node, next=node)
if prev_node:
prev_node.next = new_node
else:
self.head = new_node
node.prev = new_node
return True
def insert_after(self, prev_data, new_data):
if self.head is None:
self.head = Node(new_data)
self.tail = self.head
else:
node = self.head
while node.data != prev_data:
node = node.next
if node is None:
return False
next_node = node.next
new_node = Node(new_data, prev=node, next=next_node)
if next_node:
next_node.prev = node
else:
self.tail = new_node
node.next = new_node
def pop(self):
if self.head is None:
raise IndexError('LinkedList is empty')
item = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return item
def popleft(self):
if self.head is None:
raise IndexError('LinkedList is empty')
item = self.head.data
self.head = self.head.next
self.head.prev = None
return item
def __str__(self):
node = self.head
result = ""
while node is not None:
result = result + str(node.data) + " "
node = node.next
return result
def __len__(self):
node = self.head
cnt = 0
while node is not None:
cnt += 1
node = node.next
return cnt
if __name__ == '__main__':
DL = DoubleLinkedList()
DL.append(1); DL.append(3); DL.append(5); print(DL)
DL.appendleft(100); print(DL)
DL.insert_after(1, 2); print(DL)
DL.insert_before(5, 4); print(DL); print(len(DL))
DL.pop(); print(DL)
DL.popleft(); print(DL)
print(len(DL))
'CS > 자료구조' 카테고리의 다른 글
[자료구조] 트리(Tree) (5) | 2021.04.24 |
---|---|
[Python] 큐 구현 (0) | 2021.04.24 |
[자료구조] 큐 (Queue) (0) | 2021.04.17 |
[Python] 스택 구현 (0) | 2020.10.24 |
[자료구조] 스택 (Stack) (0) | 2020.10.23 |