动画：面试如何轻松手写链表？

一时失言乱红尘 2023-06-06 07:51 92阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 不甘平凡的码农

来源公众号 | 不甘平凡的码农

写在前边

对于数组的学习呢，在前端中，最重要的就是数组的一些方法的使用，数组的截取、查找、反转等常用的方法；除此之外，数组另一个稍微难点就是算法题。上一周我又拿起《剑指`offer`》把关于数组的算法题刷了一遍，又总结了很多的做题技巧和有关数组的解题思路，后期会分享。

那对于链表呢，我们在项目中用到的不如数组频繁，但是面试是个重点，为什么面试官喜欢考我们链表呢？想必大家对这个问题很感兴趣，因为链表灵活、涉及到的边界条件多，又加上很多细节点，对应聘者是一个考验。

不料，暑假参加的第一个公司的就让我手写一个双向链表，并完成插入数据和删除数据的操作。当时我很蒙蔽，懵逼的不是思路，而是手写，虽然写出来了，但是很多边界条件和代码规范自我感觉不好，所以有了这些细心的总结。那么今天的主题就是徒手写链表，应聘者该如何下手？

我们通常写链表准备应聘的时候，通常背加上理解，但是过了几天又让你写。就会陌生了，虽然有点思路。还是模模糊糊，小鹿也有这个记性的“毛病”，“有毛病”就要治，怎么治？我们必须在脑海里形成一套可行的步骤和方法，在遇到手写就不用手忙脚乱，而是稳稳当当，从头到尾写出一个漂亮的链表结构及操作。

思维导图

![640?wx\_fmt=png][640_wx_fmt_png]

**熟悉结构**

首先我们要知道链表的结构以及每个节点的结构，这是我们手写链表的第一步，也是学习链表的第一步。我们知道，每个链表时这样表示的：

![640?wx\_fmt=png][640_wx_fmt_png 1]

那每个节点结构是由**数据域**和**指****针域**组成，数据域是存放数据的，而指针域存放下一结点的地址。

![640?wx\_fmt=png][640_wx_fmt_png 2]

我们可以通过数据域访问到我们要的数据，而通过指针域访问到当前结点以后的结点，那么将这些结点串起来，就是一个链表。

那么用代码怎么来表示呢？

我们通常会用到函数，我们如果将一个函数抽象成一个结点，那么我们给函数添加两个属性，一个属性是存放数据的属性`data`，另一个属性是存放指向下一个结点的指针属性`next`。

你可能会问，如果我们有成千上万个结点，要定义成千上万个函数？有一个函数叫做构造函数，想必大家都听说过，声明一个构造函数就可以创造出成千上万个结点实例。

1function Node(data){
    2    this.data = data;
    3    this.next = null;
    4}

还有一个方法就是使用类的概念，在`JavaScript`中，类的概念在`ES6`才出现，使用 `Class` 来声明一个类，我们可以为类添加两个属性，同上，一样可以创造出多个结点实例。

1class Node{
    2    constructor(data){
    3        this.data = data;
    4        this.next = null;
    5    }
    6}

**理清思路**

如果你把链表的结构搞得明明白白了，恭喜你，成功的进入第二关，但是你只超越了百分之`20`的人，继续加油。

既然链表的结构弄明白了，那么我们开始理思路，我们就先拿最简单的单链表开刀，我们要完成两个操作，插入数据和删除数据。

如果我想插入数据，你可能会问，往哪里插呢？有几种插入的方法？

开始想，插入到单链表的头部算一种。

![640?wx\_fmt=gif][640_wx_fmt_gif]

然后插入到单链表的中间算一种。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

插入到单链表尾部又算一种。

![640?wx\_fmt=gif][640_wx_fmt_gif 2]

所有可能的情况就三种。那么删除呢？想必你也想到了，也一共三种，删除头部、删除中间部分、删除尾部。

如果你觉的现在可以写代码了，那你就错了，虽然我们的思路非常清晰，但是面试官仅仅考我们思路吗？其实这一关你只打败了百分之`50%`的人，最重点、最主要的是在下一个部分，边界条件。

**边界条件**

边界条件是这五个步骤最容易犯错的一部分，因为通常考虑的不全面，导致了最后的面试未通过。如果想做好这一部分，也不难，跟着小鹿的方法走。

**3.1 输入边界**

首先我们先考虑用户输入的参数，比如传入一个链表，我们首先要判断链表是否为空，如果为空我们就不能让它执行下边的程序。再比如插入一个结点到指定结点的后边，那么你也要判断输入的结点是否为空，而且还要判断该结点是否存在该链表中。对于这些输入值的判断，小鹿给他同一起个名字叫做输入边界。

