Python单链表原理与实现方法详解
本文实例讲述了Python单链表原理与实现方法。分享给大家供大家参考，具体如下：
Python实现单链表
关于链表
- 链表（LinkedList）是由许多相同数据类型的数据项按照特定顺序排列而成的线性表。
- 链表中个数据项在计算机内存中的位置是不连续且随机的，数组在内存中是连续的。
- 链表数据的插入和删除很方便，但查找数据效率低下，不能像数组一样随机读取数据。
单链表的实现
-
一个单向链表的节点由数据字段和指针组成，指针指向下一个元素所在内存地址
-
定义一个链表节点类,self.value实例属性表示节点数据字段；self.next表示指针；初始化值为None
-
classNode(object): def__init__(self,value=None,next=None): self.value=value self.next=next
-
在单链表中第一个节点为头(head)指针节点(即头指针指向的节点为单链表第一个节点，后续简称头指针节点)，从头指针节点出发可以遍历整个链表，进行元素查找，插入和删除，非常重要。一般不移动head头指针。
-
单链表中最后一个节点为尾节点，其指针为None，表示结束。
-
建立单链表我们首先需要创建头指针节点（引入头指针是为了方便操作单链表，对于头指针节点，只有指针域指向链表第一个节点，不含实际值）
-
classlinkedList(object): def__init__(self): self.head=Node() #创建头指针结点 self.length=0 #初始链表长度，头指针节点不计入长度 def__len__(self): #重写特殊方法返回self.length returnself.length
-
链表初始化之后，开始定义链表方法
-
链表头部插入节点：
-
调用Node()传入待插入的值value创建待插入节点
-
判断当前链表是否为空链表，链表为空：
- 插入节点既是链表头指针指向的节点也是尾节点(指向None)
-
链表不为空：
- 待插入节点指向原头指针节点，头指针重新指向待插入节点
- 首先需要将原头指针结点，存放到临时变量中(防止head指针变更时，指针断裂导致数据丢失，链表中指针就是连接的纽带，其中某个纽带断裂(即指针指向其他)则后续数据都将丢失)
- 将头指针指向新插入节点
- 新插入节点指针指向原头指针节点
- 长度+1
-
defhead_insert(self,value):#链表头部插入 node=Node(value) ifself.head.next==None: self.head.next=node node.next=None else: #插入元素指针域指向原head元素 tmp_head=self.head.next#原头指针节点存储到tmp_head self.head.next=node#新head指针指向node node.next=tmp_head#新插入节点指向原头指针节点 self.length+=1
-
-
链表头部删除节点：
-
依旧是先判断链表是否为空，为空则返回False
-
链表不为空时：
- 头指针指针域(指针域存放下一节点的内存地址，即头指针节点)指向头指针，也就是说链表第一个节点变成了头指针head，由于head不计入链表，所以就相当于删除了第一个节点(有点绕)
- 同时返回删除的值
-
defhead_del(self):#删除头结点,返回头结点的值 ifself.head.next==None: returnFalse else: #头指针指针域指向自己 self.head=self.head.next self.length-=1 returnself.head.value
-
-
链表尾部添加节点：
-
创建待插入节点对象
-
判断链表是否为空，为空则头指针节点就是待插入节点，也是尾节点
-
链表不为空：
- 首先通过while循环(循环条件为节点指针是否为None)找到当前链表的最后一个元素
- 然后将当前最后一个元素指向待插入节点
- 长度+1
-
defappend(self,value):#链表尾部添加结点 #创建新插入的结点对象 node=Node(value) ifself.length==0: self.head.next=node#只有一个节点，指针指向自己 else: curnode=self.head.next#变量curnode存放指针 whilecurnode.next!=None: curnode=curnode.next curnode.next=node#当为最后一个节点时，指针指向新插入节点 self.length+=1
-
-
指定位置后面插入节点：
-
这里方法接受两个位置参数，index插入位置和value插入值
-
依旧创建新节点对象
-
判断是否为空
-
在链表不为空的条件下：
- 首先定义一个变量表示当前节点，以及一个index索引比较数i
- 使用while循环，索引比较数i!=index时，更新当前节点
- 找到索引位置节点后，首先让插入节点指向索引位置节点的下一个节点
- 然后让索引位置节点指向插入节点
- 链表长度+1
-
definsert(self,index,value): node=Node(value) ifself.length==0: self.head.next=node else: i=0 cur_node=self.head.next whilei!=index: cur_node=cur_node.next i+=1 node.next=cur_node.next cur_node.next=node self.length+=1
-
-
给定值删除该值节点：
-
删除链表中给定的值我们需要遍历整个链表，因此需要创建一个可迭代对象
-
定义节点迭代方法
-
defiter_node(self): cur_node=self.head.next #当前节点 whilecur_node.next!=None: #对除最后一个节点进行可迭代化处理 yieldcur_node cur_node=curnode.next ifcur_node.next==None: #对尾节点进行可迭代化处理 yieldcur_node
-
重写特殊方法–iter–，用来声明这个类是一个迭代器
-
def__iter__(self):#遍历列表节点 fornodeinself.iter_node(): yieldnode.value
-
首先定义一个Flag变量(默认为False)，用来表示删除状态
-
依旧判断链表是否为空
-
链表不为空时：
- 设置一个前驱节点(当找到需要删除的节点时，先让前驱节点指向删除节点的后继节点)
- for循环遍历链表
- 找到符合条件的值就让前驱节点指向，删除节点的后继节点，然后del删除node，Flag更改为True
- 没找到符合条件的值，就更新前驱节点，继续遍历
-
defdelete_node(self,value): Flag=False ifself.length==0: returnFalse else: previous_node=self.head#初始化前置节点为头结点 fornodeinself.iter_node(): ifnode.value==value: previous_node.next=node.next#前置节点指针指向当前节点的后继节点 delnode self.length-=1 Flag=True else: previous_node=node#更新前置节点的值 returnFlag
-
-
完整代码：
-
#定义链表节点类 classNode(object): def__init__(self,value=None,next=None): self.value=value#节点元素 self.next=next#指针 #单链表类 classLinkedList(object): def__init__(self): self.head=Node()#创建头结点 self.length=0#初始化链表长度 def__len__(self): returnself.length def__iter__(self):#遍历列表节点 fornodeinself.iter_node(): yieldnode.value defiter_node(self): curnode=self.head.next whilecurnode.next!=None: yieldcurnode curnode=curnode.next ifcurnode.next==None: yieldcurnode defhead_insert(self,value):#链表头部插入 node=Node(value) ifself.head.next==None: self.head.next=node node.next=None else: #插入元素指针域指向原head元素 tmp_head=self.head.next#原头指针节点存储到tmp_head self.head.next=node#新head指针指向node node.next=tmp_head#新插入节点指向原头指针节点 self.length+=1 defhead_del(self):#删除头结点,返回头结点的值 ifself.head.next==None: returnFalse else: #头指针指针域指向自己 self.head=self.head.next self.length-=1 returnself.head.value defappend(self,value):#链表尾部添加结点 #创建新插入的结点对象 node=Node(value) ifself.length==0: self.head.next=node#只有一个节点，指针指向自己 else: curnode=self.head.next#变量curnode存放指针 whilecurnode.next!=None: curnode=curnode.next curnode.next=node#当为最后一个节点时，指针指向新插入节点 self.length+=1 #这里的insert是指定值后面插入不是指定位置 definsert(self,index,value): node=Node(value) ifself.length==0: self.head.next=node self.length+=1 else: forndinself.iter_node(): ifnd.value==index:#如果nd节点值等于index，则插入到nd后 tmp_node=nd.next#将nd的指针存放到中间变量 nd.next=node#nd节点指向插入节点 node.next=tmp_node#插入节点指向原nd.next节点 self.length+=1 returnTrue returnFalse defreplace(self,old_value,new_value): index=0 ifself.length==0: returnFalse else: fornodeinself.iter_node(): ifnode==old_value: node.value=new_value index+=1 ifindex!=0: returnindex#替换节点数量(存在节点值相同情况) else: returnFalse#替换失败，未找到替换值 defdelete_node(self,value): Flag=False ifself.length==0: returnFalse else: previous_node=self.head#初始化前置节点为头结点 fornodeinself.iter_node(): ifnode.value==value: previous_node.next=node.next#前置节点指针指向当前节点的后继节点 delnode self.length-=1 Flag=True else: previous_node=node#更新前置节点的值 returnFlag #测试 l=LinkedList() l.append(1) l.append(2) l.append(7) l.append(5) l.append(6) l.append(7) l.head_insert(3) print("当前链表长度：%s"%l.length) #print("删除头结点为：%d"%l.head_del()) print("当前链表长度：%s"%l.length) i=1 #l.delete_node(7) fornodeinl: print("第%d个链表节点的值:%d"%(i,node)) i+=1运行结果：
当前链表长度：7
当前链表长度：7
第1个链表节点的值:3
第2个链表节点的值:1
第3个链表节点的值:2
第4个链表节点的值:7
第5个链表节点的值:5
第6个链表节点的值:6
第7个链表节点的值:7
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。