线性表的链式存储结构

  • A+

上次实现了线性表的顺序存储结构

现在我们来实现线性表的链式存储结构

链式存储结构的特点是用一组任意的存储单元

存储线性表中的元素

可以是连续的也可以是不连续的

除了需要储存数据元素的信息外

还要存储它后继元素的内存地址


首先,在类中抽象一个类出来丛当结点

data用于保存数据(数据域)

next用于指向下一个结点(指针域)

这样把一个一个结点串联起来

_head是头结点

_last是尾结点

_currentLinkLength是链表的长度


初始化链表为只有一个头结点的空链表

头结点是为了操作方便和同一而设立的

它没有正真的数据意义

它也不是链表的必须要素


获取链表中特定位置的节点

在链表操作中

添加、插入、删除等都需要获取到指定位置的结点

①初始化结点go为头结点,初始化i = 0

②当go不为空时和当前结点位置i小于目标位置index时

将go结点向后推移

③直到链表元素不够(go ==null)或者到达目标结点(i == index)

返回 go结点

(这里i的大小刚好对应第i个结点)

线性表的链式存储结构


通过索引获取链表中的节点元素数据

①通过上面的方法,获取到对应索引的节点

②判断是否是空结点(索引超出了范围)或是为特殊结点头结点

③如果不是再取出数据


①要在链表中的最后面添加元素,先遍历链表找到最后一个结点

最后一个结点的next为空

②新建一个节点,赋值数据,指定next为空

③指定尾结点的next结点为新建结点

④指定尾结点为新建结点(用于快速添加)

⑤链表的长度+1

时间复杂度为O(n)


文章的开始

我声明了一个变量引用的就是尾结点

通过这个尾结点我们可以快速地向链表后面添加元素

①新建一个结点,赋值数据,指定next为空

②直接使用已有的last,设置尾结点的下一个next结点为新建结点

③指定新建结点为尾结点

④链表长度+1

时间复杂度为O(1)

需要保存尾结点的引用,增加了内存(这是小事)

线性表的链式存储结构


往链表头部添加元素

这时候头结点的作用就很大了

利用头结点可以轻松实现

①新建结点,赋值数据,指定第一个结点为新建结点的next个结点(新建结点为第一个)

②因为有尾结点的因素,需要判断一下是否为特殊情况的空链表

若果是则尾结点指定为新建的结点

③指定头结点的下一个结点为新节点(第一个)

④链表的长度+1


这个就不解释了


①找到需要插入位置结点的上一个结点

②判断这个结点时否符合(索引是否合法)

需要插入位置的结点i不能为空

③如果合法,则新建结点。赋值数据,指定next为待插入位置index的结点

就是上一个结点的next

④指定上一个结点的next结点为新建结点,完成插入

⑤链表长度+1

线性表的链式存储结构


注意这里不同于批量添加

批量添加由于有尾结点的缘故

所以他可以直接调用快速添加

每次为O(1)

如果批量插入每次也调用插入方法的话

每次都要去查找到对应位置的结点

所以每次插入都为O(n)

这里:

①找到插入位置的上一个结点

②做出对结点和索引合法性的判断

③合法则遍历插入的每个元素,为每个元素创建一个新的结点

赋值结点的数据

指定下一个结点为被插入结点(go.next)

指定上一个结点的next为新建结点

线性表的长度+1


通过索引删除链表的对应结点

①找到要删除结点的上一个结点

②判断结点的合法性(索引的合法性)

③将将要删除的结点赋值给p,取出它的数据

④指定上一个结点的next为将要删除结点的下一个

⑤将删除结点p设为null

⑥判断一下被删除的结点是否为最后一个

若是,则将尾结点设为上一个结点go

⑦线性表的长度-1,返回被删除元素

线性表的链式存储结构


这个不用说


测试

结果

线性表的链式存储结构

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: