JS版数据结构第三篇(链表)

谁践踏了优雅 2022-05-01 12:14 196阅读 0赞

> 链表分为单链表,双链表,以及环形链表,我将分三个模块分别介绍,并有相应的题目对应讲解。

## 单链表 ##

### 定义 ###

还是按照老规矩先看一下百度百科对单链表的定义

根据以上文字我们可以得出

*  单链表是一种链式的数据结构
 *  它由一系列结点组成
 *  每个结点包含两个部分:

1.  结点元素的数据
2.  指向下一个位置的指针(next)

### 头指针head和终端结点 ###

*  单链表中每个结点的存储地址是存放在其前趋结点next域(即它前一个节点的next指针)中
 *  而开始结点无前趋，故应设头指针head指向开始结点。
 *  链表由头[指针][Link 1]唯一确定，单链表可以用头指针的名字来命名。
 *  终端结点无后继，故终端结点的指针域为空，即NULL。

想象一下,每个结点都保存着指向下一个结点的指针,这样只要给出头指针head,

你就可以根据它获取到链表中的任何一个元素了,将结点元素'连接'在一起就称之为**链表,**

是不是还蛮形象的?

接下来我们可以尝试自己设计一个单链表

### 例题-设计链表 ###

LeetCode第707题     [原题地址][Link 2]

> 设计单链表的实现。单链表中的节点应该具有两个属性：`val` 和 `next`。`val` 是当前节点的值，`next` 是指向下一个节点的指针/引用。假设链表中的所有节点都是 0-index 的。
> 
> 在链表类中实现这些功能：
> 
>  *  get(index)：获取链表中第 `index` 个节点的值。如果索引无效，则返回`-1`。
>  *  addAtHead(val)：在链表的第一个元素之前添加一个值为 `val` 的节点。插入后，新节点将成为链表的第一个节点。
>  *  addAtTail(val)：将值为 `val` 的节点追加到链表的最后一个元素。
>  *  addAtIndex(index,val)：在链表中的第 `index` 个节点之前添加值为 `val` 的节点。如果 `index` 等于链表的长度，则该节点将附加到链表的末尾。如果 `index` 大于链表长度，则不会插入节点。
>  *  deleteAtIndex(index)：如果索引 `index` 有效，则删除链表中的第 `index` 个节点。

示例:

>     MyLinkedList linkedList = new MyLinkedList();
>     linkedList.addAtHead(1);
>     linkedList.addAtTail(3);
>     linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
>     linkedList.get(1);            //返回2
>     linkedList.deleteAtIndex(1);  //现在链表是1-> 3
>     linkedList.get(1);            //返回3复制代码

题目要求我们设计一个基本的列表并实现增删改查等基础功能，在对单链表有一个基本的了解后应该很容易读懂题目,我们直接开始解题

首先我们需要建立一个链表类(构造函数),这个也就是我们要设计的链表,它包含了：

*  `_length` 用于表示链表中的节点数量
 *  `head` 分配一个节点作为链表的头
 *  `get(index)` 根据索引查找节点对应的值
 *  `addAtHead(value)` 向链表中第一个元素前添加一个节点
 *  `addAtTail(value)` 向链表中最后元素后添加一个节点  
    
 *  `addAtIndex(index,val)` 在链表中的第 `index` 个节点之前添加值为 `val` 的节点
 *  `deleteAtIndex(index)` 删除指定位置的节点

// 链表类 class MyLinkedList{ constructor(){ // 头指针初始为空 this.head = null // 长度初始为0 this._length = 0 } get (index) { } addAtHead (val) { } addAtTail (val) { } addAtIndex (index, val) { } deleteAtIndex (index) { }}复制代码

然后我们需要一个节点类(构造函数),用来保存每个节点的value以及next属性

*  `data` 存储数据
 *  `next` 指向链表中下一个节点的指针

// 节点类 class Node(value) { // 实例化时赋值 this.val = value // next指针初始为null this.next = null }复制代码

两个构造函数已经写好了,接下来我们开始实现以下它的功能

*  **方法1:  addAtHead(val) **

在链表的第一个元素之前添加一个值为 `val` 的节点,我们需要

1.  用一个变量oldHead保存当前链表中的头指针head
2.  以val值实例化一个新的node节点,并将其作为新的头指针head
3.  将新的头指针的next指向oldHead

代码如下:

addAtHead(val){
        let oldHead = this.head
        this.head = new Node(val)
        this.head.next = oldHead
        this._length++
    }复制代码

