本文研究的主要是Python中实现单向链表的相关内容,具体如下。
什么是链表
链表顾名思义就是~链
链表是一种动态数据结构,他的特点是用一组任意的存储单元存放数据元素。链表中每一个元素成为“结点”,每一个结点都是由数据域和指针域组成的。跟数组不同链表不用预先定义大小,而且硬件支持的话可以无限扩展。
链表与数组的不同点:
数组需要预先定义大小,无法适应数据动态地增减,数据小于定义的长度会浪费内存,数据超过预定义的长度无法插入。而链表是动态增删数据,可以随意增加。
数组适用于获取元素的操作,直接get索引即可,链表对于获取元素比较麻烦需要从头一直寻找,但是适用与增删,直接修改节点的指向即可,但是对于数组就比较麻烦了,例如[1,2,3,4]需要在下标为1的位置插入-2,则需要将[2,3,4]后移,赋值ls[1]=-2
数组从栈中分配空间, 对于程序员方便快速,但自由度小。链表从堆中分配空间, 自由度大但申请管理比较麻烦.
链表基本方法实现(Python)
1. 初始化链表
"""节点类""" class Node(object): def __init__(self, data): self.data = data self.nex = None def __init__(self): """初始化链表""" self.head = None
2. 获取链表长度
def __len__(self): pre = self.head length = 0 while pre: length += 1 pre = pre.nex return length
3. 追加节点
追加节点还是比较简单的,如果head节点不存在,则当前节点为head节点,否则的话找到尾节点,将尾节点的next指向当前节点(可以添加head和tail两个节点,就不用递归寻找尾节点了)
"""追加节点""" 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值的正负
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. 设置节点
找到当前节点赋值即可
"""设置节点""" 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
"""插入节点""" 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即可
"""删除某个元素""" 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
"""反转链表""" 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. 清空链表
将头赋为空就好
"""清空链表""" def clear(self): self.head = None
总结
以上就是本文关于python实现单向链表详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
- 郭子.2001-原来你什么都不想要创作集丫滚石】【WAV+CUE】
- 《使命召唤:黑色行动6》新预告公布!10月25日发售
- Atlus《暗喻幻想》媒体评分汇总:高分好评如潮!
- 2024金摇杆奖提名揭晓 《黑神话》角逐最佳视觉设计!
- 群星《新说唱2024 第3期 (上)》[320K/MP3][32.76MB]
- 群星《新说唱2024 第3期 (上)》[FLAC/分轨][95.38MB]
- 群星《新说唱2024 第3期 (下)》[320K/MP3][31.36MB]
- 幻兽帕鲁手游什么时候正式上线 最新消息一览
- 西普大陆BOSS位置盘点 解锁天启纪元玩法
- 西普大陆精灵进阶培养攻略 精灵养成指南
- dnf手游法控法系职业哪个强 dnf手游法控法系职业强度排行
- 魔兽世界血藤护目镜图纸在哪买 wlk血藤护目镜图纸购买位置介绍
- 魔兽世界无畏远征军声望军需官在哪 wlk无畏远征军声望军需官坐标位置
- 逼迫中国选手弃权事件持续发酵 玩家抵制万代模型
- B社老员工在《星空》开发期间离职 他终于说出原因