# 노드 구조 확장
class Node:
def __init__(self, item):
self.data = item
self.next = None
self.prev = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def traverse(self):
result = []
curr = self.head
while curr.next.next: # self.tail 에 dummy node를 놓으므로
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount + 1:
raise IndexError
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while pos > i:
curr = curr.next
i += 1
return curr
def insertBefore(self, next, newNode):
prev = next.prev
newNode.prev = prev
prev.next = newNode
newNode.next = next
next.prev = newNode
self.nodeCount += 1
return True
def insertAfter(self, prev, newNode):
next = prev.next
prev.next = newNode
newNode.prev = prev
next.prev = newNode
newNode.next = next
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = getAt(pos-1)
return insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
prev.next = curr.next
curr.next.prev = prev
self.nodeCount -= 1
return curr.data
def popBefore(self, next):
prev = next.prev
prev.prev.next = next
next.prev = prev.prev
self.nodeCount -= 1
return prev.data
def popAt(self, pos):
if pos < 0 or pos > self.nodeCount:
raise IndexError
if self.nodeCount == 0:
raise IndexError
prev = self.getAt(pos-1)
return self.popAfter(prev)
