单链表python基本操作,python顺序表和链表
本文主要详细介绍python链表的基本概念和用法。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。
本文分享python链表的基本概念和用法,供大家参考。具体情况如下
一、什么是链表
链表由许多不同的节点组成,每个节点通过一个指针区域链接在一起。
链表的头指针指向头节点,通过它可以找到其他节点信息。
二、什么是节点
它由链表节点组成,每个节点包含两个部分,一个是元素区,一个是指针区。
元素存储当前节点的值,指针区域指向下一个节点的对象。在C语言中,指针应该是下一个元素的内存地址。因为python中不研究指针,所以用下一个节点的对象来代替。这样就可以通过指针区找到下一个节点的信息,从而得到下一个节点的值。
三、为什么引入链表的概念
1.先说数组的数据结构。数组是一个大的连续内存空间。每次初始化都需要开辟很大的内存空间,所以空间利用率比较低。链表不一样。链表的节点可以随机分布在任意位置,只需要指针穿透就可以了。
2.在连续存储空间中,当插入一个元素时,所有其他元素的位置也会改变。在插入和删除元素时,效率较低。
链表是一个不连续的内存空间,每个节点都有自己的内存空间,通过指针指向下一个节点。
如果您在某处插入一个节点,您只需要改变指针的方向,而不需要改变所有其他元素。
四、链表的基本操作
#实现头插入和尾插入,根据索引插入和删除节点并打印。
#定义一个节点
类别节点:
def __init__(self,data):
self.data=数据
self.next=无
类SingleLinkList:
def __init__(self):
self.head=无
self.tail=无
定义为_空(自身):
“”链表为空吗?
:返回:
回归自我。头是无
定义长度(自身):
查找当前链表的长度
:返回:
计数=0
cur=self.head
虽然cur不是None:
计数=1
下一个
返回计数
def insert_head_node(自身,数据):
将元素添加到“”链接列表的开头
:参数数据:要保存的数据
:返回:
节点=节点(数据)
node.next=self.head
self.head=node
def append_node(自身,数据):
有很多方法可以在链表的末尾添加元素。
:参数数据:
:返回:
#第一种方法是时间复杂度为O(n)的处理方法
节点=节点(数据)
#如果链表为空,则需要特殊处理
if self.is_empty():
self.head=node
else:
cur=self.head
而cur.next不是None:
下一个
#退出循环时,cur指向尾节点。
cur.next=node
#第二种方法是引入尾指针。默认情况下,当前的链表是一个空的链表,它一直指向追加节点。
# node=节点(数据)
# if self.is_empty(): #第一次向空链表中添加节点时,头指针和尾指针同时指向新节点。
# self.head=node
# self.tail=node
# else:
# 当再次添加节点到链表中的时候, 头指针始终指向头节点,尾指针始终执行未节点,如果一直向未节点追加节点,只需移动tail指针即可
# self.tail.next = node
# self.tail = node
def insert_node(self, pos, data):
"""指定位置添加元素
:param pos:
:param data:
:return:
"""
# 1, 在头部添加
if pos <= 0:
self.insert_head_node(data)
# 2, 在尾部添加
elif self.length() >= pos:
self.append_node(data)
# 3, 指定位置添加
else:
count = 0
while count < (pos - 2):
count += 1
self.head = self.head.next
# 这时候self.head 表示当前插入前一个节点
# self.head.next 表示当前插入的后一个节点
node = Node(data)
self.head.next = node
node.next = self.head.next
def delete_node(self, data):
"""删除节点
:param data:
:return:
"""
cur = self.head # 记录当前节点的位置
pre = None # 记录当前节点位置的前置节点
while cur is not None:
# 找到了要删除的元素
if cur.data == data:
# 在头部找到了要删除的元素
if cur == self.head:
self.head = cur.next
return True
else:
pre.next = cur.next
return True
else:
# 不是要找的元素, 移动光标
pre = cur
cur = cur.next
def search_node(self, data):
"""查找节点是否存在
:return:
"""
cur = self.head
while cur is not None:
if cur.data == data:
return True
cur = cur.next
return False
def reveres_node(self):
"""链表反转
:return:
"""
if self.is_empty():
return
j = 0
while j < self.length() - 1:
cur = self.head
for i in range(self.length() - 1):
cur = cur.next
if cur.next is None:
x = cur.data
self.delete_node(cur.data)
self.insert_node(j, x)
j += 1
return self.head
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。