介绍

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

实现

JavaScript

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

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

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

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

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

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

  /**
   * @public
   * @param {DoublyLinkedListNode} [prev]
   * @returns {DoublyLinkedList}
   */
  setPrev(prev) {
    if (prev && !(prev instanceof DoublyLinkedListNode)) {
      throw new Error('setPrev expects a DoublyLinkedListNode or null');
    }
    this._prev = prev || null;
    return this;
  }

  /**
   * @public
   * @returns {DoublyLinkedListNode}
   */
  getPrev() {
    return this._prev;
  }

  /**
   * @public
   * @returns {boolean}
   */
  hasPrev() {
    return this._prev instanceof DoublyLinkedListNode;
  }
}

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

  /**
   * Adds a node at the beginning of the list.
   * @public
   * @param {any} value
   * @returns {DoublyLinkedListNode}
   */
  insertFirst(value) {
    const newNode = new DoublyLinkedListNode(value);

    if (this.isEmpty()) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      this._head.setPrev(newNode);
      newNode.setNext(this._head);
      this._head = newNode;
    }
    this._count += 1;
    return newNode;
  }

  /**
   * Adds a node at the end of the list.
   * @public
   * @param {any} value
   * @returns {DoublyLinkedListNode}
   */
  insertLast(value) {
    const newNode = new DoublyLinkedListNode(value);
    if (this.isEmpty()) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      newNode.setPrev(this._tail);
      this._tail.setNext(newNode);
      this._tail = newNode;
    }
    this._count += 1;
    return newNode;
  }

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

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

    if (position === this._count) {
      return this.insertLast(value);
    }

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

    const newNode = new DoublyLinkedListNode(value);
    newNode.setNext(prev.getNext());
    newNode.setPrev(prev);
    newNode.getNext().setPrev(newNode);
    newNode.getPrev().setNext(newNode);
    this._count += 1;
    return newNode;
  }

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

    const removedNode = this._head;
    if (this._head.hasNext()) {
      this._head = this._head.getNext();
      this._head.setPrev(null);
    } else {
      this._head = null;
      this._tail = null;
    }
    this._count -= 1;
    return removedNode.setNext(null);
  }

  /**
   * Removes the tail node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  removeLast() {
    if (this.isEmpty()) return null;

    const removedNode = this._tail;
    if (this._tail.hasPrev()) {
      this._tail = this._tail.getPrev();
      this._tail.setNext(null);
    } else {
      this._head = null;
      this._tail = null;
    }
    this._count -= 1;
    return removedNode.setPrev(null);
  }

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

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

    if (position === this._count - 1) {
      return this.removeLast();
    }

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

  /**
   * Removes a node from the list by its reference.
   * @public
   * @param {DoublyLinkedListNode} node
   * @returns {DoublyLinkedListNode}
   */
  remove(node) {
    if (node && !(node instanceof DoublyLinkedListNode)) {
      throw new Error('remove: expects a DoublyLinkedListNode node');
    }

    if (!node) {
      return null;
    }

    if (!node.hasPrev()) {
      return this.removeFirst();
    }

    if (!node.hasNext()) {
      return this.removeLast();
    }

    node.getPrev().setNext(node.getNext());
    node.getNext().setPrev(node.getPrev());
    this._count -= 1;
    return node.setPrev(null).setNext(null);
  }

  /**
   * 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 current = this._head;
    while (current instanceof DoublyLinkedListNode) {
      if (cb(current, position)) {
        const next = current.getNext();
        this.remove(current);
        removedCount += 1;
        current = next;
      } else {
        current = current.getNext();
      }
      position += 1;
    }
    return removedCount;
  }

  /**
   * 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 DoublyLinkedListNode) {
      cb(current, position);
      position += 1;
      current = current.getNext();
    }
  }

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

    let current = this._tail;
    let position = this._count - 1;
    while (current instanceof DoublyLinkedListNode) {
      cb(current, position);
      position -= 1;
      current = current.getPrev();
    }
  }

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

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

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

  /**
   * Finds a node in the list using a callback in reverse order
   * @public
   * @param {function} cb
   * @param {DoublyLinkedListNode} [startingNode]
   * @returns {DoublyLinkedListNode}
   */
  findReverse(cb, startingNode = this._tail) {
    if (typeof cb !== 'function') {
      throw new Error('.findReverse(cb) expects a callback');
    }

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

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

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

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

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

  /**
   * Returns the tail node.
   * @public
   * @returns {DoublyLinkedListNode}
   */
  tail() {
    return this._tail;
  }

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

  /**
   * Converts the doubly 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._tail = null;
    this._count = 0;
  }

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

    const doublyLinkedList = new DoublyLinkedList();
    values.forEach((value) => {
      doublyLinkedList.insertLast(value);
    });
    return doublyLinkedList;
  }
}

或者：

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

class DoubleLinkedList {
  constructor () {
    this.length = 0
    this.head = null
    this.tail = null
  }

  // Add new element
  append (element) {
    const node = new Node(element)

    if (!this.head) {
      this.head = node
      this.tail = node
    } else {
      node.prev = this.tail
      this.tail.next = node
      this.tail = node
    }

    this.length++
  }

  // Add element
  insert (position, element) {
    // Check of out-of-bound values
    if (position >= 0 && position <= this.length) {
      const node = new Node(element)
      let current = this.head
      let previous = 0
      let index = 0

      if (position === 0) {
        if (!this.head) {
          this.head = node
          this.tail = node
        } else {
          node.next = current
          current.prev = node
          this.head = node
        }
      } else if (position === this.length) {
        current = this.tail
        current.next = node
        node.prev = current
        this.tail = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        node.next = current
        previous.next = node

        // New
        current.prev = node
        node.prev = previous
      }

      this.length++
      return true
    } else {
      return false
    }
  }

  // Remove element at any position
  removeAt (position) {
    // look for out-of-bounds value
    if (position > -1 && position < this.length) {
      let current = this.head
      let previous = 0
      let index = 0

      // Removing first item
      if (position === 0) {
        this.head = current.next

        // if there is only one item, update this.tail //NEW
        if (this.length === 1) {
          this.tail = null
        } else {
          this.head.prev = null
        }
      } else if (position === this.length - 1) {
        current = this.tail
        this.tail = current.prev
        this.tail.next = null
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        // link previous with current's next - skip it
        previous.next = current.next
        current.next.prev = previous
      }

      this.length--
      return current.element
    } else {
      return null
    }
  }

  // Get the indexOf item
  indexOf (elm) {
    let current = this.head
    let index = -1

    // If element found then return its position
    while (current) {
      if (elm === current.element) {
        return ++index
      }

      index++
      current = current.next
    }

    // Else return -1
    return -1
  }

  // Find the item in the list
  isPresent (elm) {
    return this.indexOf(elm) !== -1
  }

  // Delete an item from the list
  delete (elm) {
    return this.removeAt(this.indexOf(elm))
  }

  // Delete first item from the list
  deleteHead () {
    this.removeAt(0)
  }

  // Delete last item from the list
  deleteTail () {
    this.removeAt(this.length - 1)
  }

  // Print item of the string
  toString () {
    let current = this.head
    let string = ''

    while (current) {
      string += current.element + (current.next ? '\n' : '')
      current = current.next
    }

    return string
  }

  // Convert list to array
  toArray () {
    const arr = []
    let current = this.head

    while (current) {
      arr.push(current.element)
      current = current.next
    }

    return arr
  }

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

  // Get the size of the list
  size () {
    return this.length
  }

  // Get the this.head
  getHead () {
    return this.head
  }

  // Get the this.tail
  getTail () {
    return this.tail
  }

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

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

  // Method to log the LinkedList, for debugging
  // it' a circular structure, so can't use stringify to debug the whole structure
  log () {
    let currentNode = this.getHead()
    while (currentNode) {
      console.log(currentNode.element)
      currentNode = currentNode.next
    }
  }
}

参考

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