数据结构之链表(一):单向链表

马谦马谦马谦 数据结构和算法评论354字数 1575阅读5分15秒阅读模式

一、单向链表

1.1 单向链表

链表是一种线性结构,通过一个链把所有的节点都链起来,因此叫做链表。它和数组最大的不同是:数组的内存是连续的,而链表不是。数组支持随机读写,但是插入和删除麻烦,链表不支持随机读写,但是插入和删除很方便。在更多场景下,链表用途更广。

一个链表的图形示例如下,每个链表节点都包含了一个数据域和指向下一个节点指针:

数据结构之链表(一):单向链表-图片1

链表是由一系列的节点构成,从面向对象角度来说,链表和节点是两个完全不同的东西。节点是链表中的实体,而链表只是节点的抽象,它包含若干个组成链表的节点。因此,链表和节点这两个对象应该区别开来。

一个基本的单向链表支持的操作:

  • 添加节点
  • 删除节点
  • 查找节点

1.2 节点定义

一个节点的结构至少应该包含必要的数据域和next指针域,next只用用于指向下一个节点的地址。

以下是一个最简单的链表节点示例:

数据结构之链表(一):单向链表-图片2

链表节点的C++定义:

1.3 链表定义

链表是由一个个的节点构成,在它的内部只要保存链表头节点的地址,就能找到链表中所有节点地址。

因此一个链表中,只要包含头结点的地址就行了。然后根据其他的扩展,我们可能还需要用到:

  • 长度字段:O(1)的时间复杂度返回链表长度。
  • 尾结点指针:保存末尾节点的指针,尾插时O(1)的时间复杂度即可定位到尾结点。

链表的结构示意图:

数据结构之链表(一):单向链表-图片3

链表的C++定义:

所有代码使用C++完成,后面的函数无特殊说明都是类成员函数。

二、插入节点

2.1 插入逻辑

以下图为例,不考虑首尾节点状态以及插入位置,一个节点被插入的逻辑是:

  1. 设置新增节点node2的next指向为node3
  2. 修改原节点node1的next指向新节点node2
  3. 插入完成

数据结构之链表(一):单向链表-图片4

在链表类中,定义一个私有的添加节点函数add_node来完成这个插入操作:

2.2 头插法

头插法的意思是把节点插入到链表头部,这种情况下除了插入节点到链表中,还要注意的是修改链表的head节点指针。

数据结构之链表(一):单向链表-图片5

头插法函数实现:

2.3 尾插法

尾插法和头插法相对,尾插法的意思是把节点插入到链表尾部,因此,插入后也要更新尾结点指针。

数据结构之链表(一):单向链表-图片6

尾插法代码实现:

三、查找元素

3.1 查找指定值的节点

3.2 查找指定节点的前节点

在增加或删除节点之前,都要修改前节点的指针指向,因此,需要实现一个查找指定节点的头结点函数。

四、删除元素

4.1 删除逻辑

以下图为例,删除节点2的操作是:

  1. 修改节点1的next指向node3
  2. 删除node2的next指向,删除完成

数据结构之链表(一):单向链表-图片7

核心的删除代码:

4.2 删除指定节点

删除节点的一种操作是找到前节点指针,同时要注意的是,删除节点可能导致首尾指针失效,要注意更新首尾指针。

4.3 删除首尾元素

有了上面的删除指定节点函数之后,删除首尾元素的操作就变得非常简单了:

五、单元测试

5.1 头插法测试

5.2 尾插法测试

5.3 查找前一个节点测试

5.4 删除节点测试

数据结构之链表(一):单向链表-图片8

 最后更新:2020-2-14
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2018年3月25日15:14:16
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/the-singly-linked-list.html
redis源码分析:链表实现 Redis

redis源码分析:链表实现

一、链表定义 链表在redis中的使用十分广泛,例如列表的底层实现之一就是链表,包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现,只用了300+行代码...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证