面试官：说说你对链表的理解？常见的操作有哪些？

野性酷女 2022-09-12 12:41 180阅读 0赞

![b203ef926643fcec581727fd2b9ec8a3.png][]

## 一、是什么 ##

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点（链表中每一个元素称为结点）组成

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

![383379da0d8b9433c27bd84be5f4e310.png][]

节点用代码表示，则如下：

class Node {
      constructor(val) {
        this.val = val;
        this.next = null;
      }
    }

*  data 表示节点存放的数据
 *  next 表示下一个节点指向的内存空间

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到`O(1)`的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是`O(logn)`和`O(1)`

链表的结构也十分多，常见的有四种形式：

*  单链表：拥有两个特殊节点，头节点和尾节点，每个节点包含一个后继指针
 *  循环链表：跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点，首尾相连，形成了一个环
 *  双向链表：每个结点具有两个方向指针，后继指针(next)指向后面的结点，前驱指针(prev)指向前面的结点，其中节点的前驱指针和尾结点的后继指针均指向空地址NULL
 *  双向循环链表：跟双向链表基本一致，不过头节点前驱指针指向尾迹诶单和尾节点的后继指针指向头节点

## 二、操作 ##

关于链表的操作可以主要分成如下：

*  遍历
 *  插入
 *  删除

### 遍历 ###

遍历很好理解，就是根据`next`指针遍历下去，直到为`null`，如下：

let current = head
    while(current){
     console.log(current.val)
      current = current.next
    }

### 插入 ###

向链表中间插入一个元素，可以如下图所示：

![639fa33b8eb75a81f4eddadcfe5fcfe8.png][]

可以看到，插入节点可以分成如下步骤：

*  存储插入位置的前一个节点
 *  存储插入位置的后一个节点
 *  将插入位置的前一个节点的 next 指向插入节点
 *  将插入节点的 next 指向前面存储的 next 节点

相关代码如下所示：

let current = head
    while (current < position){
      pervious = current;
      current = current.next;
    }
    pervious.next = node;
    node.next = current;

如果在头节点进行插入操作的时候，会实现`previousNode`节点为`undefined`，不适合上述方式

解放方式可以是在头节点前面添加一个虚拟头节点，保证插入行为一致

### 删除 ###

向链表任意位置删除节点，如下图操作：

![d657d1f86c264d0fe21cdaae7e551e78.png][]

从上图可以看到删除节点的步骤为如下：

*  获取删除节点的前一个节点
 *  获取删除节点的后一个节点
 *  将前一个节点的 next 指向后一个节点
 *  向删除节点的 next 指向为null

如果想要删除制定的节点，示意代码如下：

while (current != node){
      pervious = current;
      current = current.next;
      nextNode = current.next;
    }
    pervious.next = nextNode

同样如何希望删除节点处理行为一致，可以在头节点前面添加一个虚拟头节点

## 三、应用场景 ##

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的`CPU`缓存、数据库缓存、浏览器缓存等等

当缓存空间被用满时，我们可能会使用`LRU`最近最好使用策略去清楚，而实现`LRU`算法的数据结构是链表，思路如下：

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头部开始顺序遍历链表

*  如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据的对应结点，并将其从原来的位置删除，并插入到链表头部
 *  如果此数据没在缓存链表中
    
     *  如果此时缓存未满，可直接在链表头部插入新节点存储此数据
     *  如果此时缓存已满，则删除链表尾部节点，再在链表头部插入新节点

由于链表插入删除效率极高，达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候，都可以使用链表

## 参考文献 ##

*  https://zh.wikipedia.org/zh-hans/%E9%93%BE%E8%A1%A8
 *  https://mah93.github.io/2019/07/19/js-linked/

\--The End--

系列正在更新：5/18

点击下方卡片解锁更多

![e9c615c83ed905744a260f5c6a05e131.png][]

创作不易，星标、点赞、在看 三连支持

