介绍

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针 (Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到$O(1)$ 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要$O(n)$ 的时间，而顺序表相应的时间复杂度分别是$O(logn)$ 和$O(1)$。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个 / 或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

链表可以在多种编程语言中实现。像 Lisp 和 Scheme 这样的语言的内建数据类型中就包含了链表的访问和操作。程序语言或面向对象语言，如 C/C++ 和 Java 依靠易变工具来生成链表。

实现

JavaScript

class LinkedListNode {
  /**
   * Creates a linked list node.
   * @param {any} value
   * @param {LinkedListNode} [next]
   */
  constructor(value, next) {
    this._value = value;
    this.setNext(next);
  }

  /**
   * @public
   * @param {any} value
   * @returns {LinkedListNode}
   */
  setValue(value) {
    this._value = value;
    return this;
  }

  /**
   * @public
   * @returns {any}
   */
  getValue() {
    return this._value;
  }

  /**
   * @public
   * @param {LinkedListNode} [next]
   * @returns {LinkedListNode}
   */
  setNext(next) {
    if (next && !(next instanceof LinkedListNode)) {
      throw new Error('seNext expects a LinkedListNode or null');
    }
    this._next = next || null;
    return this;
  }

  /**
   * @public
   * @returns {LinkedListNode}
   */
  getNext() {
    return this._next;
  }

  /**
   * @public
   * @returns {boolean}
   */
  hasNext() {
    return this._next instanceof LinkedListNode;
  }
}

class LinkedList {
  constructor() {
    this._head = null;
    this._count = 0;
  }

  /**
   * Adds a node at the beginning of the list.
   * @public
   * @param {any} value
   * @returns {LinkedListNode}
   */
  insertFirst(value) {
    this._head = new LinkedListNode(value, this._head);
    this._count += 1;
    return this._head;
  }

  /**
   * Adds a node at the end of the list.
   * @public
   * @param {any} value
   * @param {LinkedListNode} [startingNode]
   * @returns {LinkedListNode}
   */
  insertLast(value, startingNode) {
    if (this.isEmpty()) {
      return this.insertFirst(value);
    }

    if (startingNode && !(startingNode instanceof LinkedListNode)) {
      throw new Error('insertLast expects a LinkedListNode starting node');
    }

    let current = startingNode || this._head;
    while (current.hasNext()) {
      current = current.getNext();
    }

    current.setNext(new LinkedListNode(value, null));
    this._count += 1;
    return current.getNext();
  }

  /**
   * Adds a node at a specific position.
   * @public
   * @param {number} position
   * @param {any} value
   * @returns {LinkedListNode}
   */
  insertAt(position, value) {
    if (
      Number.isNaN(+position)
      || position < 0 || position > this._count
    ) {
      throw new Error('insertAt expects a position num <= linked list size.');
    }

    // head node is at position 0
    if (position === 0) {
      return this.insertFirst(value);
    }

    let currentPosition = 1;
    let prev = this._head;
    while (currentPosition < position) {
      currentPosition += 1;
      prev = prev.getNext();
    }

    // add it at a position after the head, between prev & prev.getNext()
    prev.setNext(new LinkedListNode(value, prev.getNext()));
    this._count += 1;
    return prev.getNext();
  }

  /**
   * Removes the head node.
   * @public
   * @returns {LinkedListNode}
   */
  removeFirst() {
    if (this.isEmpty()) return null;

    const removed = this._head;
    this._head = this._head.getNext();
    this._count -= 1;
    return removed.setNext(null);
  }

  /**
   * Removes the last node in the list.
   * @public
   * @returns {LinkedListNode}
   */
  removeLast() {
    if (this.isEmpty()) return null;

    let prev = null;
    let current = this._head;
    while (current.hasNext()) {
      prev = current;
      current = current.getNext();
    }

    // linked list has 1 node
    if (prev === null) {
      return this.removeFirst();
    }

    prev.setNext(null);
    this._count -= 1;
    return current;
  }

  /**
   * Removes all nodes based on a callback.
   * @public
   * @param {function} cb
   * @returns {number} number of removed nodes
   */
  removeEach(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.removeEach(cb) expects a callback');
    }

    let removedCount = 0;
    let position = 0;
    let prev = null;
    let current = this._head;
    while (current instanceof LinkedListNode) {
      if (cb(current, position)) {
        if (prev === null) {
          this.removeFirst();
        } else {
          prev.setNext(prev.getNext().getNext());
        }
        this._count -= 1;
        removedCount += 1;
      } else {
        prev = current;
      }
      position += 1;
      current = current.getNext();
    }
    return removedCount;
  }

  /**
   * Removes a node at a specific position.
   * @public
   * @param {number} position
   * @returns {LinkedListNode}
   */
  removeAt(position) {
    if (
      Number.isNaN(+position)
      || position < 0
      || position >= this._count
    ) {
      return null;
    }

    if (position === 0) {
      return this.removeFirst();
    }

    let counter = 1;
    let prev = this._head;
    while (counter < position) {
      counter += 1;
      prev = prev.getNext();
    }
    const removed = prev.getNext();
    prev.setNext(prev.getNext().getNext());
    this._count -= 1;
    return removed.setNext(null);
  }

  /**
   * Traverses the list from beginning to end.
   * @public
   * @param {function} cb
   */
  forEach(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.forEach(cb) expects a callback');
    }

    let current = this._head;
    let position = 0;
    while (current instanceof LinkedListNode) {
      cb(current, position);
      position += 1;
      current = current.getNext();
    }
  }

  /**
   * Finds one node in the list based on a callback.
   * @public
   * @param {function} cb
   * @param {DoublyLinkedListNode} [startingNode]
   * @returns {LinkedListNode}
   */
  find(cb, startingNode = this._head) {
    if (typeof cb !== 'function') {
      throw new Error('.find(cb) expects a callback');
    }

    if (startingNode && !(startingNode instanceof LinkedListNode)) {
      throw new Error('.find(cb) expects to start from a LinkedListNode');
    }

    let current = startingNode;
    while (current instanceof LinkedListNode) {
      if (cb(current)) {
        return current;
      }
      current = current.getNext();
    }
    return null;
  }

  /**
   * Filters the list based on a callback.
   * @public
   * @param {function} cb - callback should return true for required nodes.
   * @returns {LinkedList}
   */
  filter(cb) {
    if (typeof cb !== 'function') {
      throw new Error('.filter(cb) expects a callback');
    }

    let last = null;
    const result = new LinkedList();
    this.forEach((node, position) => {
      if (!cb(node, position)) return;
      last = result.insertLast(node.getValue(), last);
    });
    return result;
  }

  /**
   * Returns the head node.
   * @public
   * @returns {LinkedListNode}
   */
  head() {
    return this._head;
  }

  /**
   * Returns the nodes count in the list.
   * @public
   * @returns {number}
   */
  count() {
    return this._count;
  }

  /**
   * Converts the linked list into an array.
   * @public
   * @returns {array}
   */
  toArray() {
    const result = [];
    this.forEach((node) => result.push(node.getValue()));
    return result;
  }

  /**
   * Checks if the list is empty.
   * @public
   * @returns {boolean}
   */
  isEmpty() {
    return this._head === null;
  }

  /**
   * Clears the list
   * @public
   */
  clear() {
    this._head = null;
    this._count = 0;
  }

  /**
   * Creates a linked list from an array
   * @public
   * @static
   * @param {array} values
   * @return {LinkedList}
   */
  static fromArray(values) {
    if (!Array.isArray(values)) {
      throw new Error('cannot create LinkedList from none-array values');
    }

    const linkedList = new LinkedList();
    let lastInserted = null;
    values.forEach((value) => {
      lastInserted = linkedList.insertLast(value, lastInserted);
    });
    return linkedList;
  }
}

