java中的链表数据结构,数据结构链表的基本操作
目录
基础知识
1.1链表的基本结构
1.2节点类和链表节点的定义
1.3顺序打印和反向打印链表的基本操作
2.1计算链表的长度
2.2从前到后插入数据。
2.3查找和删除参考
1.基础知识1.1链表的基本结构
链表是由节点组成的，每个节点包含一个叫做cargo的基本单元，也是一个递归的数据结构。它可以保持数据的逻辑顺序，但存储空间不必按顺序存储。
如图所示：
链表的基本元素是：
节点：每个节点有两部分，左边部分叫值域，用来存储用户数据；右边部分称为指针字段，用于存储指向下一个元素的指针。Head:头节点始终指向第一个节点tail: tail始终指向最后一个节点None:链表中最后一个节点的指针字段为None，但链表也分为单向链表和单向循环链表，双向链表和双向循环链表，如图：
写一个基本程序来测试它：
1.2节点类和链表节点的定义
该类定义如下：
Classnode: def _ _ init _ _ (self，cargo=none，next=none):self . cargo=cargo self . next=next def _ _ str _ _(self):#测试基本函数，输出字符串返回str (self。cargo)打印节点( text) #由于任何值而输出文本
如何定义链表？
我们可以一次定义一个节点，如下所示：
1=节点(1)节点2=节点(2)节点3=节点(3)然后展示各个节点的关系，就OK了。
1.next=node2node2。next=node3 1.3顺序打印和反向打印
因为之前已经建立了关系，所以可以进入第一个节点，循环整个链表然后顺序打印整个链表。
print list(node):while node:print node node=node . nextprintlist(node 1)123使用递归方法进行打印。主要步骤如下：
将列表分成两部分，head:第一个元素，tail:其他元素向后打印。打印第一个元素def向后打印(lists):iflists==none:return head=lists tail=lists . next print，tail向后打印(Tail)打印头，Tail向后打印(node 1) 1 22 33 none 3 none 2 31 2其实可以更简单。
def backward(lists):if lists==None:return print backward(lists。next)printlistsprintbackward(node 1)2。链表的基本操作就是链表的基本操作，包括插入、删除等。但需要注意的是，下面的操作是针对非循环链表的，从第一个节点开始，我们不能在链表中插入none值。
2.1计算链表的长度
类节点(object):# nodeclass #函数：输入一个值data，将值改为一个节点def __init__(self，data，next=None):self . data=data self . next=next def _ _ str _ _(self):return self . data class linked list(object):def _ _ init _ _(self，Head=none): self。head=headdef _ _ len _ _ (self): #函数：进入头节点，返回链表长度curr=self。Headcounter=0而curr不为none: counter=1curr=curr.next返回插入前后的计数器2.2。
从前：
如果插入的数据为空，则返回以使用输入数据创建一个节点，并将该节点指向原始的头节点。设置该节点为头节点，时间复杂度和空间复杂度为O(1)。
Def insertToFront(self，data): #函数：输入数据，插入头节点前，改为头节点#输出：如果数据为none则为当前头节点：返回none node=node (data，self。头)自我。head=node从后面返回节点：追加
如果输入数据为空，则返回None。如果头节点为空，则直接将输入数据作为头节点遍历整个链表。直到当前节点的下一个节点为None，将当前节点的下一个节点设置为输入数据，时间复杂度为O(n)，空间为O(1)。
Def append(self，data): #函数：输入数据，如果数据为none，则作为节点插入到末尾：如果，则返回none node=node (data)。头无：自我。head=node返回节点curr _ node=self。头而curr _ node。next不是none: curr _ node=curr _ node。next=node返回node 2.3查找和删除
查找
如果搜索到的数据为空，则返回将首节点设置为当前节点；如果当前节点不为None，遍历整个链表；如果当前节点的数据与输入数据相同，则为当前节点；否则，轮到下一个节点，其可见时间复杂度为O(n)，空间复杂度为O(1)。
def find(self，data): #函数：如果数据为none，则查找链表的节点数据：返回none curr _ node=self。头而curr _ node不为none:if curr _ node . data==data:return curr _ node curr _ node=curr _ node . next return none删除1
申请两个变量。如果遇到匹配，不需要删除，直接将匹配节点的上一个节点指向匹配节点的下一个节点。因此，您需要定义一个前节点和一个当前节点。当前节点用于判断是否匹配输入数据，前一个节点用于改变链表的指向。
如果输入数据为None，返回设置头节点为前一个节点，头节点的下一个节点为当前节点，判断前一个节点是否匹配输入数据。如果是，则将首节点设置为当前节点，遍历整个链表。如果当前节点与输入数据匹配，则将前一个节点的指针指向当前节点的下一个节点。否则，移动到下一个节点的时间复杂度为O(n)，空间复杂度为O(1)。
def delete(slef，data): #如果数据为none则删除节点：如果self.head为none则返回none:如果self . head . data==data:self . head=self . head . next返回prev _ node=self . head . curr_node=self . head . next当curr _ node不为None:if curr _ node . data==data:prev _ node . next=curr _ node . next else:prev _ node=curr _ node curr _ node=curr _ node . next010-next
第二种解决方案是只定义一个变量作为当前节点，用它的下一个节点来判断是否与数据匹配。如果是，将当前节点直接指向下一个节点。
时间复杂度为O(n)，空间复杂度为O(1)。
def deleteAlt(self): #如果数据为none，则只定义一个变量来完成删除操作：如果self，则返回。头无：自性则归。head.data==data: self。头=自己。头。下次返回curr _ node=self。head while curr_node.next不为None:if curr _ node . next . data==data:curr _ node . next=curr _ node . next . next返回curr_node=curr_node.next引用
链接列表
用Python实现的数据结构和算法：链表
Python数据结构-链表
解决方案笔记本
历史提交的图片或压缩文件
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。