定义

链表是一种物理存储但愿上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低。

优缺点

优点

  • 插入快和删除快，由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表要快

  • 可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

    缺点

  • 查找慢，查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

  • 空间开销较大，原因是增加了节点的指针域
  • 不允许随机读取

    种类

    单向链表

    image.png
    其中，data中保存着数据，next保存着下一个链表的引用。上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。上图，值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。
    由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。进过改造，链表就成了如下的样子：
    image.png
    向链表中插入一个节点的效率很高，需要修改它前面的节点(前驱)，使其指向新加入的节点，而将新节点指向原来前驱节点指向的节点即可。下面我将用图片演示如何在 data2 节点 后面插入 data4 节点。
    image.png
    同样，从链表中删除一个节点，也很简单。只需将待删节点的前驱节点指向待删节点的，同时将待删节点指向null，那么节点就删除成功了。如下图image.png

    实现

    设计链表包含两个类，一个是 Node 类用来表示节点，另一个事 LinkedList 类提供插入节点、删除节点等一些操作。 ```javascript // Node类包含连个属性： element 用来保存节点上的数据，next 用来保存指向下一个节点的链接 //节点类 function Node(element) { this.element = element; //当前节点的元素 this.next = null; //下一个节点链接 }

// LinkedList类提供了对链表进行操作的方法，包括插入删除节点，查找给定的值等。值得注意的是，它只有一个 // 属性，那就是使用一个 Node 对象来保存该链表的头节点。 //链表类 function LList () { this.head = new Node( ‘head’ ); //头节点 this.find = find; //查找节点 this.insert = insert; //插入节点 this.remove = remove; //删除节点 this.findPrev = findPrev; //查找前一个节点 this.display = display; //显示链表 }

// find：查找给定节点 // 创建一个新节点，将链表的头节点赋给这个新创建的节点，然后在链表上循环， // 如果当前节点的 element 属性和我们要找的信息不符，就将当前节点移动到下一个节点， // 如果查找成功，该方法返回包含该数据的节点；否则，就会返回null。 function find ( item ) { var currNode = this.head; while ( currNode.element != item ){ currNode = currNode.next; } return currNode; }

// insert插入 // 在一个已知节点后插入新节点，我们首先得用find方法找到该节点。 function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; currNode.next = newNode; }

// display显示链表 将头节点赋给一个新的变量，然后循环链表，直到当前节点的 next 属性为 null 时停止循环， // 我们循环过程中将每个节点的数据打印出来就好了。 function display () { var currNode = this.head; while ( !(currNode.next == null) ){ console.log( currNode.next.element ); currNode = currNode.next; } }

// remove：从链表中删除一个节点 // 链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。 // 那么，我们就得需要定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。 // 如果找到，返回该节点，这样就可以修改它的 next 属性了。 findPrevious 的实现。 function findPrev( item ) { var currNode = this.head; while ( !( currNode.next == null) && ( currNode.next.element != item )){ currNode = currNode.next; } return currNode; }

function remove ( item ) { var prevNode = this.findPrev( item ); if( !( prevNode.next == null ) ){ prevNode.next = prevNode.next.next; } }

  1. <a name="RDhJG"></a>
  2. ### 双向链表
  3. 尽管从链表的头节点遍历链表很简单，但是反过来，从后向前遍历却不容易。我们可以通过给Node类增加一个previous属性，让其指向前驱节点的链接，这样就形成了双向链表<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/305942/1599454754425-07338970-b7d9-4a86-b9f9-ef014cfe54a0.png#align=left&display=inline&height=178&margin=%5Bobject%20Object%5D&name=image.png&originHeight=178&originWidth=952&size=37187&status=done&style=none&width=952)<br />此时，向链表插入一个节点就要更改节点的前驱和后继了，但是删除节点的效率提高了，不再需要寻找待删除节点的前驱节点了。
  4. <a name="5etBK"></a>
  5. #### 实现
  6. ```javascript
  7. //节点类
  8. function Node(element) {
  9.     this.element = element;   //当前节点的元素
  10.     this.next = null;         //下一个节点链接
  11.     this.previous = null;     //上一个节点链接
  12. }
  14. //链表类
  15. function LList () {
  16.     this.head = new Node( 'head' );     //头节点
  17.     this.find = find;                   //查找节点
  18.     this.insert = insert;               //插入节点
  19.     this.remove = remove;               //删除节点
  20.     this.findPrev = findPrev;           //查找前一个节点
  21.     this.display = display;             //显示链表
  22. }
  24. // 查找给定节点
  25. function find ( item ) {
  26.     var currNode = this.head;
  27.     while ( currNode.element != item ){
  28.         currNode = currNode.next;
  29.     }
  30.     return currNode;
  31. }
  33. // 向尾部添加节点
  34. function append(newElement){
  35.     var newNode = new Node( newElement );
  36.       var currNode = this.head;
  37.     while (currNode.next) {
  38.       currNode = currNode.next
  39.       }
  40.       currNode.next = newNode
  41. }
  43. //插入节点
  44. // 双向链表的 insert 方法与单链表相似，但需要设置新节点的 previous 属性，使其指向该节点的前驱
  45. function insert ( newElement , item ) {
  46.     var newNode = new Node( newElement );
  47.     var currNode = this.find( item );
  48.     newNode.next = currNode.next;
  49.     newNode.previous = currNode;
  50.     currNode.next = newNode;
  51. }
  53. // 删除节点
  54. // 双向链表的删除 remove 方法比单链表效率高，不需要查找前驱节点，只要找出待删除节点，
  55. // 然后将该节点的前驱 next 属性指向待删除节点的后继，设置该节点后继 previous 属性，
  56. // 指向待删除节点的前驱即可
  57. function remove ( item ) {
  58.     var currNode = this.find ( item );
  59.     if( !( currNode.next == null ) ){
  60.         currNode.previous.next = currNode.next;
  61.         currNode.next.previous = currNode.previous;
  62.         currNode.next = null;
  63.         currNode.previous = null;
  64.     }
  65. }
  67. //显示链表元素
  68. function display () {
  69.     var currNode = this.head;
  70.     while ( !(currNode.next == null) ){
  71.         console.debug( currNode.next.element );
  72.         currNode = currNode.next;
  73.     }
  74. }
  76. //反向显示链表元素
  77. function dispReverse () {
  78.     var currNode = this.findLast();
  79.     while ( !( currNode.previous == null )){
  80.         console.log( currNode.element );
  81.         currNode = currNode.previous;
  82.     }
  83. }

