数据结构（二）：单向链表、双向链表

一、什么是链表

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有的语言称为指针或连接）组成。类似于火车头，一节车厢载着乘客（数据），通过节点连接另一节车厢。

• head属性指向链表的第一个节点；
• 链表中的最后一个节点指向null；
• 当链表中一个节点也没有的时候，head直接指向null；

1.数组的缺点

1、数组的创建通常需要申请一段连续的内存空间（一整块内存），并且大小是固定的。所以当原数组不能满足容量需求时，需要扩容（一般情况下是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）。
2、在数组的开头或中间位置插入数据的成本很高，需要进行大量元素的位移。

2.链表的优点

1、链表中的元素在内存中不必是连续的空间，可以充分利用计算机的内存，实现灵活的内存动态管理。
2、链表不必在创建时就确定大小，并且大小可以无限地延伸下去。
3、链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。

3.链表的缺点

1、链表访问任何一个位置的元素时，都需要从头开始访问，需要顺着指针一个一个找（无法跳过第一个元素访问任何一个元素）。
2、无法通过下标值直接访问元素，需要从头开始一个个数组内和指针访问，直到找到对应的元素，这也是和数组最明显的区别。
3、虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。

4.链表和数组的区别

二、封装单向链表

首先定义一个节点类，用来存储新声明的节点

