为什么需要链表

数组的问题：不能方便的移动/插入/删除，所以快速排序只能使用交换，增加了代码的难度。

所以我们引入链表：

一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成……

简单的例子：

• 幼儿园小盆友手牵手的回家
• 跟团旅游，导游会让我们记住旁边的人，回头清点人数吼一声：你们旁边的人都在不？
  

一图胜前言：

总结：链表中的每一个节点都记着它的上/下一个节点。其中：

• 头（Head）节点前面没有节点
• 尾（Tail）后面没有节点

链表的：

• 可以非常方便的添加/删除/插入/移动节点，所以
• 长度（节点个数）不受限制

常用于操作系统中的内存/磁盘管理。演示：形成存储碎片 => 使用链表粘合存储空间

@想一想@：链表又有什么问题不？

分类

按照链表中节点记录的

• 单向链表，如上图所示
• 双向链表：
  
  

  比如我们一起帮的文章单页，每一篇底部都有一个“上一篇”和“下一篇”：

  
  这就是双向链表的应用。
  

还可以有一种特殊的环状/循环链表：头尾相连

单向链表实现

链表中的任一个节点，都可以看成是链表本身——因为从这个节点出发，向前（Previous）/向后（Next）就能够获得全部的节点。

定义了一个（头）节点，也就定义了一个链表：

class node {
	constructor(value) {
		//让节点中可以存放一个值，以便调试/测试用
		this.value = value;
	}
}

怎么让它记录下一个节点是啥呢？用属性next：

//生成2个节点
var n1 = new node(1);
var n2 = new node(2);

//让n1的next属性指向n2，链表成型！
n1.next = n2;

@想一想@：再加一个节点怎么做？

InsertAfter()

能不能把“插入一个节点”封装成一个方法？比如：把“节点5插入2和3之间”，怎么定义？

PS：不要忘了，我们并不总是在链表末尾插入的！

首先，把“节点5插入2和3之间”转变成“节点5插入2之后（InsertAfter()）”，@想一想@：为什么？因为：

• 2和3之间说不定还有其他节点呢？
• 少传一个无用参数呀
  

然后，节点5怎么传入方法（指明“把谁”插入节点2之后）？是不是要在InsertAfter()中定义两个参数？能不能有更好的方法？

应该在node类中定义这样的一个实例方法：

class node {
	constructor(value) {
		this.value = value;
	}
	insertAfter(node){
	}
}

调用的话：

n5.insertAfter(n2);

insertAfter()方法的实现很简单：（复习：this）

node.next = this;	// n2.next = n5;
this.next = node.next;  // n5.next = n2.next(n3);

@试一试@：是这样的吗？

var n1 = new node(1),
	n2 = new node(2),
	n3 = new node(3),
	n4 = new node(4);
n1.next = n2;
n2.next = n3;
n3.next = n4;

var n5 = new node(5);
n5.insertAfter(n2);

双向链表实现

和单向链表相比，双向链表的每个节点都多记录一个之前的节点，即多一个previous属性：

n2.previous = n1;
n3.previous = n2;
n4.previous = n3;

我们试着实现双向链表的insertAfter()，添加如下代码：

this.previous = node; //this.previous = n2;
node.next.previous = this; //n3.previous = n5;

@想一想@：就这样写一写，代码质量你放心吗？

为了提高代码质量减少bug（程序中的“缺陷”，可大可小，类似于偶尔的、在某种特殊场景下的刹车失灵、喇叭不响、车门关不严），很多大佬曾经大力倡导过：

TDD

其全称是Test-DrivenDevelopment（测试驱动开发），其核心是：先测试，再开发。即在开发功能代码之前，先编写单元测试用例代码。

具体来说，它要求的开发流程是这样的：

1. 写一个未实现的开发代码。比如定义一个方法，但没有方法实现
2. 为其编写单元测试。确定方法应该实现的功能
3. 测试，无法通过。^_^，因为没有方法实现嘛。但这一步必不可少，以免单元测试的代码有误，无论是否正确实现方法功能测试都可以通过
4. 实现开发代码。比如在方法中完成方法体。
5. 再次测试。如果通过，Over；否则，查找原因，修复，直到通过。

单元测试

按飞哥的定义，单元测试是开发人员自己用代码实现的测试。注意这个定义，其核心在于：

• 主体是“开发人员”，不是测试人员。
• 途径是“通过代码实现”，不是通过手工测试。
• 实质是一种“测试（test）”，不是代码调试（debug）。

