数组是很常见的数据类型。得益于相当友好于开发者们对数据进行操作， 数组成了套路之王了！
当然，友好于开发者，肯定会失去很多的。它就不是很友好于性能优化了，当然，当今的硬件技术发展下，一般的小项目根本就跟前端层面的性能优化无瓜的。

数组的优点：

根据下标，赋值，取值，很方便，存储型的操作！查找，赋值，取值，性能强！

缺点：

扩容，很消耗性能！
数组在低层创建时是要声明长度的！JS视角只是表层，面向内存，数组声明时，内存就把相邻连续的一块区域划分给数组了，区域大小跟声明的数组长度挂钩。
问题来了，数组可以随意地push，shift，，，就需要扩容了，扩容等同于新创建一个数组，长度是扩容时设置的长度，然后把原本的数据依次拷贝过来，然后删除原数组的内存区块。太消耗性能了！
另外,
中间插入，中间删除，首部插入，首部删除，会导致操作位置后面的所有的数据在原内存地址上依次顺序改动。

我对数组的理解：

数组就是人心中的理想的数据类型，人的暴力美学，数组操作多简单！就算是扩容，就算是中间插入删除，又咋了？堂堂正正的阳谋！不就是性能差么？又不是不能用.jif！

针对优缺点，既可以思考：数组的使用场景！比如前端，，，数据量不大时，从来就没怂过！JSON.parse(JSON.stringify(xxx))都无所畏惧，，，

当然，理性地思考，数组适合于多查找，多编辑，少中间首部插入或删除的操作。偏向于读和写的操作场景了！

对数组不适用于中间，首部的插入删除，还有扩容问题，另一种链式数据结构算是跟它完全反过来了！

链表

完全是针对数组的么！
不需要扩容！随意任何位置的元素进行插入，删除！牛皮！偏向于频繁地增删的操作场景！
这么友好于性能，，，终究是无法打破必须不完美的铁律了。它的读写性能不高，查找不如数组快。

优点

  • 因为不必像数组一样是内存里的一块连续的内存区域，相对于内存很友好，充分榨取内存的剩余价值。源于链表的数据结构，存储的有下一个节点的地址。
  • 插入和删除操作性能快。
  • 理论上只要内存够，想存多少数据就存多少，扩啥容？

缺点

读取一个节点，就要遍历一遍链表，因为它的内存地址不连续。所以，性能不如数组直接靠下标来得快！

数据结构

截屏2020-03-29 上午11.48.27.png

很典型的因果论哲学模型！比如一个人的成长历史，从小学，到初中，高中，大学。讲究因果联系！

单链表的封装

  1. //链表的封装
  2. class LinkedList {
  3.     constructor(list) {
  4.         this.header = list || null;
  5.         this.length = list ? 1 : 0;
  6.     }
  8.     append(data) {
  9.         const list = new List(data);
  10.         if (this.length === 0) {
  11.             return this.header = list;
  12.         }
  13.         let current = this.header;
  14.         while (current.next) {
  15.             current = current.next;
  16.         }
  17.         current.next = list;
  18.         this.length += 1;
  19.     }
  21.     insert(data, index) {
  22.         if (index < 0 || index > this.length) {
  23.             throw new Error("index参数不合理");
  24.         }
  25.         const list = new List(data);
  26.         let oldList = this.header;
  27.         if (index === 0) {
  28.             oldList && (list.next = oldList);
  29.             this.header = list;
  30.         } else {
  31.             let i = 0;
  32.             while (i < index - 1) {  //index-1是找的index-1的那个点，index点可以通过它找到
  33.                 oldList = oldList.next;
  34.                 i++;
  35.             }
  36.             let next = oldList.next;
  37.             oldList.next = list;
  38.             list.next = next;
  39.         }
  40.         this.length++;
  41.     }
  43.     get(position) {
  44.         if (position > this.length - 1 || position < 0) {
  45.             throw new Error("位置参数超出范围了！");
  46.         }
  47.         let current = this.header;
  48.         if (position === 0) return current;
  49.         let i = 0;
  50.         while (i < position) {
  51.             current = current.next;
  52.             i++;
  53.         }
  54.         return current;
  55.     }
  57.     update(position, data) {
  58.         this.get(position).data = data;
  59.         return true;
  60.     }
  62.     indexOf(data,key) {
  63.         let current = this.header;
  64.         if (!current) return -1;
  65.         let index;
  66.         let i = 0;
  67.         while (!index && current) {
  68.           //这里是扩展了一下如果data是复杂类型的时候，凭关键字段匹配的情况：
  69.           //在用哈希表的时候，我不得不扩展
  70.             if ( (key ? current.data[key]:current.data) === data) {
  71.                 index = i;
  72.             } else {
  73.                 current = current.next;
  74.                 i++;
  75.             }
  76.         }
  77.         return index >= 0 ? index : -1;
  78.     }
  80.     removeAt(position) {
  81.         if (position < 0 || position > this.length - 1 || this.length === 0) {
  82.             throw new Error("参数超出范围！");
  83.         }
  84.         let current = this.header;
  85.         if (position === 0) {
  86.             this.length -= 1;
  87.             this.header = current.next;
  88.             return current;
  89.         } else {
  90.             let i = 0;
  91.             while (i < position - 1) {
  92.                 current = current.next;
  93.                 i++;
  94.             }
  95.             const target = current.next;
  96.             if (target) {
  97.                 current.next = target.next;
  98.                 this.length -= 1;
  99.                 return target;
  100.             }
  101.         }
  102.     }
  104.     remove(data) {
  105.         const index = this.indexOf(data);
  106.         return this.removeAt(index);
  107.     }
  109.     size() {
  110.         return this.length;
  111.     }
  113.     isEmpty() {
  114.         return this.length === 0;
  115.     }
  117.     toString() {
  118.         let current = this.header;
  119.         let res = "";
  120.         while (current) {
  121.             res += (res ? " -> " : "") + current.data;
  122.             current = current.next;
  123.         }
  124.         return res;
  125.     }
  126. }
  128. class List {
  129.     constructor(data, next) {
  130.         this.data = data;
  131.         this.next = next ? next : null;
  132.     }
  133. }
  135. const list = new List(1);
  136. const linkedList = new LinkedList(list);
  137. console.log(linkedList);
  138. linkedList.append(30);
  139. linkedList.insert("2", 1);
  140. linkedList.insert("0", 0);
  141. linkedList.insert("6", 3);
  142. linkedList.insert("20", 4);
  143. linkedList.insert("89", 6);
  144. console.log(linkedList, linkedList.toString(), 888, linkedList.get(3),);
  145. console.log(linkedList.indexOf(3), linkedList.update(3, 10), linkedList.get(3));
  146. console.log(linkedList.removeAt(3), linkedList.toString());
  147. console.log(linkedList.remove("20"), linkedList.toString(),linkedList.size());

