数据结构与算法单链表,数据结构单链表基本结构的算法分析
Yyds干货库存
一、概述1.1为什么在链表顺序表的构造中需要提前知道数据大小才能申请连续存储空间，扩展时使用起来不是很灵活。
链表结构可以充分利用计算机内存空间，实现灵活的动态内存管理。
1.2链表(Linked list)的定义链表是一种常见的基础数据结构，它是一种线性表，但不是像顺序表那样连续存储数据，而是在每个节点(数据存储单元)中存储下一个节点的位置信息(即地址)。
二。单向链表单向链表，也叫单链表，是链表最简单的形式。它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接字段指向一个空值。
元素字段elem用于存储特定数据。域next用于存储下一个节点的位置(python中的标识)。变量p指向链表头节点(第一个节点)的位置。从p开始，可以找到表中的任意节点。2.1节点实现类SingleNode(object):
单个链接列表的节点
def __init__(self，item):
# _item保存数据元素
self.item=项目
# _next是下一个节点的ID
Self.next=None2.2单个节点的操作is_empty():链表是否为空length():链表长度travel():遍历整个链表add(item):在链表头部添加元素append(item):在指定位置添加元素insert(pos，item):添加元素remove(item):删除节点搜索(item):查找节点中是否有2.3单个节点的实现类singlinklist(object):
单一链接列表
def __init__(self):
自我。_head=无
定义为空(自身):
确定链表是否为空
回归自我。_head==无
定义长度(自身):
链表长度
# cur最初指向头节点。
cur=self。_head
计数=0
#当未到达尾部时，尾部节点指向None
一边诅咒！=无：
计数=1
#将曲线向后移动一个节点
下一个
返回计数
定义行程(自己):
遍历链表
cur=self。_head
一边诅咒！=无：
打印当前项目，
下一个
打印“”1，将元素添加到页眉
定义添加(自身，项目):
将元素添加到标头
#首先创建一个节点来保存项目的值
node=SingleNode(项目)
#将新节点的链接域next指向头节点，即_head所指向的位置。
node.next=self。_head
#将链表的head _head指向新的节点
自我。_head=node2，在末尾添加元素
定义附加(自身，项目):
在结尾加入元素
node=SingleNode(项目)
#首先判断链表是否为空，如果是，指向新节点的point _head。
if self.is_empty():
自我。_head=node
#如果它不为空，找到尾部并将尾节点的下一个指向新节点。
否则：
cur=self。_head
下一个！=无：
下一个
Cur.next=node3。在指定位置添加元素
定义插入(自身、位置、项目):
在指定位置添加元素
#如果指定的位置pos在第一个元素之前，则执行标题插入。
如果pos=0:
self.add(项目)
#如果指定位置超出了链表的结尾，则执行结尾插入。
elif pos (self.length()-1):
自我附加(项目)
#找到指定的位置
否则：
node=SingleNode(项目)
计数=0
# pre用于指向指定位置pos的前一个位置pos-1，最初从头节点移动到指定位置。
前=自我。_head
计数时(位置1):
计数=1
pre=pre.next
#首先将新节点的下一个指向插入位置的节点。
node.next=pre.next
#将插入位置上的下一个节点指向新节点
Pre.next=node4，删除该节点
定义移除(自身，项目):
删除节点
cur=self。_head
pre=无
一边诅咒！=无：
#找到了指定的元素。
if cur.item==item:
#如果第一个是删除的节点
如果不是预：
#将头指针指向头节点的下一个节点
自我。_head=cur.next
否则：
#将删除位置的上一个节点的下一个指向删除位置的下一个节点
pre.next=cur.next
破裂
否则：
#继续按链表将节点移回。
前=当前
Cur=cur.next5找出节点是否存在。
定义搜索(自身，项目):
链表找出一个节点是否存在，并返回真或假
cur=self。_head
一边诅咒！=无：
if cur.item==item:
返回True
下一个
True 2.4与顺序表相比，RETURN 2.4的链表失去了顺序表随机读取的优势。同时，由于在链表中加入了节点的指针字段，空间开销相对较大，但存储空间的使用相对灵活。
链表和顺序表的各种操作复杂度如下：
操作
链表
程序表
访问元素
O(n)
O(1)
在开头插入/删除
O(1)
O(n)
在末尾插入/删除
O(n)
O(1)
在中间插入/删除
O(n)
O(n)
注意，虽然表面上复杂度是O(n)，但是链表和有序表的插入和删除是完全不同的。链表的主要耗时操作是遍历搜索，删除和插入操作本身的复杂度为O(1)。顺序表查找速度非常快，主要的耗时操作是复制覆盖。因为，除了目标元素在尾部的特殊情况，在插入和删除序列表时，操作点之后的所有元素都需要来回移位，这只能通过复制和覆盖来完成。
第三，单循环链表
单向链表的一种变体是单向循环链表。链表中最后一个节点的next字段不再是None，而是指向链表的头节点。
3.1相关操作is_empty()确定链表是否为空。length()返回链表的长度。travel()遍历add(item)。在头部添加一个节点append(item)。在尾部添加一个节点插入(pos，item)。在指定位置添加一个节点remove(item)。搜索(项目)以确定节点是否存在。3.2实现及相关操作类节点(对象)
节点
def __init__(self，item):
self.item=项目
self.next=无
SinCycLinkedlist类(对象):
单向循环链表
def __init__(self):
自我。_head=无
定义为空(自身):
确定链表是否为空
回归自我。_head==无
定义长度(自身):
返回链表的长度
#如果链表为空，返回长度0
if self.is_empty():
返回0
计数=1
cur=self。_head
下一个！=自我。_head:
计数=1
下一个
返回计数
定义行程(自己):
遍历链表
if self.is_empty():
返回
cur=self。_head
打印当前项目，
下一个！=自我。_head:
下一个
打印当前项目，
打印
定义添加(自身，项目):
将节点添加到标头
节点=节点(项目)
if self.is_empty():
自我。_head=node
node.next=self。_head
否则：
#添加的节点指向_head
node.next=self。_head
#移动到链表的末尾，并将结束节点的下一个指向该节点
cur=self。_head
下一个！=自我。_head:
下一个
cur.next=node
#_head指向添加的节点
自我。_head=node
定义附加(自身，项目):
在结尾处添加节点
节点=节点(项目)
if self.is_empty():
自我。_head=node
node.next=self。_head
否则：
#移动到链接列表的末尾
cur=self。_head
下一个！=自我。_head:
下一个
#将尾节点指向节点
cur.next=node
#将节点指向头部node _head
node.next=self。_head
定义插入(自身、位置、项目):
在指定位置添加节点
如果pos=0:
self.add(项目)
elif pos (self.length()-1):
自我附加(项目)
否则：
节点=节点(项目)
cur=self。_head
计数=0
#移动到指定位置的前一个位置
计数时(位置1):
计数=1
下一个
node.next=cur.next
cur.next=node
定义移除(自身，项目):
删除节点
#如果链表为空，则直接返回
if self.is_empty():
返回
#指向头部节点的点cur
cur=self。_head
pre=无
#如果头节点的元素是要查找的元素项
if cur.item==item:
#如果链表有多个节点
如果cur.next！=自我。_head:
#首先找到尾节点，并将尾节点的下一个指向第二个节点。
下一个！=自我。_head:
下一个
# cur指向尾节点。
cur.next=self。_head .下一个
自我。_head=self。_head .下一个
否则：
#链表只有一个节点
自我。_head=无
否则：
前=自我。_head
#第一个节点不会被删除
下一个！=自我。_head:
#找到要删除的元素。
if cur.item==item:
#删除
pre.next=cur.next
返回
否则：
前=当前
下一个
# cur指向尾节点
if cur.item==item:
# 尾部删除
pre.next=cur.next
定义搜索（自身，项目):
查找节点是否存在
if self.is_empty():
返回错误的
cur=自我._head
if cur.item==item:
返回真实的
下一个！=自我. head:
下一个
if cur.item==item:
返回真实的
返回错误的
if __name__==__main__ :
ll=SinCycLinkedlist()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2，4)
ll.insert(4，5)
ll.insert(0，6)
打印"长度："，ll.length()
ll.travel()
打印ll.search(3)
打印ll.search(7)
ll.remove(1)
打印"长度："，ll.length()
ll.travel()四、双向链表
一种更复杂的链表是"双向链表"或"双面链表"。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
4.1 相关操作is_empty()链表是否为空长度()链表长度旅行()遍历链表添加（项目)链表头部添加追加（项目)链表尾部添加插入（位置，项目)指定位置添加移除（项目)删除节点搜索（项目)查找节点是否存在4.2 实现类节点（对象):
双向链表节点
def __init__(self，item):
self.item=项目
self.next=无
self.prev=无
类数据链接列表(对象):
双向链表
def __init__(self):
自我. head=无
定义为空（自身):
判断链表是否为空
回归自我. head==无
定义长度（自身):
返回链表的长度
cur=自我._head
计数=0
一边诅咒！=无：
计数=1
下一个
返回计数
定义行程（自己):
遍历链表
cur=自我._head
一边诅咒！=无：
打印当前项目，
下一个
打印
定义添加（自身，项目):
头部插入元素
节点=节点（项目)
if self.is_empty():
# 如果是空链表，将_head指向结节
自我. head=node
否则：
# 将结节的然后指向_head的头节点
node.next=self ._head
# 将_head的头节点的上一个指向结节
自我. head.prev=node
# 将_head指向结节
自我. head=node
定义附加（自身，项目):
尾部插入元素
节点=节点（项目)
if self.is_empty():
# 如果是空链表，将_head指向结节
自我. head=node
否则：
# 移动到链表尾部
cur=自我._head
下一个！=无：
下一个
# 将尾节点坏蛋的然后指向结节
cur.next=node
# 将结节的上一个指向坏蛋
node.prev=cur
定义搜索（自身，项目):
查找元素是否存在
cur=自我._head
一边诅咒！=无：
if cur.item==item:
返回真实的
下一个
返回错误1，指定位置插入节点
定义插入（自身、位置、项目):
在指定位置添加节点
如果pos=0:
self.add(项目)
elif pos (self.length()-1):
自我附加（项目)
否则：
节点=节点（项目)
cur=自我._head
计数=0
# 移动到指定位置的前一个位置
计数时（位置1):
计数=1
下一个
# 将结节的上一个指向坏蛋
node.prev=cur
# 将结节的然后指向坏蛋的下一个节点
node.next=cur.next
# 将坏蛋的下一个节点的上一个指向结节
cur.next.prev=node
# 将坏蛋的然后指向结节
cur.next=node2，删除元素
定义移除（自身，项目):
删除元素
if self.is_empty():
返回
否则：
cur=自我._head
if cur.item==item:
# 如果首节点的元素即是要删除的元素
if cur.next==None:
# 如果链表只有这一个节点
自我. head=无
否则：
# 将第二个节点的上一个设置为没有人
cur.next.prev=无
# 将_head指向第二个节点
自我. head=cur.next
返回
一边诅咒！=无：
if cur.item==item:
# 将坏蛋的前一个节点的然后指向坏蛋的后一个节点
cur.prev.next=cur.next
# 将坏蛋的后一个节点的上一个指向坏蛋的前一个节点
cur.next.prev=cur.prev
破裂
cur=cur.next3，测试
if __name__==__main__ :
ll=DLinkList()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2，4)
ll.insert(4，5)
ll.insert(0，6)
打印"长度："，ll.length()
ll.travel()
打印ll.search(3)
打印ll.search(4)
ll.remove(1)
打印"长度："，ll.length()
ll.travel()
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。