双链表结构比单链表结构更有优越性。它允许用户做如下的事情：
双链表结构的节点类的python实现，通过给provious指针添加一个字段，扩展了前面所讨论的Node类。如下是两个类的代码：
# coding: utf-8 class Node(object): def __init__(self, data, next=None): self.data = data self.next = next class TowWayNode(Node): def __init__(self, data, previous=None, next=None): Node.__init__(self, data, next) self.previous = previous
如下是测试程序，它通过在末尾添加项来创建了一个双链表结构。然后，程序从最后一个项开始朝着第一项处理，最终显示了整个链表结构的内容：
# coding: utf-8 class Node(object): def __init__(self, data, next=None): self.data = data self.next = next class TowWayNode(Node): def __init__(self, data, previous=None, next=None): Node.__init__(self, data, next) self.previous = previous head = TowWayNode(1) tail = head for data in range(2,6): tail.next = TowWayNode(data, tail) tail = tail.next probe = tail while probe != None: print probe.data probe = probe.previous
考虑一下程序的第一个循环中的如下两条语句：
tail.next = TowWayNode(data, tail)
tail = tail.next
这些语句的目的是在链表结构的末尾插入一个新的项。可以假设在链表结构中至少有一个节点，并且tail尾指针总是指向这个非空链表结构的最后一个节点。必须按照如下的顺序来设置3个指针：
下图展示了在一个双链表结构的末尾插入一个新节点的过程。
正如你所看到的，在双链表的中间插入，需要对较多的指针重定向。然而，不管目标位置在何处，需要重定向的指针数目总是常数级的。
对于双链表结构的较为通用的插入和删除也有两种情况，这和针对单链表结构的操作是相同的。可以通过借助一个带有哑头节点的循环链表结构来简化这一操作。
除了在结构的尾部插入和删除，双链表结构上的操作运行时间复杂度和单链表对应的操作是相同的。然而，双链表在的额外的指针，需要一个额外的、线性的内存使用量。
结束！
原文：https://www.cnblogs.com/aaronthon/p/13631035.html