数据结构-链表

数据结构-链表

链表类型

1. 单链表

• 链表通过指针将一组零散的内存块串联在一起。每一个节点除了存储数据外还需记录上下文节点的地址指针（next）。
• 如图第一个节点，我们称之为头节点，用来记录链表的基地址。最后一个节点，我们称之为尾节点，尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址null，表示这是链表上的最后一个节点。
• 代码实现

<!--节点-->
export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }

  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}

<!--链表-->
export default class LinkedList {
  /**
   * @param {Function} [comparatorFunction]
   */
  constructor(comparatorFunction) {
    /** @var LinkedListNode */
    this.head = null;

    /** @var LinkedListNode */
    this.tail = null;

    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * @param {*} value
   * @return {LinkedList}
   */
  prepend(value) {
    // Make new node to be a head.
    const newNode = new LinkedListNode(value, this.head);
    this.head = newNode;

    // If there is no tail yet let's make new node a tail.
    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  /**
   * @param {*} value
   * @return {LinkedList}
   */
  append(value) {
    const newNode = new LinkedListNode(value);

    // If there is no head yet let's make new node a head.
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;

      return this;
    }

    // Attach new node to the end of linked list.
    this.tail.next = newNode;
    this.tail = newNode;

    return this;
  }

  /**
   * @param {*} value
   * @return {LinkedListNode}
   */
  delete(value) {
    if (!this.head) {
      return null;
    }

    let deletedNode = null;

    // If the head must be deleted then make next node that is differ
    // from the head to be a new head.
    while (this.head && this.compare.equal(this.head.value, value)) {
      deletedNode = this.head;
      this.head = this.head.next;
    }

    let currentNode = this.head;

    if (currentNode !== null) {
      // If next node must be deleted then make next node to be a next next one.
      while (currentNode.next) {
        if (this.compare.equal(currentNode.next.value, value)) {
          deletedNode = currentNode.next;
          currentNode.next = currentNode.next.next;
        } else {
          currentNode = currentNode.next;
        }
      }
    }

    // Check if tail must be deleted.
    if (this.compare.equal(this.tail.value, value)) {
      this.tail = currentNode;
    }

    return deletedNode;
  }

  /**
   * @param {Object} findParams
   * @param {*} findParams.value
   * @param {function} [findParams.callback]
   * @return {LinkedListNode}
   */
  find({ value = undefined, callback = undefined }) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    while (currentNode) {
      // If callback is specified then try to find node by callback.
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }

      // If value is specified then try to compare by value..
      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }

      currentNode = currentNode.next;
    }

    return null;
  }

  /**
   * @return {LinkedListNode}
   */
  deleteTail() {
    const deletedTail = this.tail;

    if (this.head === this.tail) {
      // There is only one node in linked list.
      this.head = null;
      this.tail = null;

      return deletedTail;
    }

    // If there are many nodes in linked list...

    // Rewind to the last node and delete "next" link for the node before the last one.
    let currentNode = this.head;
    while (currentNode.next) {
      if (!currentNode.next.next) {
        currentNode.next = null;
      } else {
        currentNode = currentNode.next;
      }
    }

    this.tail = currentNode;

    return deletedTail;
  }

  /**
   * @return {LinkedListNode}
   */
  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

    if (this.head.next) {
      this.head = this.head.next;
    } else {
      this.head = null;
      this.tail = null;
    }

    return deletedHead;
  }

  /**
   * @return {LinkedListNode[]}
   */
  toArray() {
    const nodes = [];

    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.toArray().map(node => node.toString(callback)).toString();
  }
}

<!--公共方法-->
export default class Comparator {
  /**
   * @param {function(a: *, b: *)} [compareFunction]
   */
  constructor(compareFunction) {
    this.compare = compareFunction || Comparator.defaultCompareFunction;
  }

  /**
   * @param {(string|number)} a
   * @param {(string|number)} b
   * @returns {number}
   */
  static defaultCompareFunction(a, b) {
    if (a === b) {
      return 0;
    }

    return a < b ? -1 : 1;
  }

  equal(a, b) {
    return this.compare(a, b) === 0;
  }

  lessThan(a, b) {
    return this.compare(a, b) < 0;
  }

  greaterThan(a, b) {
    return this.compare(a, b) > 0;
  }

  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b);
  }

  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b);
  }

  reverse() {
    const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}
复制代码

2. 双向链表

• 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）
• 图片示例

<!--双链表节点-->
export default class DoublyLinkedListNode {
  constructor(value, next = null, previous = null) {
    this.value = value;
    this.previous = previous;
    this.next = next;
  }

  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}

<!--双链表-->
import DoublyLinkedListNode from './DoublyLinkedListNode';

<!--公共方法参考单链表里已给出-->
import Comparator from '../../utils/comparator/Comparator';

export default class DoublyLinkedList {
  constructor(comparatorFunction) {
    // 头指针
    this.head = null;
    // 尾指针
    this.tail = null;
    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * @param {*} value
   * @return { DoublyLinkedList }
   */
  prepend(value) {
    // 生成新的newNode.next-->上一个newNode
    const newNode = new DoublyLinkedListNode(value, this.head);

    // 如果头结点存在，将head.previous指向新的newNode
    if (this.head) {
      this.head.previous = newNode;
    }
    // 移动头指针永远指向newNode
    this.head = newNode;

    if (!this.tail) {
      this.tail = newNode;
    }
    return this;
  }

  /**
   * @param {*} value
   * @return { DoublyLinkedList }
   */
  append(value) {
    const newNode = new DoublyLinkedListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }

    // 将新节点附加到链接列表的末尾
    this.tail.next = newNode;
    // 将当前尾部附加到新节点的先前引用
    newNode.previous = this.tail;

    this.tail = newNode;

    return this;
  }

