单向链表Python

2024-07-13 03:10| 来源: 网络整理| 查看: 265

单向链表

文章目录单向链表链表结构用python实现单向链表单项链表所具有的操作往链表头部添加一个结点add（）返回链表中所有节点的值组成的列表往链表的末尾添加一个结点在指定的位置插入结点删除第一个数据为data的元素修改链表中的某一结点的data查找链表中是否值为data的结点链表和顺序表的时间复杂度附件：用python实现链表功能的全部代码附件2：单向链表寻找尾结点

链表结构

链表是一种物理存储单元上非连续、非顺序的存储结构

数据元素的逻辑顺序通过链表中的指针链接次序实现

链表由一系列结点组成，结点可以在运行时动态生成

每个结点包括两个部分：存储数据元素的数据域、存储下一个节点地址的指针域

在这里插入图片描述

用python实现单向链表

用class分别定义结点（Node）和链表（linklist）两个类，添加想要的属性即可！

节点类

代码实现如下：

class Node: # 结点类 def __init__(self,data,_next = None): self.data = data self._next = _next

链表类代码实现如下：

class Singlelinklist: def __init__(self): self.head = None self._length = 0 单项链表所具有的操作方法功能is_empty()链表是否为空length()返回链表的长度node_list()返回链表中所有节点的值组成的列表add(data)链表的头部添加一个节点，值为dataappend()链表尾部添加节点，值为datainsert(pos,data)指定的位置添加节点，值为dataremove(data)删除第一个值为data的节点modify(pos,data)修改指定位置元素的值为datasearch(data)查找节点是否存在往链表头部添加一个结点add（）

实现步骤：链表为空的时候照样成立

创建一个新的节点将新的节点的next属性指向原来的头部节点，即：self.head将头部节点重新指向创建的新节点链表的长度属性加1 在这里插入图片描述

链表为空的情况如下：打你想链表为空添加头部节点

代码实现如下：

注意本文def的所有的方法（函数）都需要放到类（class）中才可实现，其是一个类方法

def add(self,data): # 请将我放入类中执行 node = Node(data) node._next = self.head self.head = node # 存储的是一个类对象而不是对象类对象中包括对象和下一个类对象的地址 self.lenth += 1 返回链表中所有节点的值组成的列表

方法1实现步骤循环节点法

创建一个新的列表将每个节点的data属性添加到列表中返回列表

具体第二步入何进行实现？如何才能遍历每个节点，请看下图：在这里插入图片描述

代码实现如下：

def nodes_list(self): res = [] cur = self.head # 第一个结点 while cur: #如果有节点进入循环 res.append(cur.data) #将该节点的数据添加到列表中 cur = cur.next # 并赋值下一节点如果下一节点为 None 跳出循环返回res return res

方法2实现步骤循环索引法

创建一个列表res循环遍历指定的次数将指定的data值添加到列表中返回res列表

具体实现请看下图：在这里插入图片描述

具体的如何精确控制循环的次数？

a= 4 # a是多少就循环多少次 while a: print(f'这是第{5-a}次循环') a -= 1

这是第1次循环这是第2次循环这是第3次循环这是第4次循环

代码实现如下：

def nodes_list(self): res = [] a = self.length() #循环self.length()次 cur = self.head while a: res.append(cur.data) cur = cur.next a -= 1 return res 往链表的末尾添加一个结点

实现方法1步骤

循环找到尾节点将尾节点的next属性指向新的节点链表的长度加1 通过next属性是否为None来指向尾部节点详见博主原创文章 ==双向链表python实现==(附件1：双向链表寻找尾结点(同单向))内容尾部添加节点

代码实现如下：

def append(self, data): node = Node(data) cur = self.head if cur: # 如果head属性有节点，就证明不是空链表 while cur.next: # 当cur为尾节点的时候跳出循环 cur = cur.next cur.next = node else: self.head = node self._length += 1

实现方法2（通过索引找到指定的节点）

通过索引找到指定的节点的方法详见博主原创文章 ==双向链表python实现==(附件2：通过索引寻找指定的结点)内容查找尾节点

def append_node(self,data): node = Node(data) if self.is_empty(): self.head = node # 空链表的执行条件 cur = self.head # 非空链表的执行条件 a = self._length - 1 while a: cur = cur.next a -= 1 cur.next = node self._length += 1 在指定的位置插入结点

示意图如下：指定的位置插入节点

思考这么一个问题：

就拿上面盖的这个图来说，给索引为2的地方插入一个值，重要的是找索引为1的节点还是索引为2的节点？

显然索引为1的节点才是重要的！！！

首先Step1是将新的节点的next属性指向原来索引为2的节点，也就是索引为1的节点的next属性（就是索引为2的节点）Step2是将索引为1的next属性指向新的节点，如果得到索引为2的节点无法直接完成操作（需要定义一个前驱节点）

实现具体步骤代码实现如下：

创建新的节点node找到索引为pos-1的节点（前面好像说了如何通过索引找到指定的节点呦）将pos-1结点 next属性（原来pos位置上的结点）赋值给新的结点的next属性将新的结点赋值给 pos-1结点的next属性链表长度加1 def insert(self,pos,data): # pos代表插入节点的位置，也就是第pos+1 个结点 pos是索引 ''' 非正常情况下如果小于0 默认添加到头部如果超出范围默认添加到尾部 ''' if pos self.lenth: # 在此处pos > self.lenth-1也行只不过当添加末尾元素的时候会调用 append（）方法 self.append(data) else: node = Node(data) cur = self.head pos -= 1 while pos: # 这里应用的很巧妙因为没有像传统的循环那样创建一个计数器直接用现有的pos cur = cur.next pos -= 1 node.next = cur.next cur.next = node self.lenth += 1 删除第一个数据为data的元素

删除第一个值为data的节点具体步骤

创建前驱节点prev遍历链表，找到值为data的结点将被删除结点的next赋值给被删除结点的前一节点（也就是说程序执行的过程中，为前后两个结点共同执行）如果data找不到返回-1 如果成功删除直接跳循环返回0链表长度-1 '''仅仅只是Singlelinklist类方法定义的部分其他的部分参考上面的''' def remove(self,data): # 删除链表中第一个值为data的元素 cur = self.head prev = None # 创建一个前驱节点 while cur: if cur.data == data: # 进行删除操作 # 内层的if 都是删除操作 if not prev: # 删除的节点是第一个节点 self.head = cur.next ''' 原本的self.head 为 cur 但是如果是第一个的要被删除的话那么 self.head 必须指向第二个即第一个的next属性 ''' else: prev.next = cur.next ''' 如果删除的结点不是第一个结点那么就将被删除结点的next属性赋值给被删除结点的前一个结点prev ''' self.lenth -= 1 return 0 # 加上这行代码只删除一个不加的话删除全部 prev = cur cur = cur.next return -1

在这里再提供另一种代码的实现方法但是下面的代码的可变形性不太好，自行使用哈

def remove_(self,data): cur = self.head if cur.data == data: self.head = self.head.next self._length -= 1 return 0 prev = None while cur: if cur.data == data: prev.next = cur.next self._length -=1 return 0 else: prev = cur cur = cur.next return -1 修改链表中的某一结点的data 正常情况：只用self.head一次然后进行pos次循环next 就可以找到相对应的结点将节点的data属性进行修改即可非正常情况下输入的值超出范围的时候

代码实现如下（这部分又涉及到了通过索引找到指定的节点=附件2)

def modify(self,pos,data): ''' 修改链表中指定位置的值 ''' if 0

【本文地址】

单向链表Python

单向链表Python

今日新闻

推荐新闻