单链表的数据模型很清晰，像舞龙队。舞龙一堆人，其实，隔了很远，如何心意相通，互相完美配合，就是后面的人只关心前面的那一个人。一条链下来。还有一个游戏，就是传话，几个人一个次序方向传话。
由此，看出局限性了，节点只知道下一个节点是谁，只能一个方向次序操作，，，如果遇到一个节点，想要反方向操作上一个节点，怎么办？
比如文本编辑器的光标一行一行地向上向下移动。
需求是，一个节点既可以拿到下一个节点，单链表实现了。又可以拿到它的上一个节点，双链表可以的！

双向链表

其实就是在单链表的优点缺点的基础上，增加了点增删复杂的操作，增加了上一个节点的操作。增加了内存的消耗，其实也就是添加了一个prev的字段，跟功能比起来，可以看不见。
性能一样的。魔改版的单链表。
当然，双链表在性能跟单链表相同的情况下，功能更加完善了。它成了主流了！
截屏2020-03-30 上午10.47.00.png
截屏2020-03-30 上午10.47.25.png
一看，就可以知道，增删的方法时，要修改的属性会相当的多的。
截屏2020-03-30 上午11.00.31.png

双链表的实现封装：

  1. class DoublyLinkedList extends LinkedList {
  2.     constructor(list) {
  3.         super(list);
  4.         this.tail = list || null;
  5.     }
  7.     append(data) {
  8.         const list = new DoublyList(data);
  9.         if (this.length === 0) {
  10.             list.prev = null;
  11.             this.header = list;
  12.             this.tail = list;
  13.         } else {
  14.             const last = this.tail;
  15.             last.next = list;
  16.             list.prev = last;
  17.             this.tail = list;
  18.         }
  19.         this.length += 1;
  20.     }
  22.     insert(data, index) {
  23.         if (index < 0 || index > this.length) {
  24.             throw new Error("插入的下标超出范围！");
  25.         }
  26.         const list = new DoublyList(data);
  27.         if (index === 0) {
  28.             const current = this.header;
  29.             if (current) {
  30.                 this.header = list;
  31.                 list.next = current;
  32.                 current.prev = list;
  33.             } else {
  34.                 this.tail = list;
  35.                 this.header = list;
  36.             }
  37.         } else if (index === this.length) {
  38.             const last = this.tail;
  39.             last.next = list;
  40.             list.prev = last;
  41.             this.tail = list;
  42.         } else {
  43.             const test = index * 2 > this.length - 1;
  44.             let i = test ? this.length - 1 : 0;
  45.             let current = test ? this.tail : this.header;
  46.             let key = test ? "prev" : "next";
  47.             if (test) {
  48.                 while (i > index) {
  49.                     current = current[key];
  50.                     i--;
  51.                 }
  52.             } else {
  53.                 while (i < index) {
  54.                     current = current[key];
  55.                     i++;
  56.                 }
  57.             }
  58.             const last = current.prev;
  59.             list.prev = last;
  60.             last.next = list;
  61.             list.next = current;
  62.             current.prev = list;
  63.         }
  65.         this.length++;
  66.     }
  68.     get(index) {
  69.         if (index < 0 || this.length === 0 || index > this.length - 1) {
  70.             throw new Error("超出链表的长度范围");
  71.         }
  72.         const test = index * 2 > this.length - 1;
  73.         let current = test ? this.tail : this.header;
  74.         let i = test ? this.length - 1 : 0;
  75.         const key = test ? "prev" : "next";
  76.         if (test) {
  77.             while (i > index) {
  78.                 current = current[key];
  79.                 i--;
  80.             }
  81.         } else {
  82.             while (i < index) {
  83.                 current = current[key];
  84.                 i++;
  85.             }
  86.         }
  87.         return current;
  88.     }
  90.     removeAt(index) {
  91.         if (index < 0 || this.length === 0 || index > this.length - 1) {
  92.             throw new Error("操作的下标超出范围！");
  93.         }
  94.         const current = this.get(index);
  95.         const last = current.prev;
  96.         const next = current.next;
  97.         if (last) {
  98.             if (next) {
  99.                 last.next = next;
  100.                 next.prev = last;
  101.             } else {
  102.                 this.tail = last;
  103.                 last.next = null;
  104.             }
  105.         } else {
  106.             if (next) {
  107.                 this.header = next;
  108.                 next.prev = null;
  109.             } else {
  110.                 this.header = null;
  111.                 this.tail = null;
  112.             }
  113.         }
  114.         this.length -= 1;
  115.         return current;
  116.     }
  118.     remove(data) {
  119.         // const index = this.indexOf(data);
  120.         // return this.removeAt(index);
  121.       //这里可以简单套用上面的逻辑，但是我又重温了一下，各种逻辑的套路：
  122.         let current = this.header;
  123.         let ind, i = 0;
  124.         while (ind === undefined && current) {
  125.             if (current.data === data) {
  126.                 ind = i;
  127.             }
  128.             current = current.next;
  129.             i++;
  130.         }
  131.         if (ind === undefined) {
  132.             throw new Error("暂无此节点，无法删除！");
  133.         }
  134.         const test = ind * 2 > this.length - 1;
  135.         let cur = test ? this.tail : this.header;
  136.         const key = test ? "prev" : "next";
  137.         let Ind = test ? this.length - 1 : 0;
  138.         if (test) {
  139.             while (Ind > ind) {
  140.                 cur = cur[key];
  141.                 Ind -= 1;
  142.             }
  143.         } else {
  144.             while (Ind < ind) {
  145.                 cur = cur[key];
  146.                 Ind += 1;
  147.             }
  148.         }
  149.         const last = cur.prev;
  150.         const next = cur.next;
  151.         if (last) {
  152.             if (next) {
  153.                 last.next = next;
  154.                 next.prev = last;
  155.             } else {
  156.                 this.tail = last;
  157.                 last.next = null;
  158.             }
  159.         } else {
  160.             if (next) {
  161.                 this.header = next;
  162.                 next.prev = null;
  163.             } else {
  164.                 this.header = null;
  165.                 this.tail = null;
  166.             }
  167.         }
  168.         this.length--;
  169.         return cur;
  170.     }
  172.     update(index, data) {
  173.         const list = this.get(index);
  174.         list.data = data;
  175.         return list;
  176.     }
  178.     backwardString() {
  179.         return this.toString();
  180.     }
  182.     forwardString() {
  183.         let current = this.tail;
  184.         let res = "";
  185.         while (current) {
  186.             res += (res ? " <- " : "") + current.data;
  187.             current = current.prev;
  188.         }
  189.         return res;
  190.     }
  191. }
  193. const doublyList = new DoublyList(1);
  194. const doublyLinkedList = new DoublyLinkedList(doublyList);
  195. doublyLinkedList.append(2);
  196. doublyLinkedList.append(3);
  197. doublyLinkedList.append(4);
  198. doublyLinkedList.insert("哈哈", 2);
  199. doublyLinkedList.update(3, "test");
  200. console.log(doublyLinkedList,
  201.     doublyLinkedList.backwardString(),
  202.     doublyLinkedList.forwardString(),
  203.     doublyLinkedList.get(3),
  204.     doublyLinkedList.indexOf("哈哈")
  205. );
  206. console.log(
  207.     doublyLinkedList.removeAt(3),
  208.     doublyLinkedList.remove(4),
  209.     doublyLinkedList.toString(),
  210. );