  /**
   * @param {*} value
   * @return {DoublyLinkedListNode}
   */
  delete(value) {
    if (!this.head) {
      return null;
    }
    let deleteNode = null;
    let currentNode = this.head;

    while (currentNode) {
      if (this.compare.equal(currentNode.value, value)) {
        deleteNode = currentNode;
        if (deleteNode === this.head) {
          this.head = deleteNode.next;
          if (this.head) {
            this.head.previous = null;
          }

          if (deleteNode === this.tail) {
            this.tail = null;
          }
        } else if (deleteNode === this.tail) {
          const previousNode = deleteNode.previous;
          this.tail = previousNode;
          this.tail.next = null;
        } else {
          const previousNode = deleteNode.previous;
          const nextNode = deleteNode.next;
          previousNode.next = nextNode;
          nextNode.previous = previousNode;
        }
      }
      currentNode = currentNode.next;
    }

    return deleteNode;
  }

  /**
   * @param {Object} findParams
   * @param {*} findParams.value
   * @param {function} [findParams.callback]
   * @return {DoublyLinkedListNode}
   */
  find({
    value = undefined,
    callback = undefined
  }) {
    if (!this.head) {
      return null;
    }
    let currentNode = this.head;
    while (currentNode) {
      // If callback is specified then try to find node by callback.
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }

      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }
    return null;
  }

  /**
   * 删除头节点
   */
  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deleteNode = this.head;
    if (this.head.next) {
      this.head = this.head.next;
      this.head.previous = null;
    } else {
      this.head = null;
      this.tail = null;
    }

    return deleteNode;
  }

  /**
   * 删除尾节点
   */
  deleteTail() {
    if (!this.tail) {
      return null;
    }

    if (this.head === this.tail) {
      this.tail = null;
      this.head = null;
      return this.tail;
    }
    const deleteNode = this.tail;
    this.tail = this.tail.previous;
    this.tail.next = null;
    return deleteNode;
  }

  /**
   * @return {DoublyLinkedListNode[]}
   */
  toArray() {
    const nodes = [];

    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.toArray().map(node => node.toString(callback)).toString();
  }
}

复制代码

3. 循环链表

• 首节点和末节点被连接在一起
• 双链表对于给定指针指向的结点删除、插入操作比单链表有优势，双链表pre和next分别记录了当前节点的前驱、后继节点的指针，而单链表需要通过查询才能找到相应的节点
• java中LinkedHashMap容器底层实现其中就用到了双向链表这种数据结构
• 这里也有一种思想，用空间换时间，当内存空间比较充裕的情况下，如果我们更加追加代码的执行速度，我们可以选择空间复杂度较高，时间复杂度相对较低的算法。反之我们就需要用空间换时间（如单片机内存有限，对时间得要求没那么高）
• 图片示例

写好链表代码的注意事项

1. 理解指针或引用的含义

• 某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
• 如：p->next=q。这行代码是说，p 结点中的 next 指针存储了q结点的内存地址。

2. 警惕指针丢失和内存泄漏

p->next = x;  // 将 p 的 next 指针指向 x 结点；
x->next = p->next;  // 将 x 的结点的 next 指针指向 b 结点；
p->next 指针在完成第一步操作之后，已经不再指向结点b 了，而是指向结点 x。
第 2 行代码相当于将x赋值给x->next，自己指向
自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。
修正只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了
复制代码

3. 哨兵：是用来解决边界问题不参与业务逻辑

• 在任何时候链表是否为空，head指针都会指向哨兵节点。我们也把这种有哨兵节点的链表叫带头链表。

4. 注意边界条件

• 如果链表为空时，代码是否能正常工作
• 如果链表只有一个节点时，代码能否正常工作
• 如果链表只包含两个节点时，代码能否正常工作
• 代码在处理头节点和尾节点时，代码能否正常工作

5. 举例画图、辅助思考

链表与数组的对比

• 数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据（对于javascript不适用）。由于内存是连续的，支持随机访问，删除、和插入为了保存内存的连续性需要移动数据。
• 链表是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。删除、插入节点只需要相邻的节点改变指针，查找节点，需要遍历找到找到相应的节点
• 性能对比

应用

• 如何用单链表模拟实现 LRU 缓存淘汰策略算法呢
• 思路：
• 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
• 如果此数据没有在缓存链表中，又可以分为两种情况
• 1.如果此时缓存未满，则将此结点直接插入到链表的头部
• 2.如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部
• 优化：引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。

import LinkedList from '../../data-structures/linked-list/LinkedList';

export default class LRUCache {
  constructor(capacity = Number.MAX_VALUE) {
    this.capacity = capacity > 0 ? capacity : Number.MAX_VALUE;
    this.data = {};
    this.hash = {};
    this.linkedList = new LinkedList();
  }

  put(val) {
    const currentNode = this.linkedList.find({
      value: val
    });
    if (currentNode && currentNode.value === val) {
      this.linkedList.delete(val);
      this.linkedList.prepend(val);
    } else {
      if (this.linkedList.toArray().length >= this.capacity) {
        this.linkedList.prepend(val);
        this.linkedList.deleteTail();
      } else {
        this.linkedList.prepend(val);
      }
    }
  }

  displayInfo() {
    this.linkedList.toString();
  }
}
复制代码

参考链接

• 维基百科-链表
• 数据结构练手-git地址