//定义一个节点类，用来声明新的节点
class Node {constructor(data) {this.data = data; //数据this.next = null; //指针}
}

开始封装，声明两个属性，分别是头部指针和长度。

1. append方法：向尾部插入节点

1、先声明一个新的节点，判断链表是否有数据。如果没有数据，直接head指向新节点。
2、如果有数据，那么就要声明一个变量current来存储当前的指针。这个指针第一次肯定指向第一个元素（看代码理解），然后循环看一下current.next是否有指向，如果有，就改变current为current.next，直到current.next为空，说明已经到链表尾部了。
3、最后，将current指针指向新节点，搞定。

//封装一个单向链表
class LinkedList {constructor() {this.head = null;this.length = 0;}//将元素插入链表尾部的方法append(data) {//1.声明一个新的节点let newNode = new Node(data);if(this.length == 0) {//2.1如果链表为空，那么head直接指向新节点this.head = newNode;}else {//2.2如果链表不为空，那么循环遍历，直到指针指向最后一个节点let current = this.head; //这里每次都是指向第一个元素while(current.next) {current = current.next;}current.next = newNode;}//3.添加完之后length+1this.length++;}
}

2. toString方法：链表元素转字符串

//转字符串的方法
toString() {let result = '';let current = this.head;while (current) {result += current.data + ' '; //如果有就拼接current = current.next; //指针指向后面的元素}return result;
}

顺便测试一下append方法好不好使

let list = new LinkedList();
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素 

3. insert方法：在任意位置插入数据

情况1：在position为0的位置插入数据，那么这样的话就要

1、先让插入的新元素指向原来的第一个元素
2、然后再让head指向插入的新元素。

情况2：往其他位置插入

1、首先应该拿到该位置的那个元素
2、让新节点指向该元素
3、让该位置前边的元素指向新节点

代码（仔细看注释）：

//任意位置插入元素
insert(position, data) {//1.对position进行越界判断//position==this.length说明是往最后插，如果比它大就不行了if(position < 0 || position > this.length) return false;//2.生成新节点let newNode = new Node(data);//3.对position的不同情况进行判断//3.1如果插入的位置是第一个（position=0）if(position == 0) {newNode.next = this.head; //先保存原来的第一个元素this.head = newNode; //再把新节点给head//注意：上面这两步顺序不能反，不然就找不到原来的第一个元素了}else {//如果是往其他位置插入元素let current = this.head;  //拿到第一个元素let previous = null; //声明变量存储position前边的元素//循环查找，直到找到这个位置的元素for(let i = 0; i < position; i++) {previous = current; //保存上一个位置current = current.next;  //保存当前位置}//循环结束后current已经是position位置的元素newNode.next = current; //让新节点指向当前位置节点（挤到后边去）previous.next = newNode; //让前一个节点指向新节点}//4.长度加1this.length++;return true;
}

测试代码：

let list = new LinkedList();
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
list.insert(2,'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素 

4.get获取某个位置的元素

传入位置返回当前位置元素。
主要的思路就是从head找，通过循环依次改变指针的指向，直到指针指向当前位置，那么就把当前位置返回，（如果用户输入0，那么直接返回this.head）

//获取某个位置的元素
get(position) {//1.越界判断,如果获取最后一个位置后面，那么是没有滴，所以是>=lengthif (position < 0 || position >= this.length) return false;//2.从头往后找，直到找到该位置元素let current = this.head;for (let i = 0; i < position; i++) {current = current.next;}return current;
}

测试代码：

let list = new LinkedList();
//1.测试尾部插入
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, 'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个位置元素 
console.log(list.get(2)); //Node {data: 'ht', next: Node}

5.indexOf根据元素值返回元素位置

主要的思路是从head依次往后查找（需要定义指针current），如果当前指针不为空，就拿传入的元素值和当前current指针的元素值比较，如果相等说明是我们要找的，直接return，不相等就要依次往后指，并且index要+1

   indexOf(data) {let current = this.head;let index = 0; //定义一个索引//从头开始一个一个对比，如果相等了就返回index的值while(current) {if(current.data == data) {return index;}else {//当前节点不是我要找到节点，那么就往后指current = current.next;index++;}}//如果所有都对比完了都没找到，说明没有，就返回-1return -1;}

测试代码：

let list = new LinkedList();
//1.测试尾部插入
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, 'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个位置元素 
console.log(list.get(2)); //Node {data: 'ht', next: Node}
//4.测试获取某个元素索引
console.log(list.indexOf('zzy')); //1

6.update更新某个位置的元素

主要思路：
1、通过声明current指针，拿到这个位置的元素
2、改变该元素内部的data的值，不需要改变前后指针（因为对象地址不会变）

//更新某个位置的元素值
update(position, data) {//1.越界判断,positon==length是刚好在最后一个元素的后面那个空位if(position < 0 || position >= this.length ) return false;//2.拿到这个位置节点let current = this.head;let index = 0;while(index++ < postion) {current = current.next;}//3.修改当前节点的元素值current.data = data;return current;
}

测试更新：

let list = new LinkedList();
//1.测试尾部插入
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, 'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf('zzy')); //1
//4.测试获取某个位置元素 
console.log(list.get(2)); //Node {data: 'ht', next: Node}
//5.测试修改元素
list.update(2, '修改元素');  
console.log(list.toString()); //DantinZhang zzy 修改元素 元素 

7.removeAt删除某个位置的节点

1、如果删除的是第一个位置，那么head直接指向第二个节点，其他不用动（被删除的第一个节点由于没有指针指向它，会被垃圾回收机制回收）

2、如果删除的是其他的位置，就要让被删除节点的上一个节点指向被删除节点的下一个节点

代码如下：

//删除指定位置的节点
removeAt(position) {//1.越界判断if(position < 0 || position >= this.length) return false;let current = this.head;//2.1如果删除的是第一个节点,前边没东西，只有headif(position == 0) {this.head = current.next;}else {//2.2如果删除的是其他位置的节点let index = 0;let previous = null;//2.2.1先找到前边的节点，删除节点，后边的节点while(index++ < position) {previous = current;current = current.next;}//2.2.2将前边的节点指向后边的节点previous.next = current.next;}//3.长度-1this.length--;//4.返回被删除的元素return current;
}

测试代码：

let list = new LinkedList();
//1.测试尾部插入
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, 'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf('zzy')); //1
//4.测试获取某个位置元素 
console.log(list.get(2)); //Node {data: 'ht', next: Node}
//5.测试修改元素
list.update(2, '修改元素');  
console.log(list.toString()); //DantinZhang zzy 修改元素 元素
//6.测试删除指定位置元素
list.removeAt(2);
console.log(list.toString()); //DantinZhang zzy 元素 

8.remove删除指定data的元素

这里的思路就是先找到data对应的索引，然后删除，直接调用就行了

//删除指定data所在的节点
remove(data) {//1.先找到data所在的位置let index = this.indexOf(data);//2.删除该位置的元素return this.removeAt(index);
}

9.判断是否为空、输出长度

//判断链表是否为空
isEmpty() {return this.length == 0;
}//判断链表的长度
size() {return this.length;
}

全部测试代码：

let list = new LinkedList();
//1.测试尾部插入
list.append('DantinZhang');
list.append('zzy');
list.append('元素');
console.log(list.toString()); //DantinZhang zzy 元素
//2.测试任意位置插入
list.insert(2, 'ht');
console.log(list.toString()); //DantinZhang zzy ht 元素
//3.测试获取某个元素索引
console.log(list.indexOf('zzy')); //1
//4.测试获取某个位置元素 
console.log(list.get(2)); //Node {data: 'ht', next: Node}
//5.测试修改元素
list.update(2, '修改元素');  
console.log(list.toString()); //DantinZhang zzy 修改元素 元素
//6.测试删除指定位置元素
list.removeAt(2);
console.log(list.toString()); //DantinZhang zzy 元素 
//7.测试删除指定data的元素
list.remove('元素');
console.log(list.toString()); //DantinZhang zzy
//8.测试是否为空和输出长度
console.log(list.isEmpty()); //false
console.log(list.size()); //2

三、封装双向链表

1.什么是双向链表

双向链表：既可以从头遍历到尾，又可以从尾遍历到头。也就是说链表连接的过程是双向的，它的实现原理是：一个节点既有向前连接的引用，也有一个向后连接的引用。

双向链表的缺点：
1、每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些；
2、 相对于单向链表，所占内存空间更大一些；
3、但是，相对于双向链表的便利性而言，这些缺点微不足道。
也就是说，双向链表就是用空间换时间

• 双向链表不仅有head指针指向第一个节点，而且有tail指针指向最后一个节点；
• 每一个节点由三部分组成：item储存数据、prev指向前一个节点、next指向后一个节点点；
• 双向链表的第一个节点的prev指向null；
• 双向链表的最后一个节点的next指向null；

2.封装双向链表：结构搭建

class Node {constructor(data) {this.pre = null;this.data = data;this.next = null;}
}class DoublyLinedList {constructor() {this.head = null;this.tail = null;this.length = 0;}
}

3.append向尾部插入元素

双向链表向尾部插入元素和单向不一样，这里不需要再遍历元素，直接拿到tail操作就可以了。在插入的时候有两种情况：1、链表为空时 2、链表不为空时

（1）链表为空，添加的是第一个节点

我们只需要让head和tail都指向这个节点就可以了

（2）添加的不是第一个节点，那么改变相关指向

改变指向分为两步，首先改变下图1、2指向，此时tail指向的是原来的最后一个节点。

newNode.pre = this.tail; //先让新节点pre指向之前的尾部节点
this.tail.next = newNode; //之前尾部节点next指向新节点

第二步，改变指向3，让tail指向新插入的最后一个节点。

this.tail = newNode; //tail指向新节点

//向尾部插入节点
append(data) {//1.先生成一个节点const newNode = new Node(data);//2.添加的是第一个节点，只需要让head和tail都指向新节点if(this.length == 0) {this.head = newNode;this.tail = newNode;} else {//3.添加的不是第一个节点,直接找到尾部(不用遍历)newNode.pre = this.tail; //先让新节点pre指向之前的尾部节点this.tail.next = newNode; //之前尾部节点next指向新节点this.tail = newNode; //tail指向新节点console.log(newNode.next); //最后一个指向null}//4.长度加一this.length++;
}

测试代码：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
console.log(list); 

4.toString链表数据转换为字符串

这里有两种转字符串的方法，分别是顺序和逆序。

主要原理都一样，就是定义current变量记录当前指向的节点。首先让current指向第一个（最后一个）节点，然后通过 current = current.next 依次向后（向前）遍历。在while循环（或for循环）中以(current)作为条件遍历链表，只要current ！= null就一直遍历，由此可获取链表所有节点的数据。

代码：

//1.链表数据转换为字符串的两种遍历（顺序、逆序）
toString() {return this.forwardString();
}//2.顺序遍历转字符串
forwardString() {let result = '';let current = this.head;while (current) {result += current.data + ' ';current = current.next;}return result;
}//3.逆序遍历转字符串
backwardString() {let result = '';let current = this.tail;for (let i = 0; i < this.length; i++) {result += current.data + ' ';current = current.pre;}return result;
}

测试代码：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
list.append('zzy');
console.log(list.toString()); //DantinZhang 努力的但丁 zzy 
console.log(list.forwardString()); //DantinZhang 努力的但丁 zzy 
console.log(list.backwardString()); //zzy 努力的但丁 DantinZhang 

5.insert向任意位置插入节点

这里代码看着比较复杂，不过实现的思路不难。
具体可以去看这个人的博客，写的真的是非常详细：Javascript实现双向链表

//向任意位置插入节点
insert(position, data) {let newNode = new Node(data);//1.越界判断，其中length位置是最后一个节点的后面那个空位if (position < 0 || position > this.length) return false;//2.1如果链表为空if (this.length == 0) {this.head = newNode;this.tail = newNode;} else {//2.2如果链表不为空//2.2.1如果位置是1if (position == 0) {// this.head此时指的是第一个节点this.head.pre = newNode;newNode.next = this.head;this.head = newNode;}//2.2.2.如果在最后一个节点的后面插入else if (position == this.length) {// this.tail此时指的是最后一个节点newNode.pre = this.tail;this.tail.next = newNode;this.tail = newNode;}//2.2.3.如果在其他位置插入else {//先找到这个位置let index = 0;let current = this.head;let previous = null;while (index++ < position) {previous = current;current = current.next;}//插入新节点，到它们俩中间儿previous.next = newNode;newNode.pre = previous;newNode.next = current;current.pre = newNode;}}//3.长度别忘了+1this.length++;return true;
}

测试代码：

//测试代码//1.创建双向链表let list = new DoubleLinklist()//2.测试insert方法list.insert(0, '插入链表的第一个元素')list.insert(0, '在链表首部插入元素')list.insert(1, '在链表中间插入元素')list.insert(3, '在链表尾部插入元素')console.log(list);alert(list)

6.get获取某个位置的元素值

整体思路比较简单，为了提高效率，可以使用二分查找。判断位置是在前半部分还是在后半部分，如果在前半部分，就从head开始找；如果在后半部分，就从tail开始找。

//获取某个位置的元素值
get(position) {//1.越界判断if (position < 0 || position >= this.length) return false;//2.1如果该元素在前半部分,从head开始找if (position < this.length / 2) {let current = this.head;for(let i = 0; i < position; i++) {current = current.next;}return current.data;} else {//2.2如果该元素在后半部分,从tail倒着找let current = this.tail;let index = this.length - 1;while(index-- > position) {current = current.pre;}return current.data;}
}

测试代码：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
list.append('zzy');
list.append('ht');
list.insert(2, '第三个位置插入本元素');
console.log(list.forwardString());
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy

7.indexOf根据某个元素值获取该节点位置

这个和单向链表一样，就是从头找，找不到就返回-1，找到了就对比并返回索引

//根据元素值获取节点位置
indexOf(data) {let current = this.head;let index = 0;while(current) {if(current.data == data) {return index;}else {current = current.next;index++;}}return -1
}

测试代码：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
list.append('zzy');
list.append('ht');
list.insert(2, 'No.3');
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf('zzy'));//3

8.update更新某个元素

主要思路还是先查找，然后把数据改了就行。查找的时候采用二分查找。

//更新某个元素
update(position, data) {//1.生成节点let newNode = new Node(data);//2.越界判断if(position < 0 || position >= this.length) return false;//3.寻找位置，改变元素值，二分查找let current = null;if(position < this.length / 2) {current = this.head;let index = 0;while(index++ < position) {current = current.next;}}else {current = this.tail;for(let i = this.length-1; i > position; i--) {current = current.pre; }}current.data = data;return current.data;
}

测试代码：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
list.append('zzy');
list.append('ht');
list.insert(2, 'No.3');
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf('zzy'));//3
//测试更新
list.update(2,'DJ');
console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht 

9.removeAt删除某个位置的节点

这里的主要思路是：
1、首先判断是否只有一个节点，如果只有一个节点，删除后head和tail都要置空.
2、如果有多个节点，要看删除的是第一个、最后一个、其他位置。
3、第一个位置，先清空第二节节点指向被删除元素的pre指针（清空所有指向它的指针，这样该节点在内存中没用途，会被自动回收），然后直接让head指向第二个节点就行了。
4、最后一个位置，同理，删除倒数第二个节点指向被删除节点的next，然后让tail直接指向倒数第二个节点。
5、删除完长度-1

//删除某个位置的元素
removeAt(position) {//1.越界判断if(position < 0 || position >= this.length) return false;let current = this.head; //定义在最上面方便各种情况返回数据//2.判断是否只有一个节点if(this.length == 1) {//2.1如果只有一个节点，那么删除时head和tail都为空this.head = null;this.tail = null;}else {//2.2如果有多个节点，那么就要进行位置判断//2.2.1删除第一个节点if(position == 0) {//删除前head指向的是第一个节点this.head.next.pre = null; //所有指向它的指针都清掉this.head = this.head.next;}//2.2.2删除最后一个节点else if(position == this.length-1) {//删除前tail指向的是最后一个节点current = this.tail;this.tail.pre.next = null; //所有指向它的指针都清掉this.tail = this.tail.pre;}//2.2.3删除其他的节点else {//先找到位置let index = 0;while(index++ < position) {current = current.next;}current.pre.next = current.next;current.next.pre = current.pre;}}//3.删除完-1this.length -= 1;return current.data;
}

代码测试：

const list = new DoublyLinedList();
list.append('DantinZhang');
list.append('努力的但丁');
list.append('zzy');
list.append('ht');
list.insert(2, 'No.3');
console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy ht
console.log(list.backwardString());
console.log(list.get(2)); //第三个位置插入本元素
console.log(list.get(3)); //zzy
console.log(list.indexOf('zzy'));//3
//测试更新
list.update(2,'DJ');
console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht 
list.removeAt(2);
//测试删除
console.log(list.toString()); //DantinZhang 努力的但丁 zzy ht 

10.remove删除某个元素

//删除某个元素
remove(data) {return this.removeAt(this.indexOf(data));
}

测试代码：

   const list = new DoublyLinedList();list.append('DantinZhang');list.append('努力的但丁');list.append('zzy');list.append('ht');list.insert(2, 'No.3');console.log(list.forwardString());//DantinZhang 努力的但丁 No.3 zzy htconsole.log(list.backwardString());console.log(list.get(2)); //第三个位置插入本元素console.log(list.get(3)); //zzyconsole.log(list.indexOf('zzy'));//3//测试更新list.update(2,'DJ');console.log(list.toString()); //DantinZhang 努力的但丁 DJ zzy ht //测试删除list.removeAt(2);list.remove('努力的但丁');console.log(list.toString()); //DantinZhang zzy ht 

11.其他方法

//删除某个元素
remove(data) {return this.removeAt(this.indexOf(data));
}//测试是否为空
isEmpty() {return this.length == 0;
}//输出长度
size() {return this.length;
}//获取链表第一个元素值
getHead() {return this.head.data;
}//获取链表最后一个元素值
getTail() {return this.tail.data;
}

更详细的图解参考：大佬的博客