或者：

/* SinglyLinkedList!!
* A linked list is similar to an array, it holds a list of values.
* However, links in a linked list do not have indexes. With
* a linked list you do not need to predetermine its size as
* it grows and shrinks as it is edited. This is an example of
* a singly linked list.
*/

// Methods - size, head, addLast, addFirst, addAt, removeFirst, removeLast, remove, removeAt, indexOf, isEmpty,  elementAt, get, clean

class Node {
  constructor (data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor () {
    this.headNode = null
    this.length = 0
  }

  // initiates the currentNode and currentIndex and return as an object
  initiateNodeAndIndex () {
    return { currentNode: this.headNode, currentIndex: 0 }
  }

  // Returns length
  size () {
    return this.length
  }

  // Returns the head
  head () {
    return this.headNode?.data || null
  }

  // Return if the list is empty
  isEmpty () {
    return this.length === 0
  }

  // add a node at last it to linklist
  addLast (element) {
    // Check if its the first element
    if (this.headNode === null) {
      return this.addFirst(element)
    }
    let { currentNode } = this.initiateNodeAndIndex()

    // Loop till there is a node present in the list
    while (currentNode.next) {
      currentNode = currentNode.next
    }

    const node = new Node(element)
    // Adding node at the end of the list and increase the length
    currentNode.next = node
    this.length++
    return this.size()
  }

  // add a node at first it to linklist
  addFirst (element) {
    const node = new Node(element)
    node.next = this.headNode
    this.headNode = node
    this.length++
    return this.size()
  }

  // remove the first from the linklist
  removeFirst () {
    const removedNode = this.headNode
    if (this.length > 0) {
      this.headNode = this.headNode.next
      this.length--
    }
    console.log(removedNode.data)
    return removedNode?.data
  }

  // remove the last from the linklist
  removeLast () {
    if (this.isEmpty()) return null
    if (this.length === 1) {
      return this.removeFirst()
    }
    let { currentIndex, currentNode } = this.initiateNodeAndIndex()
    while (currentIndex !== this.length - 2) {
      currentIndex++
      currentNode = currentNode.next
    }
    const removedNode = currentNode.next
    currentNode.next = null
    this.length--
    return removedNode.data
  }

  // Removes the node with the value as param
  remove (element) {
    if (this.isEmpty()) return null
    let { currentNode } = this.initiateNodeAndIndex()
    let removedNode = null
    // Check if the head node is the element to remove
    if (currentNode.data === element) {
      return this.removeFirst()
    }
    // Check which node is the node to remove
    while (currentNode?.next) {
      if (currentNode.next.data === element) {
        removedNode = currentNode.next
        currentNode.next = currentNode.next.next
        this.length--
        break
      }
      currentNode = currentNode.next
    }
    return removedNode?.data || null
  }

  // Returns the index of the element passed as param otherwise -1
  indexOf (element) {
    let { currentIndex, currentNode } = this.initiateNodeAndIndex()

    while (currentNode) {
      // Checking if the node is the element we are searching for
      if (currentNode.data === element) {
        return currentIndex
      }
      currentNode = currentNode.next
      currentIndex++
    }
    return -1
  }

  // Returns the element at an index
  elementAt (index) {
    if (index >= this.length || index < 0) {
      throw new RangeError('Out of Range index')
    }
    let { currentIndex, currentNode } = this.initiateNodeAndIndex()
    while (currentIndex < index) {
      currentIndex++
      currentNode = currentNode.next
    }
    return currentNode.data
  }

  // Adds the element at specified index
  addAt (index, element) {
    // Check if index is out of bounds of list
    if (index > this.length || index < 0) {
      throw new RangeError('Out of Range index')
    }
    if (index === 0) return this.addFirst(element)
    if (index === this.length) return this.addLast(element)
    let { currentIndex, currentNode } = this.initiateNodeAndIndex()
    const node = new Node(element)

    while (currentIndex !== index - 1) {
      currentIndex++
      currentNode = currentNode.next
    }

    // Adding the node at specified index
    const tempNode = currentNode.next
    currentNode.next = node
    node.next = tempNode
    // Incrementing the length
    this.length++
    return this.size()
  }

  // Removes the node at specified index
  removeAt (index) {
    // Check if index is present in list
    if (index < 0 || index >= this.length) {
      throw new RangeError('Out of Range index')
    }
    if (index === 0) return this.removeFirst()
    if (index === this.length) return this.removeLast()

    let { currentIndex, currentNode } = this.initiateNodeAndIndex()
    while (currentIndex !== index - 1) {
      currentIndex++
      currentNode = currentNode.next
    }
    const removedNode = currentNode.next
    currentNode.next = currentNode.next.next
    // Decrementing the length
    this.length--
    return removedNode.data
  }

  // make the linkedList Empty
  clean () {
    this.headNode = null
    this.length = 0
  }

  // Method to get the LinkedList
  get () {
    const list = []
    let { currentNode } = this.initiateNodeAndIndex()
    while (currentNode) {
      list.push(currentNode.data)
      currentNode = currentNode.next
    }

    return list
  }

  // Method to iterate over the LinkedList
  iterator () {
    let { currentNode } = this.initiateNodeAndIndex()
    if (currentNode === null) return -1

    const iterate = function * () {
      while (currentNode) {
        yield currentNode.data
        currentNode = currentNode.next
      }
    }
    return iterate()
  }

  // Method to log the LinkedList
  log () {
    console.log(JSON.stringify(this.headNode, null, 2))
  }
}

AddTwoNumbers:

/**
 * A LinkedList based solution for Add Two Numbers
 *
 */
import { Node } from './SinglyLinkedList.js'

/*
Problem Statement:
Given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order and each of their nodes contain a single digit.
Add the two numbers and return it as a linked list.

Link for the Problem: https://leetcode.com/problems/add-two-numbers/
*/

class AddTwoNumbers {
  constructor () {
    this.dummyNode = new Node(0)
  }