[b203ef926643fcec581727fd2b9ec8a3.png]: /images/20220828/70aa880492844812a64381a7818f3c7c.png
[383379da0d8b9433c27bd84be5f4e310.png]: /images/20220828/03b9e538c4e34e42a38e74d560e02453.png
[639fa33b8eb75a81f4eddadcfe5fcfe8.png]: /images/20220828/fbca3dc050c74f7892d6e0f28c5aaba1.png
[d657d1f86c264d0fe21cdaae7e551e78.png]: /images/20220828/994ff603e2c0408d93f39131e40e93eb.png
[e9c615c83ed905744a260f5c6a05e131.png]: /images/20220828/557de550323041fc98e8e62612b3cbea.png

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关面试官：说说你对slot的理解？slot使用场景有哪些？

![format_png][] 一、slot是什么在HTML中 `slot` 元素，作为 `Web Components` 技术套件的一部分，是Web组件内的一个占

梦里梦外;/ 2022年12月28日 08:30/ 0 赞/ 168 阅读

相关面试官：说说你对DOM的理解，常见的操作有哪些？

![format_png][] 一、DOM 文档对象模型 (DOM) 是 `HTML` 和 `XML` 文档的编程接口它提供了对文档的结构化的表述，并定义了一种方式

- 日理万妓/ 2022年11月06日 12:59/ 0 赞/ 211 阅读

相关面试官：说说对React的理解？有哪些特性？

![625ade4114a82ee390b97fd97e4cf59e.png][] 一、是什么 React，用于构建用户界面的 JavaScript 库，提供了 UI

小咪咪/ 2022年10月09日 00:56/ 0 赞/ 183 阅读

相关面试官：说说你对图的理解？相关操作有哪些？

![4a3b855b4eb1cc63db13c87b3fe5f39d.png][] 一、是什么在计算机科学中，图是一种抽象的数据类型，在图中的数据元素通常称为结点，`

﹏ヽ暗。殇╰゛Y/ 2022年09月14日 00:24/ 0 赞/ 232 阅读

相关面试官：说说你对树的理解？相关的操作有哪些？

![a01ef17b4b671e13052d87772fccf5bc.png][] 一、是什么在计算机领域，树形数据结构是一类重要的非线性数据结构，可以表示数据之间一

╰+哭是因爲堅強的太久メ/ 2022年09月13日 05:21/ 0 赞/ 209 阅读

相关面试官：说说你对集合的理解？常见的操作有哪些？

![0b882c8ef88499bf387fd2c4f74214d9.png][] 一、是什么集合（Set），指具有某种特定性质的事物的总体，里面的每一项内容称作元素

心已赠人/ 2022年09月13日 00:28/ 0 赞/ 204 阅读

相关面试官：说说你对链表的理解？常见的操作有哪些？

![b203ef926643fcec581727fd2b9ec8a3.png][] 一、是什么链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结

野性酷女/ 2022年09月12日 12:41/ 0 赞/ 181 阅读

相关面试官：说说你对数据结构的理解？有哪些？区别？

![4963d675f674b30a309f45d133208907.png][] 一、是什么数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系

Myth丶恋晨/ 2022年09月12日 07:52/ 0 赞/ 224 阅读

相关面试官：说说你对 TypeScript 中高级类型的理解？有哪些？

![5f39975f9ce0336c6d0bd2c0fcdbe914.png][] 一、是什么除了`string`、`number`、`boolean` 这种基础类型

港控/mmm°/ 2022年09月11日 00:11/ 0 赞/ 195 阅读

相关面试官：说说你对操作系统的理解？核心概念有哪些？

![346a2cfc46bf4956978326668a085aa0.png][] 一、是什么操作系统（Operating System，缩写：OS）是一组主管并控制

╰+攻爆jí腚メ/ 2022年09月06日 15:16/ 0 赞/ 192 阅读