**3.2 特殊边界**

特殊边界考虑到一些特殊情况，比如插入数据，我们插入数据一般考虑到插入尾部，但是突然面试官插入到头部，插入尾部的代码并不适用于插入到头部，所以呢需要考虑这种情况，删除节点也是同样思考。其实特殊边界最主要考虑到一些逻辑上的特殊情况，考察应聘者的考虑的是否全面。小鹿给他起个名字叫做特殊边界。

**手写代码**

**4.1 定义结点**

![640?wx\_fmt=png][640_wx_fmt_png 2]

1class Node{
    2    constructor(data){
    3        this.data = data;
    4        this.next = null;
    5    }
    6}

**4.2 增加结点**

咱们就以单链表中部添加数据为例子，分解成每个步骤，每个步骤对应代码如下：

**1、**保存临时地址（`4`结点的地址）,需要进行遍历查找到`3`结点，也就是下列代码的`currentNode` 结点。

![640?wx\_fmt=gif][640_wx_fmt_gif 3]

1//先查找该元素
    2let currentNode = this.findByValue(element);
    3// 保存 3 结点的下一结点地址（4 结点的地址）
    4let pre = currentNode.next

**2、**创建新结点，将新结点（`5`结点）的指针指向下一结点指针（`4`结点地址，已经在上一步骤保存下来了）

![640?wx\_fmt=gif][640_wx_fmt_gif 4]

1let newNode = new Node(value);
    2newNode.next = pre;

**3、**将`3` 的结点地址指向新结点（`5`结点）

![640?wx\_fmt=gif][640_wx_fmt_gif 5]

1 currentNode.next = newNode;

以上步骤分析完毕，剩下的两个在头部插入和在尾部插入同样的分析方式，将这两个作为练习题，课下自己试一试这个步骤。

**4.3** **删除节点**

删除节点也分为三种，头部、中部、尾部，咱们就删除中间结点为例进行删除，我们详细看步骤操作。

我们先看删除的全部动画，然后再分步拆分。

![640?wx\_fmt=gif][640_wx_fmt_gif 6]

断开`3`结点的指针（断开`3`结点相当于让`2`结点直接指向`4`结点）

![640?wx\_fmt=gif][640_wx_fmt_gif 7]

1 let currentNode = this.head;
     2 // 用来记录 3 结点的前一结点
     3 let preNode = null;
     4 // 遍历查找 3 结点
     5 while(currentNode !== null && currentNode.data !== value){
     6        // 3 结点的前一结点
     7        preNode = currentNode;
     8        // 3 结点
     9        currentNode = currentNode.next;
    10}

让结点`2`的指针指向`4`结点，完成删除。

![640?wx\_fmt=gif][640_wx_fmt_gif 8]

1preNode.next = currentNode.next;

剩下的删除头结点和删除尾结点同样的步骤，自己动手尝试下。

所有代码实现：

1/**
      2 * 2019/3/23
      3 * 公众号:「一个不甘平凡的码农」
      4 * @author 小鹿
      5 * 功能：单链表的插入、删除、查找
      6 * 【插入】：插入到指定元素后方
      7 * 1、查找该元素是否存在？
      8 * 2、没有找到返回 -1
      9 * 3、找到进行创建结点并插入链表。
     10 * 
     11 * 【查找】：按值查找/按索引查找
     12 * 1、判断当前结点是否等于null，且是否等于给定值？
     13 * 2、判断是否可以找到该值？
     14 * 3、没有找到返回 -1；
     15 * 4、找到该值返回结点；
     16 * 
     17 * 【删除】：按值删除
     18 * 1、判断是否找到该值？
     19 * 2、找到记录前结点，进行删除；
     20 * 3、找不到直接返回-1；
     21 */
     22//定义结点
     23class Node{
     24    constructor(data){
     25        this.data = data;
     26        this.next = null;
     27    }
     28}
     29
     30//定义链表
     31class LinkList{
     32    constructor(){
     33        //初始化头结点
     34        this.head = new Node('head');
     35    }
     36
     37    //根据 value 查找结点
     38    findByValue = (value) =>{
     39        let currentNode = this.head;
     40        while(currentNode !== null && currentNode.data !== value){
     41            currentNode = currentNode.next;
     42        }
     43        //判断该结点是否找到
     44        console.log(currentNode)
     45        return currentNode === null ? -1 : currentNode;
     46    }
     47
     48    //根据 index 查找结点
     49    findByIndex = (index) =>{
     50        let pos = 0;
     51        let currentNode = this.head;
     52        while(currentNode !== null && pos !== index){
     53            currentNode = currentNode.next;
     54            pos++;
     55        }
     56        //判断是否找到该索引
     57        console.log(currentNode)
     58        return currentNode === null ? -1 : currentNode;
     59    }
     60
     61    //插入元素(指定元素向后插入)
     62    insert = (value,element) =>{
     63        //先查找该元素
     64        let currentNode = this.findByValue(element);
     65        //如果没有找到
     66        if(currentNode == -1){
     67            console.log("未找到插入位置!")
     68            return;
     69        }
     70        let newNode = new Node(value);
     71        newNode.next = currentNode.next;
     72        currentNode.next = newNode;
     73    }
     74
     75    //根据值删除结点
     76    delete = (value) =>{
     77        let currentNode = this.head;
     78        let preNode = null;
     79        while(currentNode !== null && currentNode.data !== value){
     80            preNode = currentNode;
     81            currentNode = currentNode.next;
     82        }
     83        if(currentNode == null) return -1; 
     84        preNode.next = currentNode.next;
     85    }
     86
     87     //遍历所有结点
     88    print = () =>{
     89        let currentNode = this.head
     90        //如果结点不为空
     91        while(currentNode !== null){
     92            console.log(currentNode.data)
     93            currentNode = currentNode.next;
     94        }
     95    }
     96}
     97
     98//测试
     99const list = new LinkList()
    100list.insert('xiao','head');
    101list.insert('lu','xiao');
    102list.insert('ni','head');
    103list.insert('hellow','head');
    104list.print()
    105console.log('-------------删除元素------------')
    106list.delete('ni')
    107list.delete('xiao')
    108list.print()
    109console.log('-------------按值查找------------')
    110list.findByValue('lu')
    111console.log('-------------按索引查找------------')
    112list.print()

