Python双链表实现详解：节点定义与增删改查操作
发布时间：2026-10-15| 5人浏览过
本文详细解析了Python中双链表的实现原理与代码逻辑。通过定义包含前后指针的节点类，演示了头插法、节点插入及删除的具体步骤。重点讲解了在插入和删除操作中，如何正确更新前后节点的指针指向以维持链表结构完整，适用于学习Python数据结构与算法的开发者参考。
Python双链表实现概述
本文分享使用Python语言实现双链表的具体代码示例，供读者参考学习。
双链表节点结构定义
在双链表结构中，每个节点包含两个指针域：一个指向后继节点，另一个指向前驱节点。
class Node(object):
def __init__(self, item=None):
#放数据
self.item= item
#指向后一个节点
self.next = None
#指向前一个节点
self.prior =None当前链表的第一个节点即为头节点所指向的节点，例如值为20的节点。如图所示，执行 node.next = self.head 操作时，当前节点将指向原有的第一个节点。
头插法与节点插入操作
头插法
具体的插入过程如下所示。
执行插入操作。
代码逻辑为：p.next = curNode.next 使新节点指向原后继节点；curNode.next.prior = p 使原后继节点指回新节点，从而完成双向链接。
双链表删除逻辑与特殊情况处理
删除操作。
双链表的删除逻辑。
需要特别考虑删除操作中的边界特殊情况。
常规情况下的删除流程。
以删除值为30的节点为例，展示双链表删除过程。
完整代码实现与测试
#双链表头插法实现代码
#循环终止条件为停在目标位置的前一个节点，即 count < (pos - 1)
#双向链表 从左往右读
class Node(object):
"""双向链表节点"""
def __init__(self,item):
#放数据的节点
self.elem = item
#指向后一个节点
self.next = None
#指向前一个节点
self.prev = None
#双向链表
class LinkList(object):
def __init__(self,node=None):
#代表头节点
self.__head = node
#判断链表是否为空
def is_empty(self):
return self.__head == None
def length(self):
"""返回链表的长度"""
#cur游标移动，从而实现遍历元素的功能
cur = self.__head
#count用来计数
count = 0
while cur != None:
count += 1
#让cur游标可以向下移动
cur = cur.next
return count
#遍历整个链表
def travel(self):
if self.is_empty():
return
#建立游标等于起始节点
else:
cur = self.__head
while cur != None:
print(cur.elem,end=" ")
cur = cur.next
print("")
#头插法
def add(self,item):
#新节点
node = Node(item)
if self.is_empty():
#头节点指向了新的节点
self.__head = node
else:
#新节点指向原第一个节点
node.next = self.__head
self.__head = node
node.next.prev = node
def append(self,item):
"""链表尾部添加元素"""
node = Node(item) #定义新节点
#链表是否为空链表
if self.is_empty():
#如果为空，新的节点加了进去
self.__head = node
else:
#头节点 创建游标
cur = self.__head #设置指向头结点的游标 此时的当前链表第一个节点，就是头节点指向的节点
#cur到最后一个节点停下
while cur.next != None:
cur = cur.next
#添加节点到尾部 cur道了最后一个结点 cur.next指向了新的节点node 从左往右读
cur.next = node
#当前的节点指向它前一个
node.prev = cur
#插入法 #pos从零开始
def insert(self,pos,item):
"""在指定位置添加元素"""
#指向不是头部元素，self.__head的地址
# 为下一个元素，所以pre为下一个元素
if pos <= 0:
#认为是头插法
self.add(item)
#假如长度是3 pos大于2要特殊处理
elif pos > (self.length()-1):
#尾插法
self.append(item)
else:
#创建节点 新节点
node = Node(item)
cur = self.__head
count = 0
#动起来
while count < pos:
count+=1
cur = cur.next
#把节点链接到中间任意位置 插入前一个节点 此时，cur停在后一个节点
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self,item):
"""删除元素"""
if self.is_empty():
return
cur = self.__head
#查找所有的位置有没有要删除的，若有则删除
while cur != None:
#判断cur指向的数据,是否为要删除的数据 item要删除的元素
if cur.elem == item:
#判断此节点是否为头节点
#考虑特殊情况,恰好要删除是第一个元素 当前的元素就是我要删除的元素
if cur == self.__head:
#如果删除中间, 头节点指向后一个节点
self.__head = cur.next
#考虑链表只有一个节点 直接指向None
if cur.next != None:
#是否只有一个节点
cur.next.prev = None
else:
#中间节点
cur.prev.next = cur.next
if cur.next != None:
cur.next.prev = cur.prev
break
else:
#没有找到,cur游标向继续往下移动
cur = cur.next
def search(self,item):
"""查找结点是否存在"""
#如果是一个空链表
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
#cur数据是否为查找的数据 item是要查的数据
if cur.elem == item:
return True
else:
cur = cur.next
#遍历完成 cur指向None
return False
if __name__ == '__main__':
ll = LinkList()
#第一次的
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.travel()
ll.insert(-1,50)
ll.travel()
ll.insert(2,60)
ll.travel()
ll.insert(10,300)
ll.travel()
ll.remove(50)
ll.travel()
ll.remove(300)
ll.travel()
以上内容为本文的全部介绍，希望能为读者的学习提供有益帮助，欢迎大家继续支持本站获取更多技术资源。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
