Double Linked List
Linked List란 파이썬의 리스트 처럼 순서대로 값이 나열된 것이 아닌, 각각의 요소가 다음 요소의 위치를 가르키는 포인터를 가지는 자료구조 형태이다.
Linked List에는 Single Linked List와 Double Linked List가 있다.
- Single Linked List
- Double Linked List
Single Linked List
Single Linked List는 다음 위치를 가르키는 포인터만 존재한다.
그러므로 앞에는 어떤 요소가 있는지 알지만, 자신의 뒤로는 어떤 요소가 있는지 알지 못한다.
한쪽 방향으로만 연결된 형태이다.
Double Linked List
Double Linked List는 다음 위치를 가르키는 포인터와 이전 위치를 가르키는 포인터가 있다.
그러므로 양쪽 방향으로 연결된 자료 형태이다.
Double Linked List 구현하기
# 각각의 요소는 Node라는 하나의 덩어리로 존재한다.
# 클래스로서 정의해서 사용한다.
# Node에는 앞과 뒤를 가르키는 next와 pre 속성이 존재한다.
class Node:
def __init__(self, value):
self.val = value
self.next = self.pre = None
# 실제 Double linked list에 해당하는 클래스이다.
class MyLinkedList():
# 초기화시 맨앞을 나타내는 head와 맨뒤를 나타내는 tail은 데이터가 없으므로 None이 된다.
# count은 데이터가 저장될때 index를 나타내기 위해서 설정한 속성이다.
def __init__(self):
self.head = None
self.tail = None
self.count = 0
# 앞에서 부터 모든 데이터를 출력하는 함수이다.
def print_all_from_head(self):
if self.head == None:
return None
else:
# 데이터의 기준점을 잡아준다.
# 기준을 처음으로 해서 하나씩 돌면서 print한다.
# next속성을 이용해서 출력 후 다음 node로 이동시킨다.
node = self.head
while node != None:
print(node.val)
node = node.next
# 뒤에서 부터 모든 데이터를 출력하는 함수이다.
def print_all_from_tail(self):
if self.tail == None:
return None
else:
# 위의 경우와 반대로 next가 아닌 pre를 불러서 이전의 node로 이동시킨다.
node = self.tail
while node != None:
print(node.val)
node = node.pre
# 인덱스가 주어졌을 경우에 해당 인덱스에 맞는 데이터를 출력하는 함수
def get(self, index):
if self.head == None:
return -1
# 인덱스가 해당 리스트의 전체 수보다 크면 데이터는 존재하지 않는다.
# count-1을 하는 이유는 index는 총 데이터의 수 보다 1 작기 때문이다.
elif index > self.count -1:
return -1
# index에 해당하는 만큼 for문을 돌면서 해당노드에 위치하게 node의 위치를 변경시켜준다.
else:
node = self.head
for _ in range(index):
node = node.next
return node.val
# 새로운 head데이터를 만드는 함수
def addAtHead(self, val):
if self.head == None:
self.head = Node(val)
self.tail = self.head
self.count += 1
else:
# 새로운 head가 만들어지면 이전 head에 연결시켜주고, 새로운 head로 만들어주어야 한다.
# 그리고 새로운 head는 이전 head의 pre에 위치하므로 이 역시 코드로 작성해주어야 한다.
curr_head = self.head
new_head = Node(val)
new_head.next = curr_head
new_head.next.pre = new_head
self.head = new_head
self.count += 1
# 새로운 Tail데이터를 만드는 함수
# Tail에 넣는 다는 것은 맨 마지막에 데이터를 넣는다는 의미이다.
def addAtTail(self, val):
if self.head == None:
self.head = Node(val)
self.tail = self.head
self.count += 1
else:
curr_head = self.head
# 마지막 node가 있는 위치까지 node를 먼저 이동시켜 준다.
# 마지막 위치 node의 next에 새로운 Node()를 만들어준다.
# 새로운 tail이 되므로 위의 head처럼 아래의 코드를 구현해주어야 한다.
while curr_head.next != None:
curr_head = curr_head.next
curr_head.next = Node(val)
self.tail = curr_head.next
self.tail.pre = curr_head
self.count += 1
# 인덱스 위치에 새로운 데이터를 넣는 함수
def addAtIndex(self, index, val):
# 인덱스가 count보가 큰 경우라면 데이터는 넣지 못한다.
if self.head == None or self.count < index:
return None
# 인덱스와 count가 같은 경우는 새로운 Tail를 만드는 코드이다.
elif self.count == index:
curr_head = self.head
while curr_head.next != None:
curr_head = curr_head.next
curr_head.next = Node(val)
self.tail = curr_head.next
self.tail.pre = curr_head
self.count += 1
# 인덱스가 0인경우는 새로운 head를 만드는 코드이다.
elif index == 0:
curr_head = self.head
new_head = Node(val)
new_head.next = curr_head
new_head.next.pre = new_head
self.head = new_head
self.count += 1
else:
node = self.head
for _ in range(index-1):
node = node.next
temp_node = node.next
node.next = Node(val)
temp_node.pre = node.next
node.next.pre = node
node.next.next = temp_node
self.count += 1
# 인덱스에 해당하는 데이터를 삭제하는 코드이다.
def deleteAtIndex(self, index):
if self.head == None:
return None
elif index > self.count-1:
return None
elif index == 0:
node = self.head
new_head = node.next
node.next.pre = None
self.head = new_head
self.count -= 1
return "ok"
elif index == self.count -1:
node = self.tail
new_tail = node.pre
new_tail.next = None
node.pre = None
self.tail = new_tail
self.count -= 1
return "ok"
else:
node = self.head
for _ in range(index):
node = node.next
temp_pre = node.pre
temp_next = node.next
temp_pre.next = temp_next
temp_next.pre = temp_pre
self.count -= 1
return "ok"
test = MyLinkedList()
test.addAtHead(10)
test.addAtHead(20)
test.addAtHead(30)
test.addAtHead(40)
print("head부터 출력")
test.print_all_from_head()
print("tail부터 출력")
test.print_all_from_tail()
print("===========")
print(test.get(10))
# print(test.count)
# print("=============here")
# print(test.deleteAtIndex(3))
# print("=============here")
# print("head부터 출력")
# test.print_all_from_head()
# print("tail부터 출력")
# test.print_all_from_tail()
# print(test.count)