python LinkedDeque,PositionalList的实现

Q132284591

首先是双链表。

• class _DoublyLinkedBase:
  
  
•     #A base class providing a doubly llinked list representation
  
• 
  
•     class _Node:
  
•         #nonpublic class for storing a doubly linked node
  
•         __slots__='_element','_prev','_next'
  
• 
  
•         def __init__(self,element,prev,next):
  
•             self._element=element
  
•             self._prev=prev
  
•             self._next=next
  
• 
  
• #----------------------------------------------------------------
  
•     def __init__(self):
  
•         #create an empty list
  
•         self._header=self._Node(None,None,None)
  
•         self._trailer=self._Node(None,None,None)
  
•         self._header._next=self._trailer
  
•         self._trailer._prev=self._header
  
•         self._size=0
  
• 
  
•     def __len__(self):
  
•         return self._size
  
• 
  
•     def is_empty(self):
  
•         return self._size==0
  
• 
  
•     def _insert_between(self,e,predecessor,successor):
  
•         newest=self._Node(e,predecessor,successor)
  
•         predecessor._next=newest
  
•         successor._prev=newest
  
•         self._size+=1
  
•         return newest
  
• 
  
•     def _delete_node(self,node):
  
•         #Delete nonsentinel node from the list and return its element
  
•         predecessor=node._prev
  
•         successor=node._next
  
•         predecessor._next=successor
  
•         successor._prev=predecessor
  
•         self._size-=1
  
•         element=node._element
  
•         node._prev=node._next=node._element=None
  
•         return element
  

linkedQueue

• class LinkedDeque(_DoublyLinkedBase):
  
  
•     #Double-ended queue implementation
  
• 
  
•     def first(self):
  
•         #return but not remove the element at the front
  
•         if self.is_empty():
  
•             raise Exception('Deque is empty')
  
•         return self._header._next._element          #real item after header
  
• 
  
•     def last(self):
  
•         if self.is_empty():
  
•             raise Exception('Deque is empty')
  
•         return self._trailer._prev._element         #real item before trailer
  
• 
  
•     def insert_first(self,e):
  
•         #Add an element to the front of the deque
  
•         self._insert_between(e,self._header,self._head._next) #after header
  
• 
  
•     def insert_last(self,e):
  
•         #Add an element to the back of the deque
  
•         self._insert_between(e,self._trailer._prev,self._trailer) #before trailer
  
• 
  
•     def delete_first(self):
  
•         #remove and return the element from the front of the deque
  
•         if self.is_empty():
  
•             raise Exception('Deque is empty')
  
•         return self._delete_node(self._header._next) #use inherited method
  
• 
  
•     def delete_last(self):
  
•         #remove and return the element from the back of the deque
  
• 
  
•         if self.is_empty():
  
•             raise Exception('Deque is empty')
  
•         return self._delete_node(self._trailer._prev)
  

PositionalList

• class PositionalList(_DoublyLinkedBase):
  
  
•     #A sequential container of elements allowing positional access
  
• 
  
•     class Position:
  
•         #An abstraction representing the location of a single element
  
• 
  
•         def __init__(self,container,node):
  
•             #constructor should not be invoked by user
  
•             self._container=container
  
•             self._node=node
  
• 
  
•         def element(self):
  
•             #return the element stored at this position
  
•             return self._node._element
  
• 
  
•         def __eq__(self,other):
  
•             #return true if other is a Position representing the same location
  
•             return type(other) is type(self) and other._node is self._node
  
• 
  
•         def __ne__(self,other):
  
•             #return True if other does not represent the same location
  
•             return not(self==other)
  
• #----------------------------------------------------------------------
  
• 
  
•     def _validate(self,p):
  
•         #Return position's node, or raise appropriate error if invalid
  
•         if not isinstance(p,self.Position):
  
•             raise TypeError(\'P must be proper Position type\')
  
•         if p._container is not self:
  
•             raise ValueError(\'P does not belong to this container\')
  
•         if p._node._next is None:
  
•             raise ValueError(\'p is not longer valid\')
  
•         return p._node
  
• 
  
• 
  
•     def _make_position(self,node):
  
•         #return position instance for given node (or None if sentinel)
  
•         if node is self._header or node is self._trailer:
  
•             return None
  
•         else:
  
•             return self.Position(self,node)
  
• 
  
•     #accessors
  
•     def first(self):
  
•         #return the first position in the list (or None if list is empty)
  
•         return self._make_position(self._header._next)
  
• 
  
•     def last(self):
  
•         #return the last position in the list(or None if list is empty)
  
•         return self._make_position(self._tailer._prev)
  
• 
  
•     def before(self,p):
  
•         #return the Position just before Position p(or None if p is first)
  
•         node=self._validate(p)
  
•         return self._make_position(node._prev)
  
• 
  
•     def after(self,p):
  
•         #return the Positoin just after Position p(or None if p is last)
  
•         node=self._validate(p)
  
•         return self._make_position(node._next)
  
• 
  
•     def __iter__(self):
  
•         #generate a forward iteration of the elements of the list
  
•         cursor=self.first()
  
•         while cursor is not None:
  
•             yield cursor.element()
  
•             cursor=self.after(cursor)
  
• 
  
•     #override inherited version to return Positions,rather than Node
  
•     def _insert_between(self,e,predecessor,successor):
  
•         #Add element between existing nodes and return new Position
  
•         node=super()._insert_between(e,predecessor,successor)
  
•         return self._make_position(node)
  
• 
  
•     def add_first(self,e):
  
•         #insert element e at the front of the list and return the position
  
•         return self._insert_between(e,self._header,self._header._next)
  
• 
  
•     def add_last(self,e):
  
•         #insert element e at the back of the list and return new position
  
•         return self._insert_between(e,self._trailer._prev,self._trailer)
  
• 
  
•     def add_before(self,p,e):
  
•         #insert element e into list before Position p and return new Position
  
•         original=self._validate(p)
  
•         return self._insert_between(e,original._prev,original)
  
• 
  
•     def add_after(self,p,e):
  
•         original=self._validate(p)
  
•         return self._insert_between(e,original,original._next)
  
• 
  
•     def delete(self,p):
  
•         #remove and return the element at position p
  
•         original=self._validate(p)
  
•         return self._delete_node(original)
  
• 
  
•     def replace(self,p,e):
  
•         #replace the element at position p with e
  
•         #return the element formerly at position p
  
•         original=self._validate(p)
  
•         old_value=original._element
  
•         original._element=e
  
•         return old_value