概念和用途

数组存在长度局限

数组的效率不如链表快，js中是用对象来实现的数组

链表可以用在任何一维数组的位置

关键定义

链表是一系列节点组成的集合，每个节点都是用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。（也就是箭头线的那个连接关系）

单向链表和双向链表

  1.         // 单向链表
  2.         // 1. 抽象一个node节点
  3.         function Node(ele) {
  4.             this.element = ele;
  5.             this.next = null;
  6.         }
  8.         // 2. 抽象单向链操作类
  9.         function LList() {
  10.             // 2.1 头节点
  11.             this.head = new Node('head');
  12.             // 2.2 find方法，查找某个节点
  13.             this.find = find;
  14.             // 2.3 insert 插入
  15.             this.insert = insert
  16.             // 2.3 display 遍历链表
  17.             this.display = display
  18.             // 2.4 寻找上一个
  19.             this.findPrevious = findPrevious
  20.             // 2.5 移除（依赖于寻找上一个）
  21.             this.remove = remove
  22.             // 2.6 check一个节点是否存在，存在才可以继续find
  23.             this.check = check
  24.         }
  26.         function check(ele) {
  27.             var currNode = this.head;
  28.             while (currNode != null && currNode.element != ele) {
  29.                 currNode = currNode.next;
  30.             }
  31.             if (currNode == null) return false;
  32.             return true
  33.         }
  34.         function find(ele) {
  35.             var currNode = this.head;
  36.             while (currNode.element != ele) {
  37.                 // 课程里面没有这个，导致find一个不存在的节点时候，死循环了，通过判断返回最后一个节点即可
  38.                 if (currNode.next == null) {
  39.                     return currNode;
  40.                 }
  41.                 currNode = currNode.next;
  42.             }
  43.             return currNode;
  44.         }
  46.         function insert(ele, target) {
  47.             // 1. 现有新节点
  48.             var newNode = new Node(ele);
  49.             // 2. 查找要插入的节点
  50.             if (!this.check(target)) {
  51.                 console.log('无法插入')
  52.                 return
  53.             }
  54.             var currNode = this.find(target);
  55.             // 3. 开始插入(变换指针方向)
  56.             newNode.next = currNode.next;
  57.             currNode.next = newNode;
  58.         }
  60.         function display() {
  61.             var currNode = this.head;
  62.             while (currNode.next != null) {
  63.                 console.log(currNode.next.element);
  64.                 // 第一次实现没写地下这个，导致死循环了
  65.                 currNode = currNode.next
  66.             }
  67.             console.log('--------diplay done------')
  68.         }
  70.         function findPrevious(ele) {
  71.             var currNode = this.head;
  72.             if (currNode.element == ele) {
  73.                 return currNode
  74.             }
  75.             // 第一次实现写成了 currNode!= null && currNode.element!= ele  大概是脑子进屎了吧
  76.             while(currNode.next!= null && currNode.next.element!= ele) {
  77.                 currNode = currNode.next
  78.             }
  79.             return currNode
  80.         }
  82.         function remove(ele) {
  83.             if(!this.check(ele)){
  84.                 console.log('不存在节点，不必删除')
  85.                 return
  86.             }
  87.             var currNode = this.find(ele)
  88.             var prevNode = this.findPrevious(ele)
  89.             prevNode.next = currNode.next
  90.             currNode.next = null
  92.         }
  95.         var pList = new LList();
  96.         pList.insert('p2', 'head');
  97.         pList.insert('p3', 'p2');
  98.         pList.insert('p4', 'p3')
  99.         // pList.display();
  100.         console.log('-----表演移除和寻找上一个------')
  101.         console.log(pList.findPrevious('p99'))
  102.         pList.remove('p33')
  103.         pList.remove('p3')
  104.         pList.display();
  1. // 双向链表   理解透双向链表的图示然后根据理解编写即可
  2.         // 1. 抽象一个node节点
  3.         function Node(ele) {
  4.             this.element = ele;
  5.             this.next = null;
  6.             // 比单向链表多了前驱节点
  7.             this.previous = null;
  8.         }
  10.         // 2. 抽象双向链操作类
  11.         function LList() {
  12.             // 2.1 头节点
  13.             this.head = new Node('head');
  14.             // 2.2 find方法，查找某个节点
  15.             this.find = find;
  16.             // 2.3 insert 插入
  17.             this.insert = insert
  18.             // 2.3 display 遍历链表
  19.             this.display = display
  20.             // // 2.4 寻找上一个   双向链表可以直接访问
  21.             // this.findPrevious = findPrevious
  22.             // 2.4 反向遍历
  23.             this.displayReverse = displayReverse
  24.             // 2.4.1  直接到尾节点
  25.             this.findLast = findLast
  26.             // 2.5 移除（依赖于寻找上一个）
  27.             this.remove = remove
  28.             // 2.6 check一个节点是否存在，存在才可以继续find
  29.             this.check = check
  30.         }
  32.         function check(ele) {
  33.             var currNode = this.head;
  34.             while (currNode != null && currNode.element != ele) {
  35.                 currNode = currNode.next;
  36.             }
  37.             if (currNode == null) return false;
  38.             return true
  39.         }
  40.         function find(ele) {
  41.             var currNode = this.head;
  42.             while (currNode.element != ele) {
  43.                 // 课程里面没有这个，导致find一个不存在的节点时候，死循环了，通过判断返回最后一个节点即可
  44.                 if (currNode.next == null) {
  45.                     return currNode;
  46.                 }
  47.                 currNode = currNode.next;
  48.             }
  49.             return currNode;
  50.         }
  52.         function insert(ele, target) {
  53.             // 1. 现有新节点
  54.             var newNode = new Node(ele);
  55.             // 2. 查找要插入的节点
  56.             if (!this.check(target)) {
  57.                 console.log('无法插入')
  58.                 return
  59.             }
  60.             var currNode = this.find(target);
  62.             newNode.next = currNode.next;
  63.             newNode.previous = currNode
  64.             currNode.next = newNode
  65.             // 判断是否是尾节点
  66.             if (newNode.next != null) {
  67.                 newNode.next.previous = newNode
  68.             }
  69.         }
  71.         function display() {
  72.             var currNode = this.head;
  73.             while (currNode.next != null) {
  74.                 console.log(currNode.next.element);
  75.                 // 第一次实现没写地下这个，导致死循环了
  76.                 currNode = currNode.next
  77.             }
  78.             console.log('--------diplay done------')
  79.         }
  81.         function findPrevious(ele) {
  82.             var currNode = this.head;
  83.             if (currNode.element == ele) {
  84.                 return currNode
  85.             }
  86.             // 第一次实现写成了 currNode!= null && currNode.element!= ele  大概是脑子进屎了吧
  87.             while(currNode.next!= null && currNode.next.element!= ele) {
  88.                 currNode = currNode.next
  89.             }
  90.             return currNode
  91.         }
  93.         function remove(ele) {
  94.             if(!this.check(ele)){
  95.                 console.log('不存在节点，不必删除')
  96.                 return
  97.             }
  98.             var currNode = this.find(ele)
  99.             var prevNode = currNode.previous
  100.             prevNode.next = currNode.next
  101.             currNode.next.previous = prevNode
  102.             currNode.next = null
  104.         }
  105.         function displayReverse() {
  106.             var currNode = this.findLast()
  107.             while(currNode.previous != null) {
  108.                 console.log(currNode.element)
  109.                 currNode = currNode.previous
  110.             }
  111.         }
  112.         function findLast() {
  113.             var currNode = this.head
  114.             while(currNode.next != null) {
  115.                 currNode = currNode.next
  116.             }
  117.             return currNode
  118.         }
  121.         var pList = new LList();
  122.         pList.insert('p2', 'head');
  123.         pList.insert('p3', 'p2');
  124.         pList.insert('p4', 'p3')
  125.         // pList.display();
  126.         console.log('-----表演移除和寻找最后一个------')
  127.         // console.log(pList.findLast())
  128.         // pList.displayReverse()
  129.         // console.log(pList.findPrevious('p99'))
  130.         pList.remove('p33')
  131.         pList.remove('p3')
  132.         pList.displayReverse();