本文共 5688 字，大约阅读时间需要 18 分钟。
本文来源于：不甘平凡的码农
写在前边
大家有没有碰到过，在面试的时候，手写一个双向链表，并完成插入数据和删除数据的操作？如果你看到这个问题，你手写得出来吗？如果不会，今天文章教大家如何徒手写链表代码？
思维导图
1
熟悉结构
首先我们要知道链表的结构以及每个节点的结构，这是我们手写链表的第一步，也是学习链表的第一步。我们知道，每个链表时这样表示的：
那每个节点结构是由数据域和指针域组成，数据域是存放数据的，而指针域存放下一结点的地址。
我们可以通过数据域访问到我们要的数据，而通过指针域访问到当前结点以后的结点，那么将这些结点串起来，就是一个链表。
那么用代码怎么来表示呢？
我们通常会用到函数，我们如果将一个函数抽象成一个结点，那么我们给函数添加两个属性，一个属性是存放数据的属性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} 2
理清思路
如果你把链表的结构搞得明明白白了，恭喜你，成功的进入第二关，但是你只超越了百分之20的人，继续加油。
既然链表的结构弄明白了，那么我们开始理思路，我们就先拿最简单的单链表开刀，我们要完成两个操作，插入数据和删除数据。
如果我想插入数据，你可能会问，往哪里插呢？有几种插入的方法？
开始想，插入到单链表的头部算一种。
然后插入到单链表的中间算一种。
插入到单链表尾部又算一种。
所有可能的情况就三种。那么删除呢？想必你也想到了，也一共三种，删除头部、删除中间部分、删除尾部。
如果你觉的现在可以写代码了，那你就错了，虽然我们的思路非常清晰，但是面试官仅仅考我们思路吗？其实这一关你只打败了百分之50%的人，最重点、最主要的是在下一个部分，边界条件。
3
边界条件
边界条件是这五个步骤最容易犯错的一部分，因为通常考虑的不全面，导致了最后的面试未通过。如果想做好这一部分，也不难，跟着小鹿的方法走。
3.1 输入边界
首先我们先考虑用户输入的参数，比如传入一个链表，我们首先要判断链表是否为空，如果为空我们就不能让它执行下边的程序。再比如插入一个结点到指定结点的后边，那么你也要判断输入的结点是否为空，而且还要判断该结点是否存在该链表中。对于这些输入值的判断，小鹿给他同一起个名字叫做输入边界。
3.2 特殊边界
特殊边界考虑到一些特殊情况，比如插入数据，我们插入数据一般考虑到插入尾部，但是突然面试官插入到头部，插入尾部的代码并不适用于插入到头部，所以呢需要考虑这种情况，删除节点也是同样思考。其实特殊边界最主要考虑到一些逻辑上的特殊情况，考察应聘者的考虑的是否全面。小鹿给他起个名字叫做特殊边界。
4
手写代码
4.1 定义结点
1class Node{2 constructor(data){3 this.data = data;4 this.next = null;5 }6} 4.2 增加结点
咱们就以单链表中部添加数据为例子，分解成每个步骤，每个步骤对应代码如下：
1、保存临时地址（4结点的地址）,需要进行遍历查找到3结点，也就是下列代码的currentNode 结点。
1//先查找该元素2let currentNode = this.findByValue(element);3// 保存 3 结点的下一结点地址（4 结点的地址）4let pre = currentNode.next
2、创建新结点，将新结点（5结点）的指针指向下一结点指针（4结点地址，已经在上一步骤保存下来了）
1let newNode = new Node(value);2newNode.next = pre;
3、将3 的结点地址指向新结点（5结点）
1 currentNode.next = newNode;
以上步骤分析完毕，剩下的两个在头部插入和在尾部插入同样的分析方式，将这两个作为练习题，课下自己试一试这个步骤。
4.3 删除节点
删除节点也分为三种，头部、中部、尾部，咱们就删除中间结点为例进行删除，我们详细看步骤操作。
我们先看删除的全部动画，然后再分步拆分。
断开3结点的指针（断开3结点相当于让2结点直接指向4结点）
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结点，完成删除。
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
测试用例
其实这里的测试用例主要用于判断我们写的程序到底对不对，我们一般都会输入一个自己认为的情况进行测试，这是错误的做法。程序最容易出错的还是边界情况考虑不全面导致的，所以，我们为了能够测试程序的全面性，所以我们要按照以下步骤进行全面性的测试。
5.1 普通测试
普通测试就是输入一个正常的值，比如单链表中插入数据
5.2 特殊测试
特殊输入可以参照上边边界条件中的特殊边界进行测试，比如在头部插入数据，在尾部插入数据等特殊情况的测试。
5.3 输入测试
对于输入测试的内容参考上边边界条件中的输入边界，比如：输入一个空链表测试一下程序能否正常的运行。
6
小结
做一个小结。今天的手写链表主要从五部分下手，从前到后依次为熟悉结构、理清思路、手写代码、测试用例。以后无论手写什么代码，有五步走，对于面试完全没有问题啦。
通过总结手写链表的方法，不用刻意去背，只要把思路理清楚，边界条件考虑全面，就不用去背，重复的练习。今天的内容就到这里了，如果觉得有帮助，转发文章让更多人看到是对作者最大的支持，非常感谢。
本文代码：
https://github.com/luxiangqiang/Data-Structure-Coding
推荐阅读：
1、
2、
3、
↓↓↓ 戳 “阅读原文” ，第五期打卡赠书活动！
转载地址：https://cxydev.blog.csdn.net/article/details/101442378 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