**测试用例**

其实这里的测试用例主要用于判断我们写的程序到底对不对，我们一般都会输入一个自己认为的情况进行测试，这是错误的做法。程序最容易出错的还是边界情况考虑不全面导致的，所以，我们为了能够测试程序的全面性，所以我们要按照以下步骤进行全面性的测试。

**5.1** **普通测试**

普通测试就是输入一个正常的值，比如单链表中插入数据

**5.2** **特殊测试**

特殊输入可以参照上边边界条件中的特殊边界进行测试，比如在头部插入数据，在尾部插入数据等特殊情况的测试。

**5.3** **输入测试**

对于输入测试的内容参考上边边界条件中的输入边界，比如：输入一个空链表测试一下程序能否正常的运行。

**小结**

做一个小结。今天的手写链表主要从五部分下手，从前到后依次为熟悉结构、理清思路、手写代码、测试用例。以后无论手写什么代码，有五步走，对于面试完全没有问题啦。

通过小鹿总结手写链表的方法，不用刻意去背，只要把思路理清楚，边界条件考虑全面，就不用去背，重复的练习。今天的内容就到这里了，如果觉得有帮助，转发文章让更多人看到是对小鹿最大的支持，非常感谢。

![640?][640]

**有热门推荐?**

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20230601/803df41cec144afc878e7da2d2790c76.png
[640_wx_fmt_png]: /images/20230601/32dfe54b7aef4686a0fc3c8da7c392da.png
[640_wx_fmt_png 1]: /images/20230601/54183c0bebcd4930a124d157d1e47ecd.png
[640_wx_fmt_png 2]: /images/20230601/0a0914f29bed431d90d255be02478617.png
[640_wx_fmt_gif]: /images/20230601/a7ab98ae72fa486b9e022c421327182c.png
[640_wx_fmt_gif 1]: /images/20230601/6cc85933127b43b6a14fec91eec4241d.png
[640_wx_fmt_gif 2]: /images/20230601/35aa49493d554f01aa59b7799dd02892.png
[640_wx_fmt_gif 3]: /images/20230601/4d4268f9c9b64a51b5f1055005eaa54c.png
[640_wx_fmt_gif 4]: /images/20230601/41dbb53ba9704e28b4fc01ea26cd37bb.png
[640_wx_fmt_gif 5]: /images/20230601/662ba75e31bc42c089ef43a4c50ea4f6.png
[640_wx_fmt_gif 6]: /images/20230601/2e0819b9d3b245cb9d1655245b4ab5dc.png
[640_wx_fmt_gif 7]: /images/20230601/04dc897c8acc4fc2b8bf604e96547b81.png
[640_wx_fmt_gif 8]: /images/20230601/7cce91a587e641ecbe549186b897a360.png
[640]: /images/20230601/8e4a2eeb07aa481784b4a5d810a6248c.png
[640_wx_fmt_jpeg 1]: /images/20230601/2657377a7022482f8686d8346e72cc0e.png