python LinkedDeque,PositionalList的实现

首先是双链表。

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