  solution (firstList, secondList) {
    let firstRunner = firstList
    let secondRunner = secondList
    let tail = this.dummyNode
    let carry = 0
    while (firstRunner != null || secondRunner != null) {
      const firstNumber = firstRunner ? firstRunner.data : 0
      const secondNumber = secondRunner ? secondRunner.data : 0
      const sum = carry + firstNumber + secondNumber
      carry = parseInt(sum / 10)
      tail.next = new Node(sum % 10)
      tail = tail.next
      if (firstRunner) {
        firstRunner = firstRunner.next
      }
      if (secondRunner) {
        secondRunner = secondRunner.next
      }
    }
    if (carry > 0) {
      tail.next = new Node(carry % 10)
    }

    return this.dummyNode.next
  }

  solutionToArray () {
    const list = []
    let currentNode = this.dummyNode.next
    while (currentNode) {
      list.push(currentNode.data)
      currentNode = currentNode.next
    }

    return list
  }
}

应用

循环检测 (CycleDetection)

/**
 * A LinkedList based solution for Detect a Cycle in a list
 * https://en.wikipedia.org/wiki/Cycle_detection
 */

function main () {
  /*
  Problem Statement:
  Given head, the head of a linked list, determine if the linked list has a cycle in it.

  Note:
  * While Solving the problem in given link below, don't use main() function.
  * Just use only the code inside main() function.
  * The purpose of using main() function here is to avoid global variables.

  Link for the Problem: https://leetcode.com/problems/linked-list-cycle/
  */
  const head = '' // Reference to head is given in the problem. So please ignore this line
  let fast = head
  let slow = head

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

RotateListRight

/**
 * A LinkedList based solution for Rotating a List to the right by k places
 */

function main () {
  /*
  Problem Statement:
  Given a linked list, rotate the list to the right by k places, where k is non-negative.

  Note:
  * While Solving the problem in given link below, don't use main() function.
  * Just use only the code inside main() function.
  * The purpose of using main() function here is to avoid global variables.

  Link for the Problem: https://leetcode.com/problems/rotate-list/
  */
  // Reference to both head and k is given in the problem. So please ignore below two lines
  let head = ''
  let k = ''
  let i = 0
  let current = head
  while (current) {
    i++
    current = current.next
  }
  k %= i
  current = head
  let prev = null
  while (k--) {
    if (!current || !current.next) {
      return current
    } else {
      while (current.next) {
        prev = current
        current = current.next
      }
      prev.next = current.next
      current.next = head
      head = current
    }
  }
  return head
}

参考

• 链表 - 维基百科，自由的百科全书 (opens new window)
• 单向链表 - 维基百科，自由的百科全书 (opens new window)
• Linked list - Wikipedia (opens new window)