循环链表

循环链表和单链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性执行它本身，即

  1. head.next = head;

这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表，如下图所示：
image.png

实现

  1. function DoublyLinkedList() {
  2.     var Node = function(element) {
  3.         this.element = element;
  4.         this.next = null;
  5.         this.prev = null;
  6.     };
  8.     var length = 0,
  9.         head = null,
  10.         tail = null;
  12.     this.append = function(element){
  13.         var node = Node(element),
  14.             current,
  15.             previous;
  17.         if(!head){
  18.             head = node;
  19.             tail = node;
  20.         }else{
  21.             current = head;
  22.             while(current){
  23.                 previous = current;
  24.                 current = current.next;
  25.             }
  27.             node.next = current;
  28.             current.prev = node;
  29.             previous.next = node;
  30.             node.prev = previous;
  31.         }
  33.         length++;
  34.         return true;
  35.     }
  37.     this.insert = function(position,element){
  38.         if(position > -1 && position < length){
  39.             var node = new Node(element),
  40.                 current = head,
  41.                 previous,
  42.                 index = 0;
  43.             if(position === 0){
  44.                 if(!head){
  45.                     head = node;
  46.                     tail = node;
  47.                 }else{
  48.                     node.next = current;
  49.                     current.prev = node;
  50.                     head = node;
  51.                 }
  53.             }else if (position === length -1){
  54.                 current = tail;
  55.                 current.next = node;
  56.                 node.prev = current;
  57.             }else {
  58.                 while(index++ < position){
  59.                     previous = current;
  60.                     current = current.next;
  61.                 }
  62.                 node.next = current;
  63.                 previous.next = node;
  64.                 current.prev = node;
  65.                 node.prev = previous;
  66.             }
  68.             length++;
  69.             return true;
  70.         }else{
  71.             return false;
  72.         }
  73.     };
  75.     this.removeAt = function(position){
  76.         if(position > -1 && position < length){
  77.             var current = head,
  78.                 index = 0,
  79.                 previous;
  81.             if (position === 0) {
  82.                 head = current.next;
  84.                 if(length === 1){
  85.                     tail = null;
  86.                 }else{
  87.                     head.prev = null;
  88.                 }
  89.             }else if(position === length - 1){
  90.                 current = tail;
  91.                 tail = current.prev;
  92.                 tail.next = null;
  93.             } else{
  94.                 while(index++ < position){
  95.                     previous = current;
  96.                     current = current.next;
  97.                 }
  99.                 previous.next = current.next;
  100.                 current.next.prev = previous;
  101.             };
  102.             length-- ;
  104.             return current.element;
  105.         }else{
  106.             return false;
  107.         }
  108.     };
  110.     this.remove = function(element){
  111.         var current = head,
  112.             previous;
  114.         if(current.element === element){
  115.             head = current.next;
  116.         }
  117.         previous = current;
  118.         current = current.next;
  120.         while(current){
  121.             if (current.element = element) {
  122.                 previous.next = current.next;
  123.                 current.next.prev = previous;
  124.             }else{
  125.                 previous = current;
  126.                 current = current.next;
  127.             }
  128.         }
  129.         return false;
  130.     };
  132.     this.remove = function(){
  133.         if (length === 0) {
  134.             return false;
  135.         };
  137.         var current = head,
  138.             previous;
  140.         if(length === 1){
  141.             head = null;
  142.             tail = null;
  143.             length--;
  144.             return current.element;
  145.         }
  147.         while(current){
  148.             previous = current;
  149.             current = current.next;
  150.         }
  152.         previous.next = null;
  153.         length--;
  154.         return current.element;
  155.     };
  157.     this.indexOf = function(element){
  158.         var current = head,
  159.             index = 0;
  161.         while(current && index++ < length){
  162.             if (current.element === element) {
  163.                 return index;
  164.             };
  165.             current = current.next;
  166.         }
  168.         return false;
  169.     };
  171.     this.isEmpty = function(){
  172.         return length === 0;
  173.     };
  175.     this.size = function(){
  176.         return length;
  177.     };
  179.     this.toString = function(){
  180.         var current = head,
  181.             string = '';
  183.         while(current){
  184.             string += current.element;
  185.             current = current.next;
  186.         }
  187.         return string;
  188.     };
  190.     this.getHead = function(){
  191.         return head;
  192.     };
  194.     this.getTail = function(){
  195.         return tail;
  196.     };
  197. }

