class Node(object):
def __init__(self,value=None,prev=None,next=None):
self.value,self.prev,self.next = value,prev,next
class DoubleLinkedList(object):
def __init__(self,maxsieze=None):
self.maxsieze=maxsieze
node = Node()
node.next,node.prev = node,node
self.root = node
self.length = 0
def __len__(self):
return self.length
def headnode(self):
return self.root.next
def tailnode(self):
return self.root.prev
def append(self,value):
if self.maxsieze is not None and len(self) > self.maxsieze:
raise Exception("List is Full")
node = Node(value=value)
tailnode = self.tailnode()
tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node #互指
self.length += 1
def appendleft(self,value):
if self.maxsieze is not None and len(self) > self.maxsieze:
raise Exception("List is Full")
node = Node(value=value)
if self.root.next is self.root: #如果链表为空
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1
def remove(self,node): #删除为O(1) 所以删除节点而不是值
if node is self.root:
return
else:
node.prev.next = node.next
node.next.prev = node.prev
self.length -= 1
return node
def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root:
yield curnode
curnode = curnode.next
yield curnode
def __iter__(self):
for node in self.iter_node():
yield node.value
def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode
class FullError(Exception):
pass
class EmptyError(Exception):
pass
class Deque(DoubleLinkedList):
def __init__(self,maxsieze=None):
self.maxsieze = maxsieze
def pop(self,node):
tailnode = self.tailnode()
self.remove(tailnode)
def popleft(self,node):
headnode = self.headnode()
self.remove(headnode)
def testdeque():
dq = Deque()
dq.append(0)
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)
assert list(dq) == [0,1,2,3,4,5]