定义
双向链表每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
优势
双向链表可以从任何一个节点访问前一个节点，也可以访问后一个节点，以至整个链表。双向查找节点时很便利，一般是在需要大批量的另外储存数据在链表中的位置的时候用。
python 实现双向链表
头部插入节点
代码实现
def add(self, value):
"""
头部插入节点
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 将node的next指向头节点
node.next = self._head
# 头结点的prev指向新节点
self._head.prev = node
# 将head指向node
self._head = node
尾部插入节点
代码实现
def append(self, value):
"""
尾插
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 移动到链表的尾端
cur = self._head
while cur.next:
cur = cur.next
# 将尾节点的next指向node
cur.next = node
# 将node的pre指向尾节点
node.prev = cur
指定位置插入节点
代码实现
def insert(self, value, index):
"""
指定位置插入
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移动到指定位置的前一个节点
while count < (index - 1):
count += 1
cur = cur.next
# 新节点pre指向上一个节点
node.prev = cur
# 新节点的next指向下一个节点
node.next = cur.next
# 下一个节点的prev指向node
cur.next.prev = node
# 上一个节点next指向新节点
cur.next = node
删除节点
代码实现
def remove(self, value):
"""
删除节点
"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == value:
# 如果第一个节点就是要删除的元素
if cur.next is None:
self._head = None
else:
# 将第二个节点的prev指向none
cur.next.prev = None
# head指向第二个节点
self._head = cur.next
return
while cur:
if cur.item == value:
# 将cur的前一个节点的next指向后一个节点
cur.prev.next = cur.next
# 将后一个节点的prev指向cur前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
完整代码
class Node(object):
"""
双向链表节点实现
"""
def __init__(self, item):
self.prev = None
self.item = item
self.next = None
class DoubleLinkList(object):
def __init__(self):
self._head = None
def is_empty(self):
"""
判断双向链表是否为空
"""
return self._head is None
def length(self):
"""
双向链表长度
"""
# cur用来移动遍历节点
cur = self._head
# count为计数
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def traverse(self):
"""
遍历双向链表
:return:
"""
cur = self._head
while cur is not None:
print(cur.item, end=" ")
cur = cur.next
print("")
def add(self, value):
"""
头部插入节点
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 将node的next指向头节点
node.next = self._head
# 头结点的prev指向新节点
self._head.prev = node
# 将head指向node
self._head = node
def append(self, value):
"""
尾插
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 移动到链表的尾端
cur = self._head
while cur.next:
cur = cur.next
# 将尾节点的next指向node
cur.next = node
# 将node的pre指向尾节点
node.prev = cur
def insert(self, value, index):
"""
指定位置插入
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移动到指定位置的前一个节点
while count < (index - 1):
count += 1
cur = cur.next
# 新节点pre指向上一个节点
node.prev = cur
# 新节点的next指向下一个节点
node.next = cur.next
# 下一个节点的prev指向node
cur.next.prev = node
# 上一个节点next指向新节点
cur.next = node
def remove(self, value):
"""
删除节点
"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == value:
# 如果第一个节点就是要删除的元素
if cur.next is None:
self._head = None
else:
# 将第二个节点的prev指向none
cur.next.prev = None
# head指向第二个节点
self._head = cur.next
return
while cur:
if cur.item == value:
# 将cur的前一个节点的next指向后一个节点
cur.prev.next = cur.next
# 将后一个节点的prev指向cur前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
def search(self, item):
"""
查找元素是否存在
"""
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
double_link_list = DoubleLinkList()
print("当前链表是否为空：", double_link_list.is_empty())
print("当前链表长度为：", double_link_list.length())
double_link_list.append(99)
print("当前链表是否为空：", double_link_list.is_empty())
print("当前链表长度为：", double_link_list.length())
double_link_list.append(23)
double_link_list.append(89)
double_link_list.append("python")
double_link_list.append(12.66)
double_link_list.add(27)
double_link_list.insert(4, 0)
double_link_list.remove(27)
double_link_list.traverse()
print(double_link_list.search(23))
结果
当前链表是否为空： True
当前链表长度为： 0
当前链表是否为空： False
当前链表长度为： 1
4 99 23 89 python 12.66
4
True
