概念
单链表只有一个方向的链接，只能做一个方向的扫描和逐步操作，即使增加了尾结点引用，也只能支持O(1)时间的首端元素插入/删除和尾端加入。如果希望两端插入和删除操作都能高效完，就必须修改结点的基本设计，加入另一方向的链接，这样就得到双向链接表，简称双链表。
为了支持首尾两端的高效 操作，双链表应该采用如图所示的结构，包含一个尾结点引用域
双链表结点操作：
p.prev.next = p.next
p.next.prev = p.prev
双链表类
class LNode(): def __init__(self, elem, next_=None): self.elem = elem self.next = next_ class DLNode(LNode): def __init__(self, elem, prev=None, next_=None): LNode.__init__(self, elem, next_) self.prev = prev class DLList(LList): def __init__(self): LList.l__init__(self) def prepend(self,elem): p = DLNode(elem,None,self._head) if self._head is None: self._head = p else: p.next.prev = p self._head = p def append(self, elem): p = DLNode(elem, self._rear, None) if self._head is None: self._head = p else: p.prev.next = p self._rear = p def pop(self): if self._head is None: raise LinkedListUnderflow("in pop of DLList") e = self._head.elem self._head = self._head.next if self._head is not None: self._head.prev = None return e def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last") e = self._rear.elem self._rear = self._rear.prev if self._rear is None: self._head = None else: self._rear.next = None return e
循环双链表
双链表也可以定义为循环链表，也就是说，让表尾结点next域指向表的首结点，而让表首结点的prev域指向尾结点，如图所示
由于这种表里存在双向链接，无论是掌握着表的首结点还是尾结点，都能高效首先首尾端的元素加入/删除操作（O(1)复杂度)
原文：https://www.cnblogs.com/moleo/p/13433706.html