后面我们会介绍专门的单元测试工具，但现在我们先用自己的代码简单模拟一下：

测试用例

其实就是把我们之前散乱书写（script块+控制台）的测试代码放在一个专门的方法当中，然后用console.log()输出被测试方法运行过后预期值（expected）和实际值（actual）是否一致，模拟断言（Assert）：

function insert5After2Test(){
	setup();

	//之前写在控制台
	var n5 = new node(5);
	n5.insertAfter(n2);

	//1 2 [5] 3 4
	console.log(n2.next == n5);    //true：符合预期，方法OK；否则，有问题 
	console.log(n5.next == n3);
	console.log(n3.previous == n5);
	console.log(n5.previous == n2);
	//可以一目了然的看出方法运行之后的结果是否符合预期

	tearDown();
}

这样的一个方法就被称之为一个测试用例（test case）。

注意其中的：

SetUp()&TearDown()

会在每一个测试用例执行前后调用，用于设置和清理测试环境，这里就是建立n1-n2-n3-n4构成的双向链表：

//全局变量，公用
var n1, n2, n3, n4;

function setup(){	
	n1 = new node(1);    //每次都重新生成全新的对象
	n2 = new node(2);
	n3 = new node(3);
	n4 = new node(4);	
	
	n1.next = n2;    //将对象串起来
	n2.previous = n1;
	n2.next = n3;
	n3.previous = n2;
	n3.next = n4;
	n4.previous = n3;		
}

TearDown()在这里暂时没用，所以就是一个空方法。复杂测试环境可以做一些释放文件资源/数据库连接之类的工作。

当测试走进酒吧

想得更深一点：如果是在链表的尾部插入呢？是不是也应该测一测？

继续在InsertAfterTest()中添加Assert行

var n6 = new node(6);
n6.insertAfter(n4);

//1 2 5 3 4 [6]
console.log(n4.next == n6); 
console.log(n6.next == undefined);    //可省略也可以保留
console.log(n6.previous == n4);

演示：测试无法通过，报异常

@笑一笑@：

