个人中心
gpt4 book ai didi

python实现单向链表详解

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 29 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python实现单向链表详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文研究的主要是Python中实现单向链表的相关内容，具体如下.

什么是链表 。

链表顾名思义就是～链 。

链表是一种动态数据结构，他的特点是用一组任意的存储单元存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的。跟数组不同链表不用预先定义大小，而且硬件支持的话可以无限扩展.

链表与数组的不同点:

数组需要预先定义大小，无法适应数据动态地增减，数据小于定义的长度会浪费内存，数据超过预定义的长度无法插入。而链表是动态增删数据，可以随意增加.

数组适用于获取元素的操作，直接get索引即可，链表对于获取元素比较麻烦需要从头一直寻找，但是适用与增删，直接修改节点的指向即可，但是对于数组就比较麻烦了，例如［1，2，3，4］需要在下标为1的位置插入－2，则需要将［2，3，4］后移，赋值ls[1]=-2 。

数组从栈中分配空间, 对于程序员方便快速,但自由度小。链表从堆中分配空间, 自由度大但申请管理比较麻烦. 。

链表基本方法实现（Python） 。

1. 初始化链表 。

?
1
2
3
4
5
6
7
8
9
10
11
"""节点类"""
 
 
class Node( object ):
   def __init__( self , data):
     self .data = data
     self .nex = None
 
def __init__( self ):
   """初始化链表"""
   self .head = None

2. 获取链表长度 。

?
1
2
3
4
5
6
7
def __len__( self ):
   pre = self .head
   length = 0
   while pre:
     length + = 1
     pre = pre.nex
   return length

3. 追加节点 。

追加节点还是比较简单的,如果head节点不存在，则当前节点为head节点，否则的话找到尾节点，将尾节点的next指向当前节点（可以添加head和tail两个节点，就不用递归寻找尾节点了） 。

python实现单向链表详解

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""追加节点"""
 
def append( self , data):
   """
   1.head 为none :head-->node
   2.tail.nex-->node
   :param data:
   :return:
   """
   node = Node(data)
   if self .head is None :
     self .head = node
   else :
     pre = self .head
     while pre.nex:
       pre = pre.nex
     pre.nex = node

4. 获取节点 。

获取节点也是比较容易的，无非就是判断index值的正负 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
def get( self , index):
   """
   :param index:
   :return:
   """
   index = index if index > = 0 else len ( self ) + index
   if len ( self ) < index or index < 0 :
     return None
   pre = self .head
   while index:
     pre = pre.nex
     index - = 1
   return pre

5. 设置节点 。

找到当前节点赋值即可 。

?
1
2
3
4
5
6
7
"""设置节点"""
 
def set ( self , index, data):
   node = self .get(index)
   if node:
     node.data = data
   return node

6. 插入节点 。

插入节点需要找到插入节点的前一个节点pre_node（索引index的正负，前一节点不同，需要判断一下），然后将pre_node.nex指向当前节点。同时将当前节点的nex指向pre_node.nex.nex 。

python实现单向链表详解

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""插入节点"""
 
def insert( self , index, data):
   """
   1.index 插入节点位置包括正负数
   2.找到index-1-->pre_node的节点
   3.pre_node.next-->node
    node.next-->pre_node.next.next
   4.head
   :param index:
   :param data:
   :return:
   """
   node = Node(data)
   if abs (index + 1 ) > len ( self ):
     return False
   index = index if index > = 0 else len ( self ) + index + 1
   if index = = 0 :
     node.nex = self .head
     self .head = node
   else :
     pre = self .get(index - 1 )
     if pre:
       nex = pre.nex
       pre.nex = node
       node.nex = nex
     else :
       return False
   return node

7. 删除节点 。

删除节点，也要区分一下索引的正负。找到当前节点的前一个节点pre_node和后一个节点next_node，将pre_node.nex–>next_node即可 。

python实现单向链表详解

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""删除某个元素"""
 
def delete( self , index):
   f = index if index > 0 else abs (index + 1 )
   if len ( self ) < = f:
     return False
   pre = self .head
   index = index if index > = 0 else len ( self ) + index
   prep = None
   while index:
     prep = pre
     pre = pre.nex
     index - = 1
   if not prep:
     self .head = pre.nex
   else :
     prep.nex = pre.nex
   return pre.data

8. 反转链表 。

反转链表的实现有多种方式，比较简单的就是生成一个新的链表－－》可以用数组存储所有节点让后倒序生成新的链表 在这里用下面这种方式生产： 反转链表就是将node.nex–>pre_node 递归实现即可，然后让tail赋值为head 。

python实现单向链表详解

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""反转链表"""
 
def __reversed__( self ):
   """
   1.pre-->next 转变为 next-->pre
   2.pre 若是head 则把 pre.nex --> None
   3.tail-->self.head
   :return:
   """
 
   def reverse(pre_node, node):
     if pre_node is self .head:
       pre_node.nex = None
     if node:
       next_node = node.nex
       node.nex = pre_node
       return reverse(node, next_node)
     else :
       self .head = pre_node
 
   return reverse( self .head, self .head.nex)

9. 清空链表 。

将头赋为空就好 。

?
1
2
3
4
"""清空链表"""
 
def clear( self ):
   self .head = None

总结 。

以上就是本文关于python实现单向链表详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！ 。

原文链接：http://blog.csdn.net/qq490691606/article/details/49945287 。

最后此篇关于python实现单向链表详解的文章就讲到这里了,如果你想了解更多关于python实现单向链表详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

29 4 0
文章推荐： 华米：Amazfit GTR 2 与 Amazfit GTS 2 智能手表已支持微信支付
文章推荐： Python测试人员需要掌握的知识
文章推荐： Python生成器以及应用实例解析
文章推荐： 代码分析Python地图坐标转换
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com