*  **方法2：addAtTail(val)**

向链表中最后元素后添加一个节点，我们需要

1.  以val值实例化新的node节点
2.  根据头指针head遍历到链表中最后一个元素
3.  将最后一个元素的next指针指向新的node节点

代码如下:

addAtTail (val) { let node = new Node(val) // 用一个变量保存链表最后一个节点 初始值为头指针 let last = this.head // 遍历找到最后一个节点 while(last && last.next){ last = last.next } // 如果非空链表 if(last){ // 将最后一个节点指向插入的节点 last.next = node }else{ // 若为空链表 将头指针指向新插入节点 this.head = node } this._length++ }复制代码

*  **方法3：get(index)**

根据索引查找链表中的节点,我们需要:

1.  声明一个变量currentIndex记录遍历的次数,初始为0
2.  根据头指针head的next指针遍历链表,每查询一次next,将currentIndex加1
3.  直到currentIndex与要查询的index相等

代码如下:

get(index){ // 记录遍历次数 初始为0 let currentIndex = 0 // 记录遍历到的节点 初始为head let cur = thi.head // 根据题意, 索引无效则返回 -1 if(index < 0 || this._length < index + 1){ return -1 } // 直到查找到索引为index的元素为止 while (cur){ if(currentIndex = index){ return cur.val } } cur = cur.next currentIndex++ }复制代码

*  **方法4：addAtIndex(index,val)**

从索引位置为index的前端插入值为val的元素,我们需要:

1.  以val值实例化一个新node结点
2.  找到要插入元素的前一位元素,改变它的next指针,指向新node结点
3.  将新插入的node结点的next指针指向原位置的结点

但是代码中我们要考虑到特殊的一些情况(在头部或尾部插入,链表为空等情况)

代码如下：

addAtIndex(index, val){ // 若索引在0位之前 直接调用addAtHead方法 if(index <= 0){ return this.addAtHead(val) } // 如果index值大于0 if(index >= 0 && index <= this._length){ // 以val值实例化新结点 let node = new Node(val) // 记录当前遍历的结点,初始为head let cur = this.head // 记录遍历次数 let currentIndex = 0 // 记录当前遍历结点的next指针 let next while(cur){ if(currentIndex === index - 1）{ // 此时cur为要插入结点的前方结点 // 用next保存插入元素前方结点的原next指针 next = cur.next cur.next = node node.next = next this._length++ break } cur = cur.next currentIndex++ } } }复制代码

*  **方法5：deleteAtIndex(index)**

接下来实现我们的最后一个方法,根据索引删除元素,我们需要：

1.  通过head指针遍历到index位置的元素
2.  用变量将根据索引查找到的要删除的元素下一位记录下来
3.  将要删除元素的前一位的next指针指向要删除元素的下一位

代码如下:

deleteIndex(index){ // 若索引有效 if(index >=0 && index <= this._length -1){ let cur = this.head // 若删除索引为0的元素,只需将head指针向下移动一位,不需要考虑删除元素之前结点的指针 if(index === 0){ this.head = cur.next this._length-- }else{ // 若删除索引非0 let currentIndex = 0 let next while(cur){ if(currentIndex === index-1){ // 此时cur为要删除元素的前一个结点 next = cur.next.next // 先将删除元素清空 避免内存泄漏 cur.next = null cur.next = next this._length-- } cur = cur.next currentIndex++ } } } }复制代码

这样我们就实现了一个完整的实现增删改查功能的单链表了,完整代码如下:

class Node { constructor (val) { this.value = val this.next = null } } class MyLinkedList { constructor () { this._length = 0 this.head = null } addAtHead (val) { let originHead = this.head this.head = new Node(val) this.head.next = originHead this._length++ } addAtTail (val) { let last = this.head let node = new Node(val) while (last && last.next) { last = last.next } if (last) { last.next = node } else { this.head = node } this._length++ } get (index) { let currentIndex = 0 let cur = this.head if (index < 0 || this._length < index + 1) { return -1 } while (cur) { if (currentIndex === index) { return cur.value } cur = cur.next currentIndex++ } } // 特定位置插入 addAtIndex(index, val){ // 若索引在0位之前 直接调用addAtHead方法 if(index <= 0){ return this.addAtHead(val) } // 如果index值大于0 if(index >= 0 && index <= this._length){ // 以val值实例化新结点 let node = new Node(val) // 记录当前遍历的结点,初始为head let cur = this.head // 记录遍历次数 let currentIndex = 0 // 记录当前遍历结点的next指针 let next while(cur){ if(currentIndex === index - 1）{ // 此时cur为要插入结点的前方结点 // 用next保存插入元素前方结点的原next指针 next = cur.next cur.next = node node.next = next this._length++ break } cur = cur.next currentIndex++ } } } // 按索引删除 deleteAtIndex (index) { if (index >= 0 && index <= this._length - 1) { let cur = this.head // 如果删第0位 if (index === 0) { this.head = cur.next this._length-- } else { let currentIndex = 0 let next while (cur) { if (currentIndex === index - 1) { // 此时cur是被删除元素的前一位 next = cur.next.next // 先将删除元素清空 避免内存泄漏 cur.next = null cur.next = next this._length-- } cur = cur.next currentIndex++ } } } } } 复制代码

## 循环链表 ##

在学习双向链表之前,我们先来看一下循环链表

### 定义 ###

百度百科是这样定义的

其实相对于单链表,只是链表的最后一位元素的next指向了头指针

可以说是再简单不过了。

### 例题-环形链表 ###

LeetCode-141题 [原题地址][Link 3]

> 给定一个链表，判断链表中是否有环。
> 
> 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。

示例1:

>     输入：head = [3,2,0,-4], pos = 1
>     输出：true
>     解释：链表中有一个环，其尾部连接到第二个节点。
>     
>     复制代码

示例2:

> 输入：head = \[1,2\], pos = 0                                                                                            输出：true                                                                                                                      解释：链表中有一个环，其尾部连接到第一个节点。

注意:这个题目里面的环形链表和我们定义中的循环有所不同,循环链表的定义是链表的最后一位元素一定指向头指针,而这里题目中的是尾指针可能指向链表中的任何一个非尾指针。

那我们如何判断是否有环呢?

我们正常的思路一定是从头指针head开始遍历这个链表,一直到它长度的最后一位,如果它的next指针一直不为Null,那么它就是有环的,这个时候问题来了,由于这个链表并不是我们自己设计的,他将链表传进来时是已经处理好的状态,他并没有声明length属性,如果这样遍历的话他并没有截止条件,会造成一个死循环,这里也困扰了我很久。

于是我看了一下这道题的评论,发现了一种很巧妙的'快慢指针'的解法。

我们先来看一下下面这个动画

我们先分别声明两个快慢指针,

初始位置都指向head,控制快指针每次移动两位,慢指针每次移动一位。

在上边的这个动画中快慢指针同时移动三次的时候fast指针指向了值为2的结点,,slow指针指向了。大家想象一下,当移动第四次的时候,他们会同时指向值为7的位置(原谅我动画只录到第三次)。

那么是不是可以认为只要有环,两个指针就会有指向同一个结点的情况呢?

根据这样的思路,我们可以完成以下代码:

var hasCycle = (head) => { let fast = head let slow = head while( fast != null && fast.next != null){ slow = slow.next fast = fast.next.next if( slow === fast){ return true } } return false }复制代码

## 双向链表 ##

### 定义 ###

其实说白了双向链表就是在单链表的基础上每个结点多了一个指向上一个结点的指针,了解完了单链表和环形链表,双向链表应该是不难理解了。

### 实现双向链表 ###

双项链表与单链表的结构类似,这里就不过多阐述了,在这里给出实现一个基本双向链表的源码供大家参考。

## 参考 ##

> 疯狂的技术宅- JavaScript数据结构:单向链表与双向链表      [原文链接][Link 4]
> 
> 百度百科
> 
> LeetCode原题

## 总结 ##

今天我们用js分别实现了单链表,循环链表,双链表的实现以及相关的LeetCode真题,相信以后在面试中再次碰到有关链表这种数据结构的题目你一定会游刃有余。

下一篇我们将介绍矩阵。

[**上一篇 **][Link 5]

[JS版数据结构第二篇(队列) ][Link 5]

转载于:https://juejin.im/post/5cc41225e51d456e6b5d7e2e

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E6%258C%2587%25E9%2592%2588
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fdesign-linked-list%2F
[Link 3]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Flinked-list-cycle%2F
[Link 4]: https://link.juejin.im?target=https%3A%2F%2Fsegmentfault.com%2Fa%2F1190000010345293
[Link 5]: https://juejin.im/post/5cbf0f8de51d456e5e035f5b