【30天从零学Python】重要补充三、双向链表

30天从零学Python

通信工程专业科班生，用了几十年MATLAB，为了过大厂机考，不得不自学Python。

重要补充三、双向链表

由于做题过程中遇到很多重要但是细碎的知识点，专门开辟一个系列总结一下。
本集重点补充一下Python中双向链表的创建和操作方法。双向链表可以方便地动态维护一组数据，但是编写代码的时候要细心，主要是要记得把前后链表关联起来，不要断开。

1. 双向链表基础

之前有学习过单向的链表，就是每个节点只维护下一个节点的地址，而不关心上一个节点的地址。但是这样很难访问前一个元素。所以双向链表在此基础上改进而来。

1.1 双向链表的节点类定义

classNode:def__init__(self,data):self.data=data self.pre_node=Noneself.post_node=None

1.2 双向链表类定义和方法

classNode:def__init__(self,data):self.pre_node=Noneself.post_node=Noneself.data=dataclassLinkList:def__init__(self):# 双向链表需要保存头节点和尾节点self.head_node=Noneself.end_node=None# 自定义方法defget_length(self):# 返回当前链表的长度link_length=0current_node=self.head_nodewhilecurrent_nodeisnotNone:link_length+=1current_node=current_node.post_nodereturnlink_lengthdeffind_node(self,data_i):# 返回保存了data_i的节点link_length=self.get_length()iflink_length==0:returnNonecurrent_node=self.head_nodewhilecurrent_nodeisnotNone:ifcurrent_node.data==data_i:returncurrent_node current_node=current_node.post_node prev_node=current_node.pre_nodeifprev_node.data!=data:returnNonedefdelete_node(self,node_i):ifself.get_length()==0:return# 删除节点node_iifnode_i==self.head_node:# 如果要删除的节点是头节点ifnode_i.post_nodeisNone:nx_node=Noneelse:nx_node=node_i.post_node# 找到当前节点的下一个节点（作为新的头节点）nx_node.pre_node=None# 将新的头节点的pre_node置为空self.head_node=nx_node# 更新当前链表的头节点（重要！！！不要忘记）returnifnode_i==self.end_node:new_end_node=node_i.pre_node# 找到当前节点的上一个节点（作为新的尾节点）new_end_node.post_node=None# 将新的尾节点的post_node置为空self.end_node=new_end_node# 更新当前链表的尾节点（重要！！！不要忘记）return# 如果不是头/尾节点pre_node_in_List=node_i.pre_node# 记录当前节点的上一个节点next_node_in_List=node_i.post_node# 记录当前节点的下一个节点pre_node_in_List.post_node=next_node_in_List# 将上一个节点的尾节点指向当前节点的下一个节点# 问题：只修改了前驱的后继，没有修改后继的前驱# 修复：next_node_in_List.pre_node=pre_node_in_Listreturndefadd_node(self,node_i):# 将node_i加入链表中link_length=self.get_length()iflink_length==0:self.head_node=node_i self.end_node=node_i# 不要忘记这一步returnlast_node=self.end_node# 记录当前链表的尾节点# 将当前节点加入到链表尾部node_i.pre_node=last_node last_node.post_node=node_i# (很重要！！！)node_i.post_node=Noneself.end_node=node_i# 更新当前链表的尾节点 (很重要！！！)returndefforward_read(self):# 正向打印current_node=self.head_nodewhilecurrent_nodeisnotNone:print(current_node.data,end=" ")current_node=current_node.post_nodeprint()defreverse_read(self):# 正向打印current_node=self.end_nodewhilecurrent_nodeisnotNone:print(current_node.data,end=" ")current_node=current_node.pre_nodeprint()if__name__=="__main__":data=[1,2,3,4,5]Data_Link=LinkList()fordata_iindata:node_i=Node(data_i)Data_Link.add_node(node_i)Data_Link.reverse_read()Data_Link.forward_read()target_node=Data_Link.find_node(4)iftarget_nodeisnotNone:Data_Link.delete_node(target_node)Data_Link.reverse_read()Data_Link.forward_read()

2. 主要坑点

1. 改动元素的时候需要先判断是否是头/尾节点，如果是头/尾节点，要记得把self.head_node和self.end_node更新
2. 改动的元素不是头/尾节点的时候，也要记得双向更新链表！
   

总结

本集以代码的方式创建和操作了双向链表。