前言
链表是最基础的动态数据结构。
动态数组、栈、队列，底层都是依托静态数组，靠 resize 解决固定容量问题。它们所谓的动态，是从用户的角度上来看的。
链表是真正的动态数据结构，它是数据结构中的一个重点，也有可能是一个难点吧。它是最简单的一种动态数据结构，其它更高级的动态数据结构有二分搜索树、Trie、平衡二叉树、AVL、红黑树等等。
熟悉了最简单的动态数据结构，那么对于更高级的也会比较容易掌握了。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
链表（LinkNode）
对于链表来说它涉及到了计算机领域一个非常重要的概念，更深入的理解引用（或者指针），这个概念和内存相关，在 JS 里面不需要手动的管理内存，但是对链表这种数据结构更加深入的理解，可以让你对 引用、指针甚至计算机系统中和内存管理相关很多话题有更加深入的认识。
链表本身也是有它非常清晰的递归结构的，只不过由于链表这种数据结构它本身是一种线性的数据结构，所以依然可以非常容易的使用循环的方式来对链表进行操作，但是链表本身由于它天生也是具有这种递归结构的性质，所以它也能让你更加深入的理解递归机制相应的这种数据结构，在学习更加复杂的数据结构的时候，对递归这种逻辑机制深入的理解是必不可缺的。
链表这种数据结构本身就具有功能性，它可以用来组成更加复杂的数据结构，比如 图结构、hash 表、栈(链表版)、队列(链表版)，所以他可以辅助组成其它数据结构。
先简单认识一下链表
数据存储在“节点”（Node）中，把数据存在一种单独的结构中，这个结构通常管它叫做节点，对于链表节点来说他通常只有两部分，一部分就是存储真正的数据，另一部分存储的是当前节点的下一个节点，链表其实就像一个火车，每一个节点都是一节车厢，在车厢中存储数据，而车厢和车厢之间还会进行连接，以使得这些数据是整合在一起的，这样用户可以方便的在所有的这些数据上进行查询等等其它的操作，数据与数据之间连接就是用下面的这个 next 来完成的。
class Node {
e; //Element
next; //Node
}链表的优缺点
链表的优点：
真正的动态，不需要处理固定容量的问题，它不像静态数组那样一下子 new 出来一片空间，也根本不需要考虑这个空间是不是不够用，也根本不用去考虑这个空间是不是开多了。
对于链表来说，你需要多少个数据。你就可以生成多少个节点，把它们挂接起来了，这就是所谓的动态。
链表的缺点：
和数组相比，它丧失了随机访问的能力。不能像数组那样给一个索引就能直接访问对应索引位置的元素，这是因为从底层机制上数组所开辟的空间在内存里是连续分布的，所以才能够直接去向索引对应的偏移计算出相应的数据所存储的内存地址，然后就能够直接用O(1)的复杂度取出这个元素，但是链表不同，链表由于是靠 next 一层一层连接的，所以在计算机的底层，每一个节点他所在的内存的位置是不同的，只能够靠这个 next 来一层一层的找到这个元素，这就是链表最大的缺点。
数组与链表的对比
数组
数组最好永远索引有语意的情况，如 scores[2]
最大的优点：支持快速查询
链表
链表不适合用于索引有语意的情况。
最大的优点：动态存储。
对比
数组也可以没有语意，并不是所有的时候索引是有语意的，也并不是所有有语意的这样的一个标志就适合做索引，如身份证号，将一个静态数组改变为一个动态数组，就是在应付不方便使用索引的时候有关数据存储的问题，对于这样的存储数据的需求使用链表是更合适的，因为链表最大的优点是动态存储。
要清楚什么时候使用数组这样的静态数据结构，什么时候使用链表这类的动态数据结构。
简单的链表实现-MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {}
}封装链表
在链表中进行添加、插入操作
链表是通过节点来装载元素，并且节点和节点之间会进行连接。如果想访问这条链表中所有的节点，那么就必须把链表的头给存储起来，通常这个链表的头叫做的 head，应该说在MyLinkedList中应该有一个变量指向链表中的第一个节点。
给自定义数组添加元素是从数组尾部开始添加，给链表添加元素是从数组头部开始添加，因为自定义数组有维护一个 size，这个 size 指向的是下一个待添加元素的位置，所以你直接将 size 做索引直接赋值即可，有 size 这个变量在跟踪数组的尾巴，而对于链表来说 有设置一个链表的头这样的一个变量，也就是说有一个变量在跟踪链表的头，并没有一个变量去跟踪链表的尾巴，所以在链表头部添加元素是非常方便。
添加操作原理将一个新的元素挂接到链表头部，同时不破坏现在链表的这个结构，添加一个新元素 666，它的名字叫 node，就只需要使用 node.next = head，也就是将新添加的元素的 next 指向链表的头，这个时候新添加的元素也成为新的链表头，也就是head = node，这样 head 就会指向新的元素 666，也就是 node 这个节点，如此一来就完成了将 node 这个节点插入了整个链表的头部，node 这个变量是在一个函数中声明的，所以函数结束之后这个变量的作用域也就结束了，链表的 head 也等于 node，链表中就新增了一个新元素。
在链表头部添加元素非常简单，只需要创建节点，让节点的 next 指向 head，然后让 head 重新指向这个节点，也就是让 head 变成新的元素，因为链表是从头部添加元素的。
在链表中间添加元素，定义一个 prev 的变量指向中间元素的前一个元素，然后让新增加的元素这样，node.next = prev.next，之后这样，prev.next = node，这样一来就在 prev 这个元素和原本 prev 的下一个元素之间插入了一个新元素，叫做 node，整个过程就是将 prev 的 next(下一个元素)的引用传递给新元素的 next(下一个元素)，然后将 prev 的 next(下一个元素)变更为这个新元素，最后就将新元素插入到中间了。这个过程的关键是找到待添加的节点的前一个节点，这个就是 prev 变量要做的事情。
在链表的操作中很多时候顺序非常重要，如在链表中插入一个元素，在指定的元素后面插入一个元素，并且不影响整个链表结构，和在链表中间添加元素一样，把原本的node.next = prev.next和prev.next = node的顺序变一下，prev.next = node在前，node.next = prev.next 在后，这样一来逻辑就不成立了，链表不仅断开了，而且新节点的 next 指向的是自己，死循环了，所以一样的代码，顺序颠倒了，得到的结果就是错误的。
在链表的 index(0-based)位置添加元素 e，通过索引来操作链表，在链表中不是一个常用的操作，因为在选择使用链表的时候通常就选择不使用索引了，这个需求在面试考题中有很大出现的概率哟，不过这种需求它的主要作用更多是一个练习吧。
代码实现
(class: MyLinkedList)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 获取链表中实际的节点个数
getSise() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
let node = new MyLinkedListNode(element, null);
node.next = this.head;
this.head = node;
this.size++;
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
if (index === 0) {
this.addFirst(element);
} else {
// 第一个prev就是head
let prev = this.head;
// 变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 1; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
}给链表设立虚拟头节点
在链表中进行指定索引处插入元素时，对链表头插入元素与对链表其它位置插入元素的逻辑有区别，所以就导致每次操作都需要对索引进行判断，如果你是在索引 0 的位置插入元素，那么就没有 prev(前一个元素)，自然就不可以使用node.next = prev.next和prev.next = node了，那时候你可以直接使用node.next = head和head = node，不过已经有了向链表头添加元素的方法了，所以向头部插入元素时根本就不需要这么做，这时候可以通过给链表设立虚拟头节点来解决这个问题。
为什么对链表头插入元素那么特殊？
因为插入元素时，必需要找到该索引位置的节点之前的一个节点(prev)，而链表头(head)之前并没有任何节点，所以逻辑上就会特殊一些。
不过在链表的具体实现中有一个非常常用的技巧，可以把链表头的这种特殊的操作与其它的操作一起统一起来，其实这个方法的想法很简单，既然它没有链表头之前的节点，那就自己造一个链表头之前的节点，这个链表头之前的节点不会用来存储任何元素，存储的数据为空，这个空节点就称之为整个链表头的 head，也可以叫它 dummyHead，因为它就是一个假的 head，它也是为链表设立的虚拟头节点，这样一来 链表的第一个元素就是 dummyHead 的 next 所对应的那个节点，因为 dummyHead 这个位置的元素是根本不存在的，对用户来讲也是根本没有意义的，这只是为了编写逻辑方便而出现的一个虚拟的头节点，所以一个这样的内部机制对用户来说也是不可见的，用户不知道链表中有没有虚拟的头节点，这和自定义的循环队列有点像，自定义循环队列中有一个不可用的空间，有意识地去浪费一个空间，为了编写逻辑更加的方便，从而也让性能在整体上得到了提升。
有了 dummyHead 之后就不需要处理头节点这个特殊的操作，因为当你在头部插入元素时，可以这样node.next = dummyHead.next、dummyHead.next = node ，这样你就解决了每次插入时都要进行一次逻辑判断了，这样一来就说明了链表中所有的节点都有前一个节点了，在初始的时候 dummyHead 指向的是索引为 0 的元素前一个位置的节点。
链表操作的实际原理
在没有使用虚拟头节点之前，一直都是在链表头 head 这个地方不停的添加节点，然后将 head 这个变量不停的指向新添加的节点 node.next = head.next;head = node;。
在使用了虚拟头节点之后，一直是在链表虚拟头 dummyHead 这个地方后面一个位置不停的插入新节点，dummyHead 从未变动过，永远在链表的第一个位置，node.next = dummyHead.next; dummyHead.next = node;，但是dummyHead.next才是链表中第一个实际记录的节点，用户会不知道虚拟节点的存在，因为 dummyHead 并不算在链表的实际节点中，也就是 size 中不会维护 dummyHead，dummyHead 的存在是为了维护一致的插入操作。
代码实现
(class: MyLinkedList)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSise() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
}在链表中进行遍历、查询、修改操作
如果要找指定索引元素的前一个节点，那么就要从dummyHead开始遍历，如果要找指定索引元素的那个节点，那么就要从dummyHead.next开始遍历。
代码实现
(class: MyLinkedList, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor () {
/this.alterLine("MyLinkedList Area");
let mylinkedList = new MyLinkedList();
for (let i = 1; i <= 5 ; i++) {
mylinkedList.addFirst(i);
console.log(mylinkedList.toString());
}
mylinkedList.insert(2, 88888);
console.log(mylinkedList.toString());
}
// 将内容显示在页面上
show (content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine (title) {
let line = `--------------------${title}----------------------`
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}在链表中进行删除操作
链表元素的删除
假设要删除索引为 2 位置的元素就是要索引为 2 位置的元素的前一个元素，还要索引为 2 位置的元素的后一个元素，让前一个元素的 next 等于后一个元素，也就是前一个元素的 next 等于索引为 2 的元素的 next。
也就是让 prev 指向待删除的那个节点的前一个节点，prev 这个节点的 next 就是要删除的那个节点 delNode，然后让prev.next = delNode.next，这样就让待删除的那个节点的前一个节点的 next，也就是直接指向了待删除的那个节点的后一个节点了，然后让delNode.next = null 就完成了删除，千万不要这样delNode = delNode.next，这个并不是删除，而是将待删除节点的引用指向了下一个节点，通过设置为 null 才是真正的与当前链表脱离关系。
代码实现
(class: MyLinkedList, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 删除指定索引位置的节点
remove(index) {
// 验证索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待删除的节点
let delNode = node.next;
// 给待删除那个节点的前一个的节点的next引用替换为
// 但删除的这个节点的next
node.next = delNode.next;
// 或者这样也行
// node.next = node.next.next;
// 临时存储待删除的那个节点里的元素
let element = delNode.element;
// 清空 待删除的节点
delNode = null;
this.size--;
return element;
}
// 扩展：移除链表头的元素
removeFirst() {
return this.remove(0);
}
// 扩展：移除链表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedList Area');
let mylinkedList = new MyLinkedList();
for (let i = 1; i <= 5; i++) {
mylinkedList.addFirst(i);
console.log(mylinkedList.toString());
}
mylinkedList.insert(2, 88888);
console.log(mylinkedList.toString());
mylinkedList.remove(2);
console.log(mylinkedList.toString());
mylinkedList.removeFirst();
console.log(mylinkedList.toString());
mylinkedList.removeLast();
console.log(mylinkedList.toString());
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}链表的时间复杂度分析
增：O(n)：在只对链表头进行操作时为O(1)
删：O(n)：在只对链表头进行操作时为O(1)
改：O(n)
查：O(n)：只查链表头的元素时为O(1)
链表增删改查的时间复杂度
整体上要比数组增删改查的时间复杂度要差，因为数组有一个优势，你有索引的话你就可以快速访问，而链表没有这样的优势但是链表的优势是，如果你只对链表头进行增删的操作，那么它的时间复杂度是 O(1)级别的，而且它整体是动态的，所以不会大量的浪费内存空间。链表适合做的事情是不去修改、也不去查任意的元素，就算查，也只能查链表头的元素，查的时候，只有那样才是 O(1)级别的时间复杂度，并且增加删除的时候只对链表头进行操作，只有在这种时候才会和数组整体的时间复杂度是一样的，不过链表整体是动态的，不会去大量的浪费内存空间，所以它具有一定的优势。
链表还有诸多的改进的方式，所以应用链表在一些情况下仍然是有它的优势的，最最重要的是 链表本身是一种最最基础的动态数据结构，对这种动态数据结构要深刻的理解和掌握，对于学习更重要的动态数据结构是有巨大的帮助，比如说二叉树、平衡二叉树、AVL、红黑树等等。
添加操作 O(n)
addLast(e)：O(n)
会从头遍历到尾，找到最后一个节点之后才能添加元素
addFirst(e)：O(1)
直接从头部添加元素
insert(index, e)：O(n/2) = O(n)
会去遍历链表中每一个节点，检索到合适的位置才会添加这个元素。
删除操作 O(n)
removeLast()：O(n)
会去遍历链表中每一个节点，找到最后一个节点后才会删除
removeFirst()：O(1)
直接从头部删除这个节点
remove(index)：O(n/2) = O(n)
会去遍历链表中每一个节点，检索到合适的位置才会移除这个元素
修改操作 O(n)
set(index, e)：O(n)
会去遍历链表中每一个节点，找到了合适位置的节点后，才会修改元素
查找操作 O(n)
get(index)：O(n)
会去遍历链表中每一个节点，找到了合适位置的节点后，返回这个元素。
contains(e)：O(n)
会去遍历链表中每一个节点，返回 是否有相同元素的 bool 值。
find(e)：O(n)
这个方法对链表来说是没有用的，就算你拿到了那个索引你也不能快速访问。
总结
如果刚接触链表，对链表不熟悉，然后很多这种操作在脑子里不能非常快的反应出来，不清楚他的意义是什么，那你可以使用纸笔来稍微画一下，每一步程序逻辑的执行意味着当前这个链表变成了什么样子，这个过程能够帮助你更加深入的理解程序，包括在调试的时候来看你的程序到底为什么出了错误时，非常非常有帮助的，不要犯懒，为了更加深入的理解你的程序，不能只盯着你的代码去想，一定要写写画画，必要的时候甚至根据你的程序进行具体的调试，这些都是非常重要非常有帮助的。
拓展
使用链表来实现栈
对链表进行添加操作时，时间复杂度为O(n)，但是在只对链表头进行操作时为O(1)
对链表进行删除操作时，时间复杂度为O(n)，但是在只对链表头进行操作时为O(1)
对链表进行查询操作时，时间复杂度为O(n)，但是在只查链表头的元素时为O(1)
这些特性很符合栈的需求栈是后进先出的，并且栈只查栈顶的元素，所以可以使用链表来实现栈这样的数据结构。
链表实现的栈
MyLinkedListStack
void push(E e)：添加一个元素 E pop()：移除一个元素 E peek()：查看栈顶的元素 int getSize()：获取栈中实际的元素个数 boolean isEmpty()：判断栈是否为空
代码示例
(class: MyLinkedList,class: MyLinkedListStack, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 删除指定索引位置的节点
remove(index) {
// 验证索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待删除的节点
let delNode = node.next;
// 给待删除那个节点的前一个的节点的next引用替换为
// 但删除的这个节点的next
node.next = delNode.next;
// 或者这样也行
// node.next = node.next.next;
// 临时存储待删除的那个节点里的元素
let element = delNode.element;
// 清空 待删除的节点
delNode = null;
this.size--;
return element;
}
// 扩展：移除链表头的元素
removeFirst() {
return this.remove(0);
}
// 扩展：移除链表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListStack
class MyLinkedListStack {
constructor() {
this.myLinkedList = new MyLinkedList();
}
// 入栈
push(element) {
this.myLinkedList.addFirst(element);
}
// 出栈
pop() {
return this.myLinkedList.removeFirst();
}
// 查看栈顶元素
peek() {
return this.myLinkedList.getFirst();
}
// 查看栈中实际元素的个数
getSize() {
return this.myLinkedList.getSize();
}
// 判断栈是否为空
isEmpty() {
return this.myLinkedList.isEmpty();
}
// 输出栈中信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
arrInfo += `data = stack top [`;
let node = this.myLinkedList.dummyHead.next;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += ']';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedListStack Area');
let myLinkedListStack = new MyLinkedListStack();
for (let i = 1; i <= 5; i++) {
myLinkedListStack.push(i);
console.log(myLinkedListStack.toString());
}
console.log(myLinkedListStack.peek());
this.show(myLinkedListStack.peek());
for (let i = 0; i < 5; i++) {
console.log(myLinkedListStack.toString());
myLinkedListStack.pop();
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 执行主函数
new Main();
};自定义数组实现的栈 VS 自定义链表实现的栈
自定义数组栈与自定义链表栈的性能相差很少，但是随着操作的次数增长，数组栈会慢慢强过链表栈，自定义链表栈中有太多的 new 操作，new 操作在有一些系统上比较耗费性能的，因为它在不停的在内存中寻找可以开辟空间的地方来进行开辟空间，自定义数组栈中有比较多的扩容操作，所以这个比较是相对比较复杂的，和你的语法、操作系统、编译器、解释器都有关系，不过他们的时间复杂度都是O(1)级别的，所以他们之间的性能差异无非就 1-2 倍这样，在最极端的情况下 3-5 倍就已经很难了，不会有几百倍的巨大的差异，因为毕竟他们的时间复杂度一样。
代码示例
(class: MyLinkedList, class: MyLinkedListStack, class: MyArray, class: MyStack, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 删除指定索引位置的节点
remove(index) {
// 验证索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待删除的节点
let delNode = node.next;
// 给待删除那个节点的前一个的节点的next引用替换为
// 但删除的这个节点的next
node.next = delNode.next;
// 或者这样也行
// node.next = node.next.next;
// 临时存储待删除的那个节点里的元素
let element = delNode.element;
// 清空 待删除的节点
delNode = null;
this.size--;
return element;
}
// 扩展：移除链表头的元素
removeFirst() {
return this.remove(0);
}
// 扩展：移除链表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListStack
class MyLinkedListStack {
constructor() {
this.myLinkedList = new MyLinkedList();
}
// 入栈
push(element) {
this.myLinkedList.addFirst(element);
}
// 出栈
pop() {
return this.myLinkedList.removeFirst();
}
// 查看栈顶元素
peek() {
return this.myLinkedList.getFirst();
}
// 查看栈中实际元素的个数
getSize() {
return this.myLinkedList.getSize();
}
// 判断栈是否为空
isEmpty() {
return this.myLinkedList.isEmpty();
}
// 输出栈中信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
arrInfo += `data = stack top [`;
let node = this.myLinkedList.dummyHead.next;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += ']';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyArray
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyStack
class MyStack {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入栈
push(element) {
this.myArray.push(element);
}
// 出栈
pop() {
return this.myArray.pop();
}
// 查看栈顶的元素
peek() {
return this.myArray.getLast();
}
// 栈中实际元素的个数
getSize() {
return this.myArray.getSize();
}
// 栈是否为空
isEmpty() {
return this.myArray.isEmpty();
}
// 查看栈的容量
getCapacity() {
return this.myArray.getCapacity();
}
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Stack: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] stack top is right!`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('Stacks Comparison Area');
let myStack = new MyStack();
let myLinkedListStack = new MyLinkedListStack();
let performanceTest = new PerformanceTest();
let myStackInfo = performanceTest.testStack(myStack, 100000);
let myLinkedListStackInfo = performanceTest.testStack(
myLinkedListStack,
100000
);
this.alterLine('MyStack Area');
console.log(myStackInfo);
this.show(myStackInfo);
this.alterLine('MyLinkedListStack Area');
console.log(myLinkedListStackInfo);
this.show(myLinkedListStackInfo);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
class Student {
constructor(studentName, studentScore) {
this.name = studentName;
this.score = studentScore;
}
toString() {
let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
return studentInfo;
}
}
window.onload = function() {
// 执行主函数
new Main();
};使用链表来实现队列
对链表进行添加操作时，时间复杂度为O(n)，只对链表头进行操作时为O(1)，对链表尾部进行操作时为O(n)
对链表进行删除操作时，时间复杂度为O(n)，只对链表头进行操作时为O(1)，对链表尾部进行操作时为O(n)
对链表进行查询操作时，时间复杂度为O(n)，只查链表头的元素时为O(1)，查链表尾部的元素时为O(n)
队列中的操作，在线性结构的一端插入元素，在另外一端删除元素，所以必然会在线性结构的两端同时操作，此时就会有一端的操作的复杂度是O(n)级别，这个问题在用自定义数组实现时也遇到了，也正因为如此产生了循环队列，通过改进使用数组来实现队列的方式，所以链表也可以进行改进。
改进链表，不能使用之前的链表来进行队列的实现，设置一个 head 变量指向链表的头部第一个节点，设置一个 tail 变量指向链表的尾部第一个节点，有了 tail 这个变量，那么在链表的尾部添加一个元素非常容易，有了 head 和 tail 之后在两端添加节点是非常容易的，但是无法使用O(1)去删除尾部的节点，从 tail 这一端删除元素并不容易，但是如果将 head 作为队首，将 tail 作为队尾，队列操作是从队尾进队首出的，只需要从队尾 tail 插入元素，从队首 head 删除元素，这样一来就可以实现队列的功能。
链表中不再有插入的功能所以不需要 dummyHead，但是由于没有 dummyHead，所以需要注意链表为空的情况。
让自定义动态数组队列与自定义链表队列进行对比，自定义动态数组队列的性能最差自定义动态数组循环队列与自定义链表队列的性能相近。
与链表相关的有一个非常重要的内容，就是递归，因为链表本身具有天然的递归性质，同时它又是一种非常简单的数据结构，所以链表是一种非常好的研究学习递归的逻辑机制的的数据结构。
代码示例
( class: MyArray, class: MyQueue, class: MyLoopQueue, class: MyLinkedListQueue, class: Main)
MyArray
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyQueue
class MyQueue {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入队
enqueue(element) {
this.myArray.push(element);
}
// 出队
dequeue() {
return this.myArray.shift();
}
// 查看队首的元素
getFront() {
return this.myArray.getFirst();
}
// 查看队列中实际元素的个数
getSize() {
return this.myArray.getSize();
}
// 查看 队列当前的容量
getCapacity() {
return this.myArray.getCapacity();
}
// 查看队列是否为空
isEmpty() {
return this.myArray.isEmpty();
}
// 输出队列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Queue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLoopQueue
class MyLoopQueue {
constructor(capacity = 10) {
// 初始化新数组
this.data = new Array(capacity);
// 初始化 队首、队尾的值 (索引)
this.front = this.tail = 0;
// 队列中实际元素个数
this.size = 0;
}
// 扩容
resize(capacity) {
let newArray = new Array(capacity);
let index = 0;
for (let i = 0; i < this.size; i++) {
// 索引可能会越界，于是就要取余一下，
// 如果越界了，就从队首开始
index = (this.front + i) % this.getCapacity();
newArray[i] = this.data[index];
}
this.data = newArray;
this.front = 0;
this.tail = this.size;
}
// 入队
enqueue(element) {
// 判断队列中是否已满
if ((this.tail + 1) % this.getCapacity() === this.front) {
this.resize(this.getCapacity() * 2);
}
this.data[this.tail] = element;
this.tail = (this.tail + 1) % this.getCapacity();
this.size++;
}
// 出队
dequeue() {
// 判断队列是否为空
if (this.isEmpty()) {
throw new Error("can't dequeue from an empty queue.");
}
let element = this.data[this.front];
this.data[this.front] = null;
this.front = (this.front + 1) % this.getCapacity();
this.size--;
// 当size 为容量的四分之一时就缩容一倍
if (this.size === Math.floor(this.getCapacity() / 4)) {
this.resize(Math.floor(this.getCapacity() * 2));
}
return element;
}
// 查看队首的元素
getFront() {
if (this.isEmpty()) {
throw new Error('queue is empty.');
}
return this.data[front];
}
// 查看实际的元素个数
getSize() {
return this.size;
}
// 查看容量
getCapacity() {
return this.data.length;
}
// 队列是否为空
isEmpty() {
// return this.size === 0;
return this.front == this.tail;
}
// 输出循环队列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `LoopQueue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListQueue
class MyLinkedListQueue {
constructor() {
this.front = this.tail = null;
this.size = 0;
}
// 入队
enqueue(element) {
// 判断队尾是否为空
if (this.tail === null) {
// 第一个节点 即是尾也是头
this.tail = new MyLinkedListNode(element, null);
this.front = this.tail;
} else {
let node = new MyLinkedListNode(element, null);
this.tail.next = node;
this.tail = node;
}
this.size++;
}
// 出队
dequeue() {
// 判断队首是否为空
if (this.front === null) {
throw new Error('front is empty.');
}
let delNode = this.front;
let element = delNode.element;
this.front = this.front.next;
delNode = null;
if (this.front === null)
// 如果头为空了，那么尾部也为空
this.tail = null;
this.size--;
return element;
}
// 查看队首的元素
getFront() {
// 判断队首是否为空
if (this.front === null) {
throw new Error('front is empty.');
}
return this.front.element;
}
// 查看队列中实际元素的个数
getSize() {
return this.size;
}
// 判断队列是否为空
isEmpty() {
return this.size === 0;
}
// 输出队列中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListQueue: size = ${this.getSize()}，\n`;
arrInfo += `data = front [`;
let node = this.front;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += '] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedListQueue Area');
let myLinkedListQueue = new MyLinkedListQueue();
for (let i = 1; i <= 5; i++) {
myLinkedListQueue.enqueue(i);
console.log(myLinkedListQueue.toString());
}
console.log(myLinkedListQueue.getFront());
this.show(myLinkedListQueue.getFront());
for (let i = 0; i < 5; i++) {
console.log(myLinkedListQueue.toString());
myLinkedListQueue.dequeue();
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
class Student {
constructor(studentName, studentScore) {
this.name = studentName;
this.score = studentScore;
}
toString() {
let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
return studentInfo;
}
}
window.onload = function() {
// 执行主函数
new Main();
};
