每种编程语言都实现了数组，但在大多数语言中，数组大小是固定的（创建时指定），从数组起点或中间插入或移除元素的成本很高，因为后面的元素都需要挨个挪位置。

1. 链表数据结构

链表是一种动态的数据结构，用于存储有序的元素集合，可以从中任意添加或移除元素，不需要移动其他元素，可按需扩容（如众人手拉手，加个人和减个人都很简单），链表中的元素并不是连续放置的，每个元素由一个存储元素本身的节点，和一个指向下一个元素的引用（也称指针或链接）组成：
image.pngimage.png
数组可以直接访问任何位置的元素（可以理解为是物理电路，访问任意位置的元素都一样快），而想要访问链表中间的元素，就需要从表头开始迭代链表中的节点，挨个寻找，就像藏宝游戏，不断地根据线索寻找。
各自优势：

  • 链表：增、删

  • 数组：改、查

    1.1 创建链表

  • append(element)：向列表尾部添加一个新的项。

  • insert(position, element)：向列表的特定位置插入一个新的项。
  • remove(element)：从列表中移除一项。
  • indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
  • removeAt(position)：从列表的特定位置移除一项。
  • isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
  • size()：返回链表包含的元素个数。与数组的length属性类似。

  • toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。

    1. function LinkedList() {
    3. // 单个节点类，表示要加入到链表中的项
    4. let Node = function (element) {
    5.   this.element = element;
    6.   this.next = null;
    7. };
    9. let length = 0; // 内部私有变量，记录链表长度
    10. let head = null; // 头指针
    12. /**
    13.  * 向链表尾部添加一个新的项
    14.  * 两种场景：链表为空，添加的是第一个元素；链表不为空，向其追加元素。
    15.  *
    16.  * @param element
    17.  */
    18. this.append = function (element) {
    20.   let node = new Node(element), current;
    22.   if (head === null) {
    23.     head = node;
    24.   } else {
    25.     current = head;
    26.     // 从表头开始循环找到最后一项
    27.     while (current.next !== null) {
    28.       current = current.next;
    29.     }
    30.     // 把节点链接到最后一项的 next 上
    31.     current.next = node;
    32.   }
    34.   length++; // 更新链表长度
    35. };
    37. /**
    38.  * 从任意位置移除元素并返回被移除的元素
    39.  * 两种场景：移除第一个元素；移除第一个以外的任一元素。
    40.  * 被移除的元素被丢弃在计算机内存中，等待被垃圾回收器清理。
    41.  *
    42.  * @param {number} position
    43.  * @returns {element|null}
    44.  */
    45. this.removeAt = function (position) {
    47.   // 检查是否越界
    48.   if (position >= 0 && position < length) {
    50.     let current = head,
    51.       previous,
    52.       index = 0;
    54.     // 分两种情况：表头和非表头
    55.     if (position === 0) {
    56.       head = current.next;
    57.     } else {
    58.       // position 的前一个位置时终止循环
    59.       while (index++ < position) {
    60.         previous = current;
    61.         current = current.next;
    62.       }
    63.       // 上下节点进行链接，跳过中间将被移除的 current 节点
    64.       previous.next = current.next;
    65.     }
    67.     length--;
    69.     return current.element;
    70.   } else {
    71.     return null;
    72.   }
    73. };
    75. /**
    76.  * 在任意位置插入元素
    77.  *
    78.  * @param {number} position
    79.  * @param element
    80.  * @returns {boolean}
    81.  */
    82. this.insert = function (position = 0, element) {
    84.   // 检查是否越界,注意这里包含了空链表时的情形
    85.   if (position >= 0 && position <= length) {
    87.     let node = new Node(element),
    88.       current = head,
    89.       previous,
    90.       index = 0;
    92.     if (position === 0) {
    93.       node.next = current;
    94.       head = node;
    95.     } else {
    96.       while (index++ < position) {
    97.         previous = current;
    98.         current = current.next;
    99.       }
    100.       node.next = current; // 即新节点插入到目标位置的前面，这里current可能是null
    101.       previous.next = node;
    102.     }
    104.     length++;
    106.     return true;
    107.   } else {
    108.     return false;
    109.   }
    110. };
    112. /**
    113.  * 把 LinkedList 对象转换成字符串
    114.  *
    115.  * @returns {string}
    116.  */
    117. this.toString = function () {
    118.   let current = head,
    119.     string = '',
    120.     index = 0;
    122.   while (current) {
    123.     string += index++ + ': ' + current.element + (current.next ? '\n' : '');
    124.     current = current.next;
    125.   }
    126.   return string;
    127. };
    129. /**
    130.  * 查找给定元素的索引,找不到则返回 -1
    131.  *
    132.  * @param element
    133.  * @returns {number}
    134.  */
    135. this.indexOf = function (element) {
    137.   let current = head,
    138.     index = -1;
    140.   while (current) {
    141.     index++;
    142.     if (element === current.element) {
    143.       return index;
    144.     }
    145.     current = current.next;
    146.   }
    148.   return -1;
    149. };
    151. /**
    152.  * 移除给定的元素
    153.  *
    154.  * @param element
    155.  * @returns {element|null}
    156.  */
    157. this.remove = function (element) {
    158.   const index = this.indexOf(element);
    159.   return this.removeAt(index);
    160. };
    162. /**
    163.  * 链表是否为空
    164.  * @returns {boolean}
    165.  */
    166. this.isEmpty = function () {
    167.   return length === 0;
    168. };
    170. /**
    171.  * 链表大小
    172.  * @returns {number}
    173.  */
    174. this.size = function () {
    175.   return length;
    176. };
    178. /**
    179.  * 获取表头
    180.  * 方便实例外部访问和迭代链表
    181.  *
    182.  * @returns {element|null}
    183.  */
    184. this.getHead = function () {
    185.   return head;
    186. };
    187. }

    1.2 双向链表

    image.png

    1. function DoublyLinkedList() {
    3. let Node = function (element) {
    4.   this.element = element;
    5.   this.next = null;
    6.   this.prev = null;
    7. };
    9. let length = 0;
    10. let head = null;
    11. let tail = null;
    13. /**
    14.  * 从任意位置移除元素
    15.  *
    16.  * @param position
    17.  * @returns {element|null}
    18.  */
    19. this.removeAt = function (position) {
    21.   if (position >= 0 && position < length) {
    23.     let current = head,
    24.       previous,
    25.       index = 0;
    27.     if (position === 0) { // 第一项
    28.       head = current.next;
    29.       // 如果只有一项，需要更新tail
    30.       if (length === 1) {
    31.         tail = null;
    32.       } else {
    33.         head.prev = null;
    34.       }
    35.     } else if (position === length - 1) { // 最后一项
    36.       current = tail;
    37.       tail = current.prev;
    38.       tail.next = null;
    39.     } else {
    40.       while (index++ < position) {
    41.         previous = current;
    42.         current = current.next;
    43.       }
    44.       previous.next = current.next;
    45.       current.next.prev = previous;
    46.     }
    48.     length--;
    50.     return current.element;
    51.   } else {
    52.     return null;
    53.   }
    54. };
    56. /**
    57.  * 从任意位置添加节点
    58.  *
    59.  * @param {number} position
    60.  * @param element
    61.  * @returns {boolean}
    62.  */
    63. this.insert = function (position, element) {
    65.   if (position >= 0 && position <= length) {
    67.     let node = new Node(element),
    68.       current = head,
    69.       previous,
    70.       index = 0;
    72.     if (position === 0) { // 在第一个位置添加
    73.       if (!head) { // 当前链表为空
    74.         head = node;
    75.         tail = node;
    76.       } else {
    77.         node.next = current;
    78.         current.prev = node;
    79.         head = node;
    80.       }
    81.     } else if (position === length) { // 最后一项
    82.       current = tail;
    83.       current.next = node;
    84.       node.prev = current;
    85.       tail = node;
    86.     } else {
    87.       while (index++ < position) {
    88.         previous = current;
    89.         current = current.next;
    90.       }
    91.       previous.next = node;
    92.       node.next = current;
    93.       current.prev = node;
    94.       node.prev = previous;
    95.     }
    97.     length++;
    99.     return true;
    100.   } else {
    101.     return false;
    102.   }
    103. };
    105. // 其他方法和单向链表类似
    106. }

    1.3 循环链表

    循环链表 CircularLinkedList 可以只有单向引用，也可以像双向链表一样有双向引用。
    单向循环链表中：循环链表中 tail.next 指向 head。
    image.png
    双向循环链表中：tail.next 指向 head，head.prev 指向 tail。
    image.png

    2. 链表相关问题

    2.1 判断链表是否存在环形

    ```javascript // https://leetcode.com/problems/linked-list-cycle/

// 1. 暴力解法(brute force): 迭代节点, 存储或进行标记, 如果遇见已经存在的记录, 则说明存在环形

// 2. 快慢双指针(龟兔赛跑): // slow速度为1, fast为2, 若fast遇见了slow(地球是圆的), 则说明存在环形

/**

  • Definition for singly-linked list.
  • function ListNode(val) {
  • this.val = val;
  • this.next = null;
  • } */

/**

  • 判断链表是否存在环形 *
  • @param {ListNode} head

  • @return {boolean} */ const hasCycle = function (head) { let slow = head, fast = head;

    while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } } return false; }; ```

    2.2 求两个链表交集时的节点

    ```javascript // https://leetcode.com/problems/intersection-of-two-linked-lists/

// 1. 暴力解法(brute force): 使用数组或者set存储一条链表所有节点,然后迭代第二条链表进行查找是否存在(略)

// 2. 双指针 two pointers // 两个链表指针同时从各自表头移动, 速度一致, 当较短的链表(A)跑到头后, 较长的链表(B)就开始顺便重定向头部指针, // 此后B的前后两个指针之差始终等于A的总长度, // 然后等到B的后指针也跑到头后, 再同时从A和B的左侧指针开始迭代比较是否相等,找出交点.

// Time complexity : O(m+n)O(m+n). // Space complexity : O(1)O(1).

/**

  • Definition for singly-linked list.
  • function ListNode(val) {
  • this.val = val;
  • this.next = null;
  • } */

/**

  • 求两个链表交集时的节点 *
  • @param {ListNode} headA
  • @param {ListNode} headB

  • @return {ListNode|null} */ const getIntersectionNode = function (headA, headB) { let a = headA, b = headB;

    while (a !== null || b !== null) { if (a !== null) { a = a.next; } else { headB = headB.next; }

    if (b !== null) { b = b.next; } else { headA = headA.next; } }

    while (headA !== headB) { headA = headA.next; headB = headB.next; }

    return headA; }; ```