Double-LinkedList
는 앞 뒤로 움직일 수 있는 리스트를 말함
일반적으로 head
를 이용해 한 방향으로 밖에 이동할 수 없는 LinkedList
와는 대조적임
양방향
으로 이동하기 위해서는 왼쪽에는 Prev
가, 오른쪽에는 Next
가 있어야 하고, head
뿐 아니라, tail
도 있어야함
class Node:
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
기존의 LinkedList
에서 prev
를 추가한 Node
클래스를 작성
class DoubleLinkedList:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head #tail과 head가 동일한 노드를 가리키도록 함
위처럼 해주는 이유는 처음에 생성된 Node
는 처음이기도 하고 끝이기도 하기 때문
여기서 Node
가 많이 삽입될수록, tail
은 점점 그 Node
를 따라가고, head
는 맨 앞의 자기 자리를 지키기 때문에 값의 변경이 없음
아래 메소드들을 DoubleLinkedList
클래스 코드 안에 추가
def add_last(self, data):
new = Node(data)
new.prev = self.tail
self.tail.next = new
self.tail = new
def add_first(self, data):
new = Node(data)
new.next = self.head
self.head.prev = new
self.head = new
기본적인 틀은 그냥 LinkedList
와 매우 비슷함
기존의 node
와 새롭게 추가되는 new
의 next, prev
를 적절히 잘 연결시켜주지 않으면 delete
같은 메소드에 문제가 발생함
그걸 쉽게 도와주는게 바로 head, tail
이니 적절히 활용
def delete(self, data):
if self.head == '':
return False
if self.head.data == data:
temp = self.head
self.head = self.head.next
del temp
node = self.head
while node.next:
if node.next.data == data:
temp = node.next
node.next = node.next.next
node.next.prev = node
del temp
return True:
node = node.next
return False
delete
까지 구현하면 삽입 삭제가 전부 가능해짐
하지만 애초에 Double-LinkedList
구현 목적은 양방향의 이동을 활용하는 점인데 아직 그게 등장하지 않았음
먼저 데이터를 정방향 그리고 역방향으로 출력하는 메소드
def display(self):
node = self.head
while node:
print(node.data)
node = node.next
def display_reverse(self):
node = self.tail
while node:
print(node)
node = node.prev
데이터를 앞에서부터 N번째 인덱스에 해당하는 Node
뒤에 데이터를 추가하는 방법
def getLength(self):
node = self.head
count = 0
while node:
node = node.next
count += 1
return count
먼저 연결리스트의 길이를 구하는 메소드 정의
위 방식처럼해도 되고 add
할 때마다 count
를 올려도 됨
def insert_front(self, n, data):
if n == 0:
add_first(data)
return True
elif n == self.getLength()-1:
add_last(data)
return True
else:
node = self.head.next
count = 1
while node.next and count < n:
count += 1
node = node.next
if count < n:
return False
new = Node(data)
new.next = node.next
node.next.prev = new
node.next = new
new.prev = node
return True
상) 앞에서 N번째 인덱스 뒤에 data를 삽입하는 메소드
하) 뒤에서 N번째 인덱스 앞에 data를 삽입하는 메소드
def insert_back(self, n, data):
if n == 0:
add_last(data)
return True
elif n == self.getLength()-1:
add_first(data)
return True
else:
node = self.tail.prev
count = 1
while node.prev and count < n:
count += 1
node = node.prev
if count < n:
return False
new = Node(data)
new.prev = node.prev
node.prev.next = new
node.prev = new
new.next = node
return True