链表

Python的list类是高度优化的，并且通常是考虑存储问题时很好的选择。除此之外，list类也有一些明显的缺点。
1）一个动态数组的长度可能超过实际存储数组元素所需的长度。
2）在实时系统中对操作的摊销边界是不可接受的。
3“）在一个数组内部执行插入和删除操作的代价太高。
在本篇文章，我们介绍一个名为链表的数据结构，它为基于数组的序列提供了另一种选择。一个链表依赖于更多的分布式表示法，采用称作节点的轻量级对象，分配给每一个元素。每个节点维护一个指向它的元素的引用，并含一个或多个指向相邻节点的引用，这样做的目的是为了集中地表示序列的线性顺序。

单向链表

单向链表最简单的实现形式就是由多个系欸单的集合共同构成一个线性序列，每个节点存储一个对象的引用。
每个节点被表示为唯一的对象，该对象实例存储着指向其元素成员的引用和指向下一个节点的引用。另一个对象用于代表整个链表。链表实例至少必须包括一个指向链表头节点地引用。

# 用单向链表实现栈
from queue import Empty


class LinkedStack:
    class _Node:
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next
            
    def __init__(self):
        self._head = None
        self._size = 0
        
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0
    
    def push(self,e):
        self._head = self._Node(e,self._head)
        self.size += 1
        
    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        
        return self._head._element
    
    def pop(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        return answer

# 用单向链表实现队列

class LinkedQueue:
   class _Node:
       __slots__ = '_element', '_next'

       def __init__(self, element, next):
           self._element = element
           self._next = next
   
   def __init__(self):
       self._head = None
       self._tail = None
       self.__size = 0
       
   def __len__(self):
       return self.__size
   
   def is_empty(self):
       return self.__size == 0
   
   def first(self):
       if self.is_empty():
           raise Empty('Stack is empty')
       
       return self._head._element
   
   def dequeue(self):
       if self.is_empty():
           raise Empty('Stack is empty')
       answer = self._head._element
       self._head = self._head._next
       self._size -= 1
       if self.is_empty():
           self._tail = None
       return answer
   
   def enqueue(self,e):
       newest = self._Node(e,None)
       if self.is_empty():
           self._head = newest
       else:
           self._tail._next = newest
       self._tail = newest
       self._size += 1
   ```
### 循环链表
在链表中，我们可以使链表的尾部节点地"next"指针指向链表的头部，由此来获得一个更切实际的循环链表的概念，我们称这种表结构为循环链表。
### 双向链表
在使用哨兵时，实现方法的关键是要记住双端队列的第一个元素并不存储在头节点，而是存储在头节点后的第一个节点，同样，尾节点之前的一个节点中存储的是双端队列的最后一个元素。
### 位置列表的抽象数据类型
我们希望能够设计一个抽象数据类型为用户提供一种可以定位到序列中任何元素的方法，并且能够执行任意的插入和删除操作。
链表结构的好处之一是：只要给出列表相关节点的引用，它可以实现在列表的任意位置执行插入和删除操作的时间复杂度都是O(1)。
为了给具有标识元素位置能力的元素序列提供一般化抽象，我们定义了一个含位置信息的列表ADT以及一个更简单的位置抽象数据类型，来描述列表中的某个位置。