链表以head 为头节点，head中不存放任何数据，代表链表的开始
链表也是一种线性表，但是链表中的节点是非连续的，非顺序存储的
链表的顺序是通过指针依次链接链表中的每个节点
链表中有一种双向链表，可以从一个节点查看它的下一个节点，也可以查看它的上一个节点

链表的定义

  1. 链表是线性结构
  2. 链表的存储方式是不连续的，是将零散的内存块串联起来
  3. 每个内存块称为节点Node, 除了存储数据，还需要存储指向下一个内存块的指针
  4. 存储方式，以head为头节点，头节点可以不存放任何数据，它是链表的开始，指向链表中的第一个节点，而每个节点都有一个next的向下引用，指向下一个节点，直到最后一个节点，每个节点由两部分组成，包括data, next

链表中常见的名词

  1. 首元节点，指的是链表中存储第一个数据元素的节点
  2. 头节点，它是在首元节点之前设置的一个节点，其指针指向首元节点
  3. 头指针，指向链表中的第一个节点的指针

使用链表的必要性

  1. 使用链表不需要预先知道大小，去申请内存，它实现动态管理内存
  2. 它的增删O(1）, 随机访问O(n)
    1. 链表的增删只需要改变指针指向
    2. 随机访问需要每次都从头开始遍历
  3. 数组的缺点
    1. 需要申请连续空间，连续空间不足会申请失败
    2. 大小固定，空间不足需扩容的情况下需要进行数据复制
  4. 链表的缺点
    1. 占用内存过大，需要保存额外的指针
    2. 增删频繁的情况下，需要频繁的申请和释放内存，容器产生内存碎片
  5. 选择
    1. 访问操作 > 增删操作 - 数组
    2. 访问操作 < 增删操作 - 链表

常见的链表

  1. 单向链表
    1. 每个节点只包含一个后继指针
    2. 单链表有两个特殊的节点，即首节点和尾结点
    3. 性能，插入和删除节点 O(1), 查找复杂度O(n)
  2. 单向循环链表
    1. 尾结点的后继指针指向首节点的单向链表
  3. 双向链表
    1. 每个节点有两个节点，指向前一个节点地址prev和下一个节点 的指针next
    2. 首节点的前驱指针和尾结点的后继指针均指向空地址
    3. 性能特点
      1. 和单链表相比，存储相同的数据，需要消耗更多的存储空间，每个节点需要存储两个指针
      2. 插入、删除操作比单链表效率更高，O(1)级别
        1. 给定数据值删除对应的节点，单链表和双向链表，都需要从头到尾进行遍历，从而找到对应的节点进行删除，时间复杂度为O(n)
        2. 给定节点地址删除节点，要进行操作必须找到前驱节点，单链表需要从头到尾，进行遍历直到p.next = q, 时间复杂度为 O(n), 而双向链表可以直接找到前驱节点，时间复杂度为O(1)
      3. 对于一个有序链表，双向链表的按值查询效率要比单向链表高一些，可逆向查找，节省查找时间
  4. 双向循环链表
    1. 首节点的前驱指针指向尾结点，尾结点的后继指针指向首节点

单链表的类实现

  1. class Node {
  2.     constructor(el) {
  3.     this.el = el
  4.     this.next = null
  5.   }  
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.       this.head = null
  11.     this.length = 0
  12.   }
  14.   append(el) {
  15.       let node = new Node(el)
  16.     if (this.length == 0) {
  17.         this.head = node;
  18.     } else {
  19.         let current = this.head;
  20.       while(current.next) {
  21.           current = current.next;
  22.       }
  23.       current.next = node;
  24.     }
  25.     ++this.length
  26.   }
  28.   insert(el, pos) {
  29.       let current;
  30.     let previous;
  31.     let node = new Node(el)
  32.     let index = 0;
  33.     if (pos >= 0 && pos <= this.length) {
  34.         if (pos == 0) {
  35.           node.next = this.head;
  36.         this.head = node;
  37.       } else {
  38.           let current = this.head;
  39.         while(index < pos) {
  40.             previous = current;
  41.           current = current.next;
  42.           index++
  43.         }
  44.         node.next = current;
  45.         previous.next = node;
  46.       }
  48.       this.length++
  49.     }
  50.   }
  52.   remove(el) {
  53.     let pos = this.indexOf(el)
  54.     return removeAt(pos)
  55.   }
  57.   removeAt(pos) {
  58.       let previous;
  59.     let current = this.head;
  60.     let index = 0;
  61.     if (pos > - 1 && pos < this.length) {
  62.         if (pos == 0) {
  63.           this.head = current.next;
  64.       } else {
  65.           while(index < pos) {
  66.           previous = current
  67.             current = current.next
  68.                   index++
  69.         }
  70.         previous.next = current.next;
  71.         --this.length;
  72.         return true;
  73.       }
  74.     }
  75.     return false;
  76.   }
  78.   indexOf(el) {
  79.       let index = 0;
  80.     let current = this.head;
  81.     while(current) {
  82.         if (current.el == el) return index;
  83.       current = current.next;
  84.       index++
  85.     }
  86.     return index;
  87.   }
  89.   size() {
  90.       return this.length;
  91.   }
  93.   isEmpty() {
  94.       return this.length == 0;
  95.   }
  97. }
  1. 判断链表中是否有环
    1. const hasCycle = (head) => {
    2.  if (head == null || head.next == null) {
    3.    return false;
    4. }
    5. let slow = fast = head;
    6. while(fast != null && fast.next != null) {
    7.    fast = fast.next.next;
    8.  slow = slow.next;
    9.  if (fast == slow) {
    10.      return true
    11.  }
    12. }
    13. return false;
    14. }

小结

  1. 什么是链表
  2. 链表的优缺点， 增删快，查找慢
  3. 单向和双向链表
  4. 如何查找链表中的环

练习题

查找未知长度链表中倒数第K个元素

方法1

  1. 先遍历链表，获取链表长度
  2. 将链表长度 - k 获取要查找的索引值
  3. 再次遍历数组，获取到该索引位置的值；
  4. 若查找不到，返回-1
  5. 缺点，要遍历两次
  1. /*
  2.     输入： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11;
  3. */
  5. function getLengthOfLinkedList(linkedList) {
  6.     let length = 0;
  7.   let current = linkedList.head;
  8.   if (current == null) return length;
  9.   while(current) {
  10.     length++;
  11.       current = current.next;
  12.   }
  13.   return length;
  14. }
  16. function searchNode(linkedList, k) {
  17.     let index = 0;
  18.   let resultIndex = getLengthOfLinkedList(linkedList) - k;
  19.   let current = linkedList.head
  20.   if (current == null) return -1;
  21.   while(current) {
  22.       if (index === resultIndex) return  current.element; 
  23.     current = current.next;
  24.     index++
  25.   }
  26.   return -1;
  27. }

方法2

  1. 定义两个指针
  2. 先让指针p1 向前移动 k - 1 步
  3. 遍历链表，如果p1 指向了尾结点，此时p2就是我们要找的节点
  4. 只需要遍历一次就可以查找到元素
  1. /*
  2.     输入： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11;
  3. */
  5. function searchNode(linkedList, k) {
  6.     let p1 = linkedList.head
  7.   let p2 = linkedList.head
  9.   for(let i = 0;  i < k - 1; i++) {
  10.       p1 = p1.next;
  11.   }
  13.   while(p1.next) {
  14.       p1 = p1.next;
  15.     p2 = p2.next;
  16.   }
  17.   return p2.elment;
  18. }
  19. console.log(searchNode(linkedList, 3)) // 9