链表

8/8/2020 数据结构与算法链表算法

# 什么是链表?

链表(Linked list)也是一种线性表数据结构。它是一种在物理上非连续、非顺序的数据结构,由若干节点所组成,节点之间的逻辑顺序通过指针的链接次序实现。

理解几个关键词:

# 1.非连续、非顺序

链表在物理内存中存储并不像数组一样需要整块的连续空间,而是散落在各个地方,哪里有空就存在哪里。(图中红色表示链表的存储空间,灰色表示已占用空间,绿色表示未占用空间)

# 2.若干节点

链表在物理存储结构上由零零散散的内存块组成,这些散落在各地的内存块被称为节点,我们把第一个节点成为头节点,最后一个节点称为尾节点

# 3.指针

指针将链表各节点串联起来,形成有逻辑顺序的数据结构。

每个节点包含数据和指针两部分,指针用来存储下一个节点的地址,我们把记录下个结点地址的指针叫 后继指针 next。其中,链表基地址指向头节点,尾节点指针指向 null。

含义

将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。

示例

p -> next = q 表示p节点的后继指针存储了q节点的内存地址。

p -> next = p -> next -> next 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

# 链表的基本操作

# 1.查询

链表的查询不像数组可以使用寻址公式随机访问,因为它是非连续、非顺序存储在内存中,只能通过头节点依次向后遍历,就像是玩寻宝游戏一样,每一个线索都指向下一个线索,直到链表的最后。

比如要查找 p节点,只能从头节点开始依次往下查找:

链表只能按顺序进行访问,最坏情况时间复杂度为O(n)。

# 2.更新

链表更新同数组类似,直接更新节点中的数据即可。

不考虑查找节点的时间,单纯更新操作时间复杂度为O(1)。

# 3.插入

链表的插入不像数组需要对数据进行搬移工作,由于是通过指针将各节点串联起来的,插入一个节点只需要改变相关指针的指向即可,非常高效。

如图,在 b 节点后面插入 x 节点,只需要将 x 节点的指针指向 b节点后面的 c 节点,然后将 b 节点的指针指向 x 节点即可。

用伪代码表示为:

x->next = b->next
b->next = x
// 注意:注意两行代码的顺序,如果先写第2行代码会造成内存泄漏
1
2
3

不考虑查找节点的时间,单纯插入操作时间复杂度为O(1)。

# 4.删除

链表删除操作同插入操作类似,只需要改变相关指针的指向即可。

如图,要删除 b 节点后面的 c 节点,只需要b 节点的指针指向 d 节点即可,这样 c 节点从链条上断裂成为一个游离的节点,相当于从链表中删除。被删除的 c 节点由于未被引用,在像 java 这样的语言中,就会被GC(垃圾回收)掉。

用伪代码表示为:

b->next = b->next->next
1

不考虑查找节点的时间,单纯删除操作时间复杂度为O(1)。

# 边界情况处理

前面插入删除操作都是一般情况下的处理,假如遇到边界情况则需要做特殊处理,比如向空链表中插入数据,删除链表最后一个节点等等。

如果向空链表中插入数据 x ,就不能按照上面的插入伪代码来写了,需要做判断:

if(head == null){ // head表示链表的头节点
	head = x
}
1
2
3

再来看删除操作,如果链表仅剩最后一个节点,也需要做特殊的处理:

if(head->next = null){
   head = null
}
1
2
3

可以看到,针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理,这样代码会显得不简洁而且容易出错,那么如何解决这个边界问题呢?接下来 哨兵模式 就要登场了。

# 利用哨兵模式来简化边界问题

为了解决上面提到的链表边界问题,我们可以引入一个哨兵节点作为链表的头节点,哨兵节点一直存在,不参与业务逻辑也不存储数据。我们把带有哨兵节点的链表叫带头链表,把没有哨兵节点的链表叫不带头链表

由于哨兵节点一直存在,插入第一个节点和插入其他节点,删除最后一个节点和删除其他节点,都可以统一为相同的代码逻辑,不用再特殊判断了,在数据量较大的链表中,少去这个判断步骤能节省不少时间。

在写链表的时候,边界问题非常容易出错,可以参考以下来检查:

  • 如果链表为空时,代码是否能正常工作?

  • 如果链表只包含一个结点时,代码是否能正常工作?

  • 如果链表只包含两个结点时,代码是否能正常工作?

  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

# 链表的几种形态

# 1.单链表

单链表是最基础、最常用的链表形式,其他链表也是根据单链表变种而来。

# 2.循环链表

循环链表是一种特殊的单链表,它跟单链表唯一的区别就在尾结点。单链表的尾节点指针指向 null ,而循环链表的尾节点指针指向头节点,首尾呼应,形成一个环形结构。

# 3.双向链表

单链表只有一个方向,每个节点只有一个后继指针指next指向下一个节点。而双向链表除了有后继指针指向下一个节点外,还有一个前驱指针prev指向上一个节点。双向链表也是开发中常用到的数据结构。

# 4.双向循环链表

将双向链表的首尾相连,就形成了双向循环链表。双向循环链表尾节点的后继指针指向头节点,头节点的前驱指针指向尾节点,形成一个双环。

# 链表和数组时间复杂度比较

# 实际应用

以下代码用 java 作为示例,链表节点用 Node 类表示如下:


1

# 1.如何用链表来实现LRU缓存淘汰算法?

常见缓存淘汰策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

思路:

用一个单链表来存储缓存数据,越靠近头节点的数据是越新访问的。当访问某个数据时,遍历链表:

  • 如果该数据存在链表中,删除该数据所在的节点,然后将该节点插入到链表头部
  • 如果该数据不在链表中,分两种情况:
    1. 缓存未满,直接插入新数据至链表头部
    2. 缓存已满,删除链表尾节点,然后插入新数据至链表头部

# 2.单链表反转

# 3.链表中环的检测

# 4.两个有序的链表合并

# 5.删除链表倒数第 n 个结点

# 6.求链表的中间结点

# 7.后面补充