一个测试工程师走进一家酒吧，要了一杯啤酒 一个测试工程师走进一家酒吧，要了一杯咖啡； 一个测试工程师走进一家酒吧，要了0.7杯啤酒； 一个测试工程师走进一家酒吧，要了-1杯啤酒； 一个测试工程师走进一家酒吧，要了2^32杯啤酒； 一个测试工程师走进一家酒吧，要了一杯洗脚水； 一个测试工程师走进一家酒吧，要了一杯蜥蜴； 一个测试工程师走进一家酒吧，要了一份asdfQwer@24dg!&*(@； 一个测试工程师走进一家酒吧，什么也没要； 一个测试工程师走进一家酒吧，又走出去又从窗户进来又从后门出去从下水道钻进来； 一个测试工程师走进一家酒吧，又走出去又进来又出去又进来又出去，最后在外面把老板打了一顿； 一个测试工程师走进一家酒吧，要了一杯烫烫烫的锟斤拷； 一个测试工程师走进一家酒吧，要了NaN杯Null； 一个测试工程师冲进一家酒吧，要了500T啤酒咖啡洗脚水野猫狼牙棒奶茶； 一个测试工程师把酒吧拆了； 一个测试工程师化装成老板走进一家酒吧，要了500杯啤酒并且不付钱； 一万个测试工程师在酒吧门外呼啸而过； 一个测试工程师走进一家酒吧，要了一杯啤酒';DROP TABLE 酒吧； 测试工程师们满意地离开了酒吧。 然后一名顾客点了一份炒饭，酒吧炸了。

@想一想@：关于InsertAfter()，还有什么我们没有想到的不？

修改我们的开发代码：

//引入分支
if(node.next == undefined){

//1 2 5 3 4 [6]
//n6.insertAfter(n4);
//this:n6; node:n4	

node.next = this;
this.previous = node;

再跑一下测试……

再看一下我们的代码，有没有发现一些可以优化的地方？比如，应该拆成两个测试方法：

insert5After2Test();
insert6After4Test();

重构

其实飞哥之前给同学们进行作业点评。如果你的代码没有错误，但我还是给你改了，这就是在做重构（refactor）：

在不改变代码运行结果的前提下，优化代码质量（安全、性能和可读性）。

不知道大家有没有听说过一句话：

好代码都是改出来的。

很少有人一次性的写出非常完美的代码——尤其是代码会随着业务逻辑不断变化的时候，你根本就不可能一次性的完成代码，一定是不断的修修补补。

但是，实际开发中，你会发现“修修补补”就会把代码慢慢地变成了“祖传屎山”。最有越改越烂，哪有什么“千锤百炼”？！

可以想象的一个场景：你满怀激情地正准备要重构，被你项目经理一把扑倒在地，“小子，不要命啦！？”

为什么？

代码之间是相互“耦合”的，所以“牵一发而动全身”，完全有可能形成“多米诺骨牌效应”，一改就崩。

比如，原开发代码insertAfter()的分支中就有重复代码，能将他们抽出分支么？

node.next = this;
this.previous = node;

if(node.next != undefined){
    this.next = node.next;  
    // this.previous = node;    //if...else里都有，所以……    
    node.next.previous = this; 
    // node.next = this;    
}

从逻辑上看，好像没有问题？确定不确定？你懵了……

这就是为什么不能/不敢/不愿重构的原因：

重构风险太大

如果没有单元测试保障的话。

其实添加新的feature（功能），修复旧的bug也一样，很容易对其他代码产生干扰，引入新的bug。而且这些bug可能很隐蔽，不一定能够被及时发现——除非你有单元测试。

有了单元测试，每次代码改动，把所有的（注意，是所有的！）单元测试跑一遍，都跑过了，就证明改动没有影响现有代码。

#常见面试题：你如何看待TDD？

优势

因为要先写单元测试再写开发代码，所以所有的开发代码都有对应的单元测试（这被称之为100%的代码测试覆盖率），于是单元测试保证了代码的：

• 正确性。理论上，TDD的代码bug率非常低——那得你单元测试和开发代码都有疏漏，且双方的疏漏“兼容”才行。否则，开发代码的bug会被单元测试暴露出来；单元测试的bug也会被开发代码暴露出来。
• 可维护性。这其实才是TDD最重要的价值。以后同学们会越来越多的体会到代码维护工作的难度和重要性。业界有一句非常著名的论断：
  一个项目，开发所需的时间要占20%，而维护的时间要占80%同学们进入工作岗位，更大概率也是进行代码的维护工作（添加新feature，修复老bug等），而不是从头开发。如果没有单元测试覆盖，很多时候维护工作就是“头疼医头脚疼医脚”，修复了旧的bug，带来了新的bug。形象的比喻就是：
  
  • 这里有个坑，我在旁边挖点土填上，于是旁边又有了一个坑；
  • 好丑的一坨屎，怎么办？再上面再拉一坨屎盖住它！于是那些历史遗留代码都被称之为“祖传屎山”。

劣势

成本增加，使用TDD开发

• 代码量至少翻番
• 能够TDD开发的程序员，工资说不定也得翻番
  单元测试不是那么好写的！尤其是涉及到数据库，涉及到外部调用接口，项目变得越来越复杂耦合度越来越高的时候……能够单元测试的代码，一定是非常容易解耦的（高质量的）代码。

成本和收益

值得么？

确实，TDD可以降低后期的维护成本；但是，降低多少呢？和现在的投入相比，收益如何呢？更重要更重要的一个问题：能这个项目有后期维护么？99%的互联网项目，根本就活不到后期维护好吧？

就飞哥个人而言，更愿意取一个折中：

仅为“核心”代码使用TDD，引入单元测试。

什么是核心代码呢？大致来说，复杂的、被大量使用、被反复修改的……，都可以算。但最终还是要靠开发人员根据实际情况具体掌握了。

作业

按TDD的要求，基于双向链表，完成：

1. InsertBefore()：在某节点前插入
2. Delete()：删除某节点
3. FindBy()：根据节点值查找到某个节点
   
4. [选]Swap()：将链表中某节点和另一节点交换
   
5. [选]QuickSort()：快速排序，即把一个值（value）无序的链表，重新按值从小到大排列。
6. 为什么作业是基于双向链表，不是单向链表呢？（盘外招：想一想飞哥的人品，^_^）
   

提示：

• 重用
• 先常规，后特殊
  

体会：软件项目的复杂性。（区别于：算法复杂度）

非常简单的、琐碎的代码通过组合，就能够带来层出不穷的、此起披伏的bug：按下了葫芦浮起了瓢！

源栈学历

在当前系列 数据结构和算法 中继续学习：

多快好省！前端后端，线上线下，名师精讲

• 先学习，后付费；
• 不满意，不要钱。
• 编程培训班，我就选源栈

更多了解 加：