数据结构:简单理解单链表,python实现单链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构:简单理解单链表,python实现单链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3574字,纯文字阅读大概需要6分钟。
内容图文
单链表
特点:结点中只包含一个指针域,且首尾不连接
图解:
名词:
名词 | 概念 |
---|---|
头指针 | 指向链表中第一个结点(或为头结点、或为首元结点)的指针 |
头结点 | 在链表的首元结点之前附设的一个结点;数据域内只放表长等信息,它不计入表长度。其作用是统一空表、和非空链表的形式 |
首元结点(开始结点) | 指链表中存储线性表第一个数据元素a1的结点 |
尾结点(结束结点) | 指链表中最后一个结点,尾指针指向NULL |
大家要明白,链表解决的是我们开发中的什么问题?
数组在插入和删除的时候,需要查找到当前元素,并把后续所有的元素全部向前或者向后移动,而链表在查找到以后,只需要用前一节点的指针指向新的节点或者删除元素的后一节点即可。
可以用大脑想一下,对于无序不相邻的元素,通过链表进行关联,并且可以进行快速的增删是多么方便的一件事!
Python中单链表的实现
#创建结点对象类
class Node(object):
#创建结点,初始化两个变量,默认均为None,创建新结点传value值即可,next存的是下一个结点对象
def __init__(self, value=None, next=None):
self.value, self.next = value, next
class SingleLink(object):
#初始化三个变量,
# final_node:记录最后一个结点
# root:记录头结点
# length:记录链表长度
def __init__(self):
self.final_node = None
self.root = Node()
self.length = 0
# 末尾增加
# 在链表末尾插入结点,即将final_node指向新结点,更新final_node,length自增1
def append(self, value):
node = Node(value)
if self.final_node is None:
self.root.next = node
else:
self.final_node.next = node
self.final_node = node
self.length += 1
# 头部增加
# 在头部插入结点,即将root头结点指向新结点,临时记录下指向新结点之前的next结点,将root结点指向新结点,将新结点指向next结点即可,长度length自增1
def appendleft(self, value):
node = Node(value)
if self.root.next is None:
self.root.next = node
else:
cur_node = self.root.next
self.root.next = node
node.next = cur_node
self.length += 1
# 循序结点
# 循环遍历链表,首先判断链表是否为None,None即空链表
# 从root结点开始,依次while循环next结点并输出结点,当结点=final_node时,即遍历到最后一个结点,直接退出循环,输出最后一个结点即可
def iter(self):
if self.root is None:
raise Exception("Link is Null")
else:
cur_node = self.root.next
while cur_node != self.final_node:
yield cur_node
cur_node = cur_node.next
yield cur_node
# 返回链表长度
def len(self):
return self.length
# 返回链表数据为数组
# 使用列表生成式生成包含链表所有value的数组
def iterlink(self):
return [node.value for node in self.iter()]
# 删除链表数据
# 存储上一个结点,初始为root结点
# 循环遍历结点,调用iter()方法即可,当遍历结点value与传入value相等时,将上一结点指向当前结点的下一结点,即为删除(也可手动del此结点在内存中的占用),若结点为最后一个结点,记得更新final_node为当前结点的上一结点,长度length自减1
def delete(self, value):
prev_node = self.root
for node in self.iter():
if node.value == value:
if node is self.final_node:
self.final_node = prev_node
else:
prev_node.next = node.next
self.length -= 1
else:
prev_node = node
# 查询链表数据
# 调用iter方法即可,遍历结点node的值与输入值相同时,返回node即可
def find(self, value):
for node in self.iter():
if node.value == value:
return node
return -1
# 更新链表数据
# 调用iter方法,遍历结点node的值与传入值相同时,将新值赋给遍历node即可,此赋值仅改变value,对象还是同一个结点对象,所以无需其它操作
def update(self, old_value, new_value):
node = self.find(old_value)
if node != -1:
node.value = new_value
return 1
else:
return -1
python编写单链表,需要大家思考的问题是:
1.最终结点final_node变量的使用
2.删除操作时,对于上一结点prev_node变量的使用还有一个尾巴,相信看懂的应该可以看到,上述方法还不支持对于重复数据的查找,删除,更新操作,目前只会对第一个找到的结点做操作,大家看完文章后可以自己试一下,拓展出重复数据的删改查操作,只有自己动手才能真正的记住和理解,不要只停留在看懂这一层阶噢,加油吧
注:欢迎大家沟通学习,可以但不限于Web,数据结构,操作系统,数据库,中间件等知识
内容总结
以上是互联网集市为您收集整理的数据结构:简单理解单链表,python实现单链表全部内容,希望文章能够帮你解决数据结构:简单理解单链表,python实现单链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。