【戏玩算法】05-五分钟8张图带你快速了解[链表]

Hi~，我是 一碗周，一个在舒适区垂死挣扎的前端，如果写的文章有幸可以得到你的青睐，万分有幸~

🫐 写在前面

前面我们讨论了栈和队列这两个数据结构，这篇文章来讨论一下链表这个数据结构。

🍓 什么是链表

链表就是一种线性的数据结构，链表的存储时不连续的，它通过next指针连接在一起，如下图所示：

正如上图所示，链表将任意的一组数据进行连接，为了将这些数据进行连接，在每个数据元素中需要存储下一个元素的地址，它有一个官方的名字——后继指针****。

上图中这个链表叫做单链表，还有双向循环链表以及循环链表。

🍉 JavaScript中的链表

JavaScript中并没有链表，但是我们可以通过对象模拟链表，示例代码如下：

// 随意定义一些元素
const a = { value: 'a', next: null }
const b = { value: 'b', next: null }
const c = { value: 'c', next: null }
const d = { value: 'd', next: null }

// 实现链表
a.next = b
b.next = c
c.next = d

上面的代码就是要给最简单的链表，画成图是下面这个样子：

🍒 链表的基本操作

现在我们来介绍一下链表的一些基本操作，包括遍历、查找、插入、删除操作。

🍌 遍历链表

遍历列表我们可以定义一个指针，用于记录当前遍历到的元素，在循环中一直将指针后移，即可实现，示例代码如下：

let p = a // p 指向链表的头部
while (p) {
  console.log(p.value)
  p = p.next
}

运行过程如下：

🍍 删除链表元素

删除单链表中的元素存在两种情况，第一种就是知道要删除元素的上一个元素，这时候删除就比较简单了，直接将上一个的next指向下一个next，如下图：

还有一种情况就是不知道上一个元素是什么，这个时候需要进行两步操作：

• 将删除元素的下一个元素的值赋值给当前元素
• 删除下一个元素

如下图所示：

现在我们可以利用前面学习的内容，在力扣上做一个算法题，它的题号是83，题目【删除排序链表中的重复元素】，题目描述是给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

上图中就是这个题目需要做的事情。

题目分析：

• 首先我们需要遍历这个列表，并判断当前与下一个是否相等
• 如果相等将删除元素
• 如果不相等将指针指向下一个

实现代码如下：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head
    while (p && p.next) { // 判断p是否为null以及p.next是否存在，p.next不存在说明他是最后一个节点
        if (p.val === p.next.val) {
            p.next = p.next.next
        }else {
            p = p.next
        }
        
    }
    return head
};

运行过程如下图：

🍑 插入元素

现在我们来学习如何实现在链表插入元素，还是之前那段代码：

// 随意定义一些元素
const [a, b, c, d] = [
  { value: 'a', next: null },
  { value: 'b', next: null },
  { value: 'c', next: null },
  { value: 'd', next: null },
]
const e = { value: 'e', next: null }

// 实现链表
a.next = b
b.next = c
c.next = d

现在我们在b和c之间插入元素e，操作步骤如下：

1. 我们将e的next指向c，确保原来的链表不断；
2. 我们将b的next指向e，就实现了元素的插入

图解如下：

🍎 写在最后

本篇文章到这就结束了，制图不易，求个赞~

本专栏采用JavaScript作为编程语言，从前端的角度去介绍数据结构与算法，如果对你所有帮助，可以点个关注支持一下啊~