前情提要：Python数据结构与算法_8_链表、无序链表
前情提要：Python数据结构与算法_9_有序链表
什么是双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。——《百度百科对于双向链表的解释》
双向链表是在单向链表的基础上扩展而成的更为复杂的数据结构，双向链表其中的每个节点除了含有自身数据元素之外，还含有两个链接（以prev与next为例），分别指向它的上一个节点与下一个节点。
- prev 链接指向前一个节点，当此节点为第一个节点时，则 prev 链接指向None。
- next 链接指向下一个节点，当此节点为最后一个节点时，则 next 链接指向None。
图例则如下所示：
双向链表适用于需要双向查找节点值的场景中，在数据量难以估计并且数据增删操作频繁的场景中，双向链表有一定优势；链表在内存中呈现的状态是离散的地址块，不需要像列表一样预先分配连续的内存空间，在内存的充分利用上更胜一筹，不过增加了一些额外开销。
双向链表的实现
首先需要构造节点，由于引入了前驱和后继两个指针，所以节点相比单链表也发生了变化，实现代码如下。
class DNode:
def __init__(self, initdata):
self.data = initdata
self.prev = None
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def getPrev(self):
return self.prev
def set Data(self, newdata):
self.data = new data
def setNext(self, newnext):
self.next = newnext
def setPrev(self, newprev):
self.prev = newprev
然后我们实现双向链表的构造方法，仍然是链表头指向None，代码如下：
class DLinkList:
def __init__(self):
self.head = None
下面我们来实现双向链表的三个基本方法，即判断链表是否为空（isEmpty()），以及得到链表长度（节点个数）（length()），还有搜索链表中的元素（search()）。双向链表的这三个基本方法与单链表是相同的，并没有发生变化。
class DLinkList:
def isEmpty(self):
return self.head == None
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
实现 add 方法，链表头部插入节点：
class DLinkList:
def add(self, item):
temp = DNode(item)
if self.head == None:
self.head = Node
else:
temp.setNext(self.head)
self.head.setPrev(temp)
self.head = temp
实现 append 方法，链表尾部插入节点：
class DLinkList:
def append(self, item):
temp = DNode(item)
if self.head == None:
self.head = Node
else:
current = self.head
while current.getNext() != None:
current = current.getNext()
current.setNext(temp)
temp.setPrev(current)
实现 insert 方法，链表指定位置插入节点：
class DLinkList:
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
temp = Node(item)
current = self.head
count = 0
# 移动到指定位置的前一个位置 因为实际控制的是指定位置的上一个节点
while count < (pos-1):
count = count + 1
current = current.getNext()
# 将temp的prev 指向当前节点
temp.setPrev(current)
# 将temp的next 指向当前节点的下一个节点
temp.setNext(current.getNext())
# 将当前节点的下一个节点的prev 指向temp
current.getNext().setPrev(temp)
# 将当前节点的next 指向temp
current.setNext(temp)
insert 方法过程图示如下：
实现 remove 方法，移除链表中的某个节点：
class DLinkList:
def remove(self, item):
if self.head == None:
return False
else:
current = self.head
# 如果首节点的元素即是要删除的元素
if current.getData() == item:
# 如果链表只有这一个节点
if current.getNext() == None:
self.head = None
else:
# 将第二个节点的prev设置为None
current.getNext().setPrev(None)
# 将链表头head指向第二个节点
self.head = current.getNext()
return True
# 循环遍历寻找目标节点
while current != None:
# 寻找到目标节点
if current.getData() == item:
# 将当前节点的前一个节点的next 指向 当前节点的后一个节点
current.getPrev().setNext(current.getNext())
# 将当前节点的后一个节点的prev 指向 当前节点的前一个节点
current.getNext().setPrev(current.getPrev())
return True
current = current.getNext()
return False