双向循环链表

将双向链表的头尾指针相连，就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历，查询节点的速度也是最快的。

实现

  1. function DoublyCircularLinkedList(){
  2.     var Node = function(element){
  3.         this.element = element;
  4.         this.next = null;
  5.         this.prev = null;
  6.     };
  8.     var length = 0,
  9.         head = null,
  10.         tail = null;
  12.     this.append = function(element){
  13.         var node = new Node(element),
  14.             current,
  15.             previous;
  17.         if (!head) {
  18.             head = node;
  19.             tail = node;
  20.             head.prev = tail;
  21.             tail.next = head;
  22.         }else{
  23.             current = head;
  25.             while(current.next !== head){
  26.                 previous = current;
  27.                 current = current.next;
  28.             }
  30.             current.next = node;
  31.             node.next = head;
  32.             node.prev = current;
  33.         };
  35.         length++;
  36.         return true;
  37.     };
  39.     this.insert = function(position, element){
  40.         if(position >= 0 && position <= length){
  41.             var node = new Node(element),
  42.                 index = 0,
  43.                 current = head,
  44.                     previous;
  46.             if(position === 0){
  48.                 if(!head){
  50.                     node.next = node;
  51.                     node.tail = node;
  52.                     head = node;
  53.                     tail = node;
  55.                 }else{
  57.                     current.prev = node;
  58.                     node.next = current;
  59.                     head = node;
  60.                     node.prev = tail;
  62.                 }
  64.             }else if(position === length){
  65.                 current = tail;
  67.                 current.next = node;
  68.                 node.prev = current;
  69.                 tail = node;
  70.                 node.next = head;
  71.             }else{
  73.                 while(index++ < position){
  74.                     previous = current;
  75.                     current = current.next;
  76.                 }
  78.                 current.prev = node;
  79.                 node.next = current;
  80.                 previous.next = node;
  81.                 node.prev = previous;
  83.             }
  85.             length++;
  86.             return true;
  87.         }else{
  88.             return false;
  89.         }
  90.     };
  92.     this.removeAt = function(position){
  93.         if(position > -1 && position < length){
  95.             var current = head,
  96.                 index = 0,
  97.                 previous;
  99.             if(position === 0){
  101.                 current.next.previous = tail;
  102.                 head = current.next;
  104.             }else if(position === length - 1){
  106.                 current = tail;
  108.                 current.prev.next = head;
  109.                 head.prev = current.prev;
  110.                 tail = current.prev;
  111.             }else{
  113.                 while(index++ < position){
  114.                     previous = current;
  115.                     current = current.next;
  116.                 }
  118.                 previous.next = current.next;
  119.                 current.next.prev = previous;
  121.             }
  123.             length--;
  124.             return true;
  125.         }else{
  126.             return false;
  127.         }
  128.     };
  130.     this.remove = function(element){
  131.         var current = head,
  132.             previous,
  133.             indexCheck = 0;
  135.         while(current && indexCheck < length){
  136.             if(current.element === element){
  137.                 if(indexCheck === 0){
  138.                     current.next.prev = tail;
  139.                     head = current.next;
  140.                 }else{
  141.                     current.next.prev = previous;
  142.                     previous.next = current.next;
  143.                 }
  144.                 length--;
  145.                 return true;
  146.             }
  148.             previous = current;
  149.             current = current.next;
  150.             indexCheck++;
  151.         }
  153.         return false;
  154.     };
  156.     this.remove = function(){
  157.         if(length === 0){
  158.             return false;
  159.         }
  161.         var current = head,
  162.             previous,
  163.             indexCheck = 0;
  165.         if(length === 1){
  166.             head = null;
  167.             tail = null;
  168.             length--;
  169.             return current.element;
  170.         }
  172.         while(indexCheck++ < length){
  173.             previous = current;
  174.             current = current.next;
  175.         }
  177.         previous.next = head;
  178.         tail = previous.next;
  179.         length--;
  180.         return current.element;
  181.     };
  183.     this.indexOf = function(element){
  184.         var current = head,
  185.             index = 0;
  187.         while(current && index++ < length){
  188.             if(current.element === element){
  189.                 return index;
  190.             }
  191.             current = current.next;
  192.         }
  194.         return false;
  195.     };
  197.     this.toString = function(){
  198.         var current = head,
  199.             indexCheck = 0,
  200.             string = '';
  202.         while(current && indexCheck < length){
  203.             string += current.element;
  204.             indexCheck++;
  205.             current = current.next;
  206.         }    
  208.         return string;
  209.     };
  211.     this.isEmpty = function(){
  212.         return length === 0;
  213.     };
  215.     this.getHead = function(){
  216.         return head;
  217.     };
  219.     this.getTail = function(){
  220.         return tail;
  221.     };
  223.     this.size = function(){
  224.         return length;
  225.     };
  226. }

https://www.cnblogs.com/zhuwq585/p/6075117.html

参考自 https://www.jianshu.com/p/f254ec665e57 https://www.cnblogs.com/xbblogs/p/9897118.html