本文共 6175 字，大约阅读时间需要 20 分钟。

菜鸟昨天就准备写这个的，但是昨天下午有事出来了，现在在亲戚家学习，虽然是带伤奔波，但是感觉还不错。而且菜鸟认识了一个一类大学的朋友，知道了原来大三下学期就可以直接投简历进大厂，想想就激动o(* ￣▽￣ *)ブ

好了话不多说，开始艰难的敲代码之旅吧！

一、js单链表代码（增删改查）

function LinkedList() {       let Node = function (element) {           this.element = element;        this.next = null;    }    let head = null;    let length = 0;//length要记得++和--	//向链表插入值（尾插法，和输入顺序一致）    this.append = function (element) {           let node = new Node(element);        let current = head;        if (head === null) {               head = node;        } else {               while (current.next) {   //读者可以分析，为什么不能写current？会产生断链                current = current.next;            }            current.next = node;        }        length++;        console.log(head);    }	//移除指定位置的值    this.removeAt = (position) => {           if (position > -1 && position < length) {               let index = 0,//赋值在判断之后执行，可以减少不必要的损耗                current = head,                previous;            if (position === 0) {   //这里===0的情况要谨记                head = current.next;            } else {                   while (index++ < position) {                       previous = current;                    current = current.next;                }                previous.next = current.next;            }            length--;            return current.element;        } else {               return false;        }    }	//修改指定元素的值    this.chanceAt = (position, element) => {           if (position > -1 && position < length) {               let index = 0,                current = head;            while (index++ < position) {                   current = current.next;            }            current.element = element;        } else {               return -1;        }    }	//寻找元素位置    this.find = (element) => {           let index = 0,            current = head;        while (index++ < length) {   //current也可以            if (current.element === element) {                   return index;            }            current = current.next;        }    }	//在指定位置插入值    this.appendAt = (position, element) => {           if (position > -1 && position <= length) {   //这里是<=length,因为可以插在最后            let index = 0,                current = head,                previous;            let node = new Node(element);            if (position === 0) {                   node.next = head;                head = node;            } else {                   while (index++ < position) {                       previous = current;                    current = current.next;                }                previous.next = node;                node.next = current;            }            length++;            return true;        } else {               return false;        }    }	//将单链表转换为字符串    this.toString = function () {           let current = head,            string = "";        while (current) {               string += current.element + "  ";//表达式 A+=B 会进行 A = A + B; 也就是js的加法运算            current = current.next;        }        return string;    }}let list = new LinkedList();

使用方式

相信很多初学者都有一个疑问，这个js在哪里调试呀？我写出来了，但是只知道html页面可以在浏览器显示，那js咋搞？

这里菜鸟说一个最简单的办法，还是创建一个html界面，然后再创建一个js，页面啥也不用写，只需要引用一下js就好，eg:

然后直接在浏览器运行该页面，打开f12，进入console就好。操作就看你js代码里面有什么了，这里菜鸟拿上面的单链表举个例子，eg:

二、如何写出链表的技巧

这里菜鸟还是说一下，其实菜鸟到现在为止，连最简单的单链表都写不出来，只能怪菜鸟上数据结构的时候确实没怎么打代码。如果你也仅仅只是上课听听讲，似懂非懂，然后下课不打，那菜鸟直截了当的告诉你，你可能也无法快速正确的打出代码。（不管什么语言都一样）

想学好数据结构这个东西，菜鸟感觉也确实没什么捷径，等一下写的也只是一些帮助你更好的理解和写出代码的技巧，如果你想只看这些技巧就掌握数据结构，那你还是不要看了。

菜鸟感觉技不技巧都是虚的，最重要的就是自己打，打到自己能默写，然后默写到自己写了上一行，下一行代码的思路、原理都直接出现在脑子里，那么菜鸟相信，你不需要任何技巧，代码都是信手捏来。

菜鸟希望读者，花一个星期或者几天，就专门抽一些时间，不停的敲，不停的练，直到达到我上面说的程度，菜鸟也会这么干，等我能行如流水的默写了，我才会更新下一节数据结构与算法之美！一起加油(ง • v •)ง

技巧一：理解指针或引用的含义

事实上，看懂链表的结构并不是很难，但是一旦把它和指针混在一起，就很容易让人摸不着头脑。所以，要想写对链表代码，首先就要理解好指针。

我们知道，有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

实际上，对于指针的理解，你只需要记住下面这句话就可以了：

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

不知道你有没有这样的感觉，写链表代码的时候，指针指来指去，一会儿就不知道指到哪里了。所以，我们在写的时候，一定注意不要弄丢了指针。

指针往往都是怎么弄丢的呢？我拿单链表的插入操作为例来给你分析一下。

p->next = x; // 将 p 的 next 指针指向 x 结点x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点

初学者经常会在这儿犯错。p->next 指针在完成第一步操作之后，已经不再指向结点 b了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。

对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。

技巧三：利用哨兵简化实现难度

首先，我们先来回顾一下单链表的插入和删除操作。如果我们在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

new_node->next = p->next;p->next = new_node;

但是，当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中 head 表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

if (head == null) {   	head = new_node;}

我们再来看单链表结点删除操作。如果要删除结点 p 的后继结点，我们只需要一行代码就可以搞定。

p->next = p->next->next;

但是，如果我们要删除链表中的最后一个结点，前面的删除代码就不行了。跟插入类似，我们也需要对于这种情况特殊处理。写成代码是这样子的：

if (head->next == null) {   	head = null;}

从前面的一步一步分析，我们可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。如何来解决这个问题呢？

技巧三中提到的哨兵就要登场了。哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

还记得如何表示一个空链表吗？head=null 表示链表中没有结点了。其中 head 表示头结点指针，指向链表中的第一个结点。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

我画了一个带头链表，你可以发现，哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

技巧四：重点留意边界条件处理

我经常用来检查链表代码是否正确的边界条件有这样几个：

• 如果链表为空时，代码是否能正常工作？
• 如果链表只包含一个结点时，代码是否能正常工作？
• 如果链表只包含两个结点时，代码是否能正常工作？
• 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

当然，边界条件不止我列举的那些。针对不同的场景，可能还有特定的边界条件，这个需要你自己去思考，不过套路都是一样的。

实际上，不光光是写链表代码，你在写任何代码时，也千万不要只是实现业务正常情况下的功能就好了，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

技巧五：举例画图，辅助思考

就像我上面给的图一样，大家敲的时候也一定要自己动手画画那样的图，可以更好的帮你解决问题。特别是想不明白的时候，画图可以帮你分担很大的脑容量！

技巧六：多写多练，没有捷径

其实也没有什么技巧，就是把常见的链表操作都自己多写几遍，出问题就一点一点调试，熟能生巧！

所以，我精选了 5 个常见的链表操作。你只要把这几个操作都能写熟练，不熟就多写几遍，我保证你之后再也不会害怕写链表代码。

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点

写这些之前，希望读者先把单链表的增删改查写到我上面说的程度，再来写这几个，相信就会好很多！

菜鸟也得去敲到熟练了，估计得几天后，才能达到默写的程度，到时候再来和大家一起分享后面的学习！