Python单向链表与双向链表原理及实现详解
本文详细解析Python中单向链表和双向链表的原理与实现。涵盖节点结构、头尾节点定义，以及插入和删除操作的核心逻辑与边界条件处理。通过完整代码示例展示单链表的双向遍历与双向链表的反向输出，帮助开发者深入理解链表数据结构在实际编程中的应用。
本文通过具体实例深入讲解Python中单向链表和双向链表的原理及其使用方法，供读者参考学习。
链表作为一种基础数据结构，虽然在循环遍历场景下效率相对较低，但在执行插入和删除操作时具有显著优势。
链表的基本构成单元是节点。
单向链表的每个节点包含两部分内容：存储的数据对象以及对下一个节点的引用，关键在于指向后续节点。
双向链表与单向链表不同，其节点由三部分构成：存储的数据对象、指向下一个节点的引用以及指向前一个节点的引用，从而支持双向遍历。
单向列表的结构示意图如下所示：
其中head表示头节点，tail表示尾节点，每个节点由Data字段存储对象和Next字段指向下一个节点组成。
接下来介绍单向链表的插入与删除操作流程。
插入新节点的操作步骤如下：
核心原理是：将前一个节点的Next引用指向新节点，同时让新节点的Next引用指向原插入位置的后一个节点。
注意：在实际代码实现中，必须考虑插入位置位于头节点或尾节点的边界情况。
删除节点的操作步骤如下：
核心原理是：定位到待删除节点的前一个节点，将该前节点的Next引用直接指向待删除节点的下一个节点，从而绕过待删除节点。
注意：实际应用中需判断被删除节点是否为头节点或尾节点，并需同步更新链表的长度信息。
以下提供一段使用Python编写的单向链表完整示例代码。
class Node:
next = None
data = None
def __init__(self,nodeData):
self.data = nodeData
class List:
head = None
size = 0
def __init__(self):
self.size = 0
self.head = None
#遍历链表
def a(self):
print("avx")
def printlist(self):
p=self.head
while(p is not None):
print(p.data)
p=p.next
print("——————————————————————————————————————")
def insertlink(self, a, newdata):
newnode = Node(newdata)
if self.size == 0:
print("The link is none")
self.head = newnode
self.size = self.size+1
else:
p = self.head
while(p is not None )and (p.data != a):
p = p.next
if p.next is None:
p.next = newnode
self.size = self.size + 1
else:
newnode.next = p.next
p.next = newnode
self.size = self.size + 1
#删除链表中的节点
def deldata(self,a):
if self.size == 0:
print("The link is none")
elif self.size ==1:
self.head = None
self.size = self.size -1
else:
p = self.head
while(p is not None )and (p.data != a):
q = p
p = p.next
if p is None:
print("Can't find a")
elif p == self.head:
self.head = p.next
elif p.data ==a and p.next is not None:
q.next = q.next.next
self.size = self.size - 1
else:
q.next = None
self.size = self.size - 1
#修改链表中的指定节点
def updatelink(self,a,b):
p = self.head
print(p.data)
while(p is not None ) and (p.data!=a):
p = p.next
if p is None:
print("Can't find a")
else:
p.data = b
if __name__=="__main__":
p = List()
p.insertlink(1,1)
p.insertlink(1,2)
p.insertlink(1,3)
p.insertlink(1,4)
print("_________________________---insertlink")
p.printlist()
print("_________________________--chalink")
p.updatelink(2,5)
p.printlist()
print("___________________________-----dellink")
p.deldata(5)
p.printlist()
代码运行后的输出结果如下：
The link is none _________________________---insertlink 1 4 3 2 —————————————————————————————————————— _________________________--chalink 1 1 4 3 5 —————————————————————————————————————— ___________________________-----dellink 1 4 3 ——————————————————————————————————————
双向链表的结构示意图如下所示：
head为头节点，tail为尾节点，每个节点包含Data存储对象、Next指向下一个节点的引用以及Pre指向前一个节点的引用，由此实现双向遍历功能。
接下来介绍双向链表的插入与删除逻辑。
插入新节点的操作步骤如下：
核心原理如下：
首先定位到目标插入位置，将新节点的Next指向该位置的下一个节点，并将原下一个节点的Pre指向新节点；同时，将插入位置左侧节点的Next指向新节点，并将新节点的Pre指向左侧节点。
删除节点的操作步骤如下：
具体说明如下：
首先定位到待删除节点的前一个节点；接着将该前节点的Next指向待删除节点的下一个节点；最后将待删除节点下一个节点的Pre指向前一个节点，即可完成删除。
以下是双向链表的完整实现代码：
class Node():
data = None
nextnode = None
prenode = None
def __init__(self, data):
self.data = data
class PersonChan():
size = 0
head = None
tail = None
def __init__(self):
self.head = None
self.tail = None
self.size = 0
#增加节点
def add_node(self, a):
newnode = Node(a)
if(self.head == None):
self.head = newnode
self.head.prenode = None
self.tail = newnode
self.tail.prenode = None
self.tail.nextnode = None
self.size = self.size+1
else:
temp = self.head
while temp.nextnode is not None:#返回尾节点tail
temp = temp.nextnode
temp.nextnode = newnode
self.tail = newnode
self.tail.prenode = temp
self.tail.nextnode = None
self.size = self.size+1
#在查找到的a后面增加节点
def ins_node(self,a,b):
newnode = Node(b)
if self.head ==None:
self.head = newnode
self.tail = newnode
print("Insert success:",newnode.data)
self.size = self.size +1
else:
temp = self.head
while(temp is not None)&(temp.data != a):
temp = temp.nextnode
if temp.nextnode == None:
temp.nextnode = newnode
self.tail = newnode
self.tail.prenode = temp
self.tail.nextnode = None
temp = None
print("Insert success:",newnode.data)
self.size = self.size+1
else:
newnode.prenode = temp
newnode.nextnode = temp.nextnode
temp.nextnode = newnode
print("Insert success:",newnode.data)
self.size = self.size+1
#删除节点
def del_node(self,a):
if self.head == None:
pass
elif self.head.data == a:
if self.size ==1:
self.head = None
self.tail = None
self.size = self.size-1
else:
self.head = self.head.nextnode
self.size = self.size -1
else:
temp = self.head.nextnode
while (temp is not None) and (temp.data != a):
temp = temp.nextnode
p = temp.prenode
if temp != None:
if temp.nextnode == None:
self.tail = p
self.tail.nextnod = None
else:
p.nextnode = temp.nextnode
temp = None
self.size = self.size -1
print("Delete is success:",a)
def listall(self):#正序排列
if self.size == 0:
print("No data in the list")
else:
temp = self.head
while(temp is not None):
print(temp.data)
temp = temp.nextnode
def lista(self):#倒序排列
if self.size == 0:
print("No data in the list")
temp = self.tail
while(temp is not None):
print(temp.data)
temp = temp.prenode
if __name__ == '__main__':
link = PersonChan()
link.add_node(1)
link.add_node(2)
link.add_node(3)
link.add_node(4)
link.listall()
print("The list's size is:",link.size)
link.lista()
代码运行后的输出结果如下：
1 2 3 4 ("The list's size is:", 4) 4 3 2 1
更多关于Python相关技术的详细内容，建议读者参考本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》以及《Python入门与进阶经典教程》。
希望本文所述内容能对读者的Python程序设计工作有所帮助。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
