第三章、链表

链表是有序元素集合，但链表在内存中并不是连续放置的，每个元素有一个储存元素本身的节点和一个指向下一个元素的引用组成。

创建链表

// 链表元素
class Node {
  constructor(item) {
    this.item = item;
    this.next = undefined;
  }
}

// 链表
class LinkedList {
  constructor() {
    this.count = 0;
    this.head = undefined;
  }
  // 向链表末尾添加元素
  push(item) {
    const node = new Node(item);
    if (!this.head) {
      this.head = node;
    } else {
      // 从链表的第一个元素开始查找
      let current = this.head;
      // 当某一项不存在下一项时，即为最后一项
      while (current.next) {
        current = current.next;
      }
      // 将最后一项的下一项只向新增加的项，新增加的项就成为最后一项
      current.next = node;
    }
    this.count++;
  }
  // 根据索引查找链表中的某个元素
  getItemAt(index) {
    // 不存在的索引直接返回undefined
    if (index < 0 || index >= this.count) {
      return undefined;
    }
    // 从链表头部开始查找
    let node = this.head;
    for (let i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }
  // 根据值查找某个元素的索引(只查找第一个符合的元素)
  getItemOf(item) {
    // 从链表头部开始查找
    let current = this.head;
    for (let i = 0; i < this.count; i++) {
      // 根据全等判断是否为要查找的元素
      if (item === current.item) {
        return i;
      }
      current = current.next;
    }
    // 没找到就返回-1
    return -1;
  }
  // 根据索引移除某个元素
  removeItemAt(index) {
    // 不存在的索引直接返回undefined
    if (index < 0 || index >= this.count) {
      return undefined;
    }
    // 从第一项开始查找
    let current = this.head;
    // 要移除的是第一项
    if (index === 0) {
      // 直接将链表头部指向第二项
      this.head = this.head.next;
    } else {
      // 要移除的不是第一项，找到指定位置的项，将要移除的项的前一项和后一项关联起来
      const prevItem = this.getItemAt(index - 1);
      current = prevItem.next;
      prevItem.next = current.next;
    }
    this.count--;
    return current.item;
  }
  // 根据值移除某个元素(只移除第一个符合的元素)
  removeItemOf(item) {
    // 直接找到元素的索引然后根据索引移除
    const index = this.getItemOf(item);
    return this.removeItemAt(index);
  }
  // 在任意位置插入元素
  insertItem(item, index) {
    // 不存在的索引直接报错
    if (index < 0 || index >= this.count) {
      return false;
    }
    const node = new Node(item);
    // 插入到链表头部时
    if (index === 0) {
      const current = this.head;
      node.next = current;
      this.head = node;
    } else {
      const prevItem = this.getItemAt(index - 1);
      const current = prevItem.next;
      prevItem.next = node;
      node.next = current;
    }
    this.count++;
  }
  // 返回链表大小
  size() {
    return this.count;
  }
  // 判断链表是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回链表头部
  getHead() {
    return this.head;
  }
  // 返回链表的字符串表示
  toString() {
    // 链表中没有元素时直接返回空字符串
    if (!this.head) {
      return "";
    }
    let objString = `${this.head.item}`;
    let current = this.head.next;
    for (let i = 1; i < this.size(); i++) {
      objString = `${objString},${current.item}`;
      current = current.next;
    }
    return objString;
  }
}

双向链表

双向链表拥有指向前一个元素的引用和指向下一个元素的引用。

// 双线链表元素，继承自链表元素，新增prev属性
class DoublyNode extends Node {
  constructor(item, next, prev) {
    super(item, next);
    this.prev = prev;
  }
}
// 双向链表，继承自链表，新增tail属性
class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    // 新增表示链表尾部的元素
    this.tail = undefined;
  }
  // 向链表任意位置插入元素
  insertItem(item, index) {
    // 不存在的索引直接报错
    if (index < 0 || index > this.count) {
      return false;
    }
    const node = new DoublyNode(item);
    let current = this.head;
    // 插入到链表头部时
    if (index === 0) {
      // 链表为空时
      if (!this.head) {
        this.head = node;
        this.tail = node;
      } else {
        node.next = this.head;
        current.prev = node;
        this.head = node;
      }
    } else if (index === this.count) {
      // 插入到链表末尾
      current = this.tail;
      current.next = node;
      node.prev = current;
      this.tail = node;
    } else {
      // 插入到链表中间某个位置
      const prevItem = this.getItemAt(index - 1);
      current = prevItem.next;
      node.next = current;
      node.prev = prevItem;
      current.prev = node;
      prevItem.next = node;
    }
    this.count++;
  }
  // 从链表任意位置移除元素
  removeAt(index) {
    if (index < 0 || index >= this.count) {
      return undefined;
    }
    // 从头部开始查找
    let current = this.head;
    // 移除头部元素
    if (index === 0) {
      this.head = current.next;
      // 只有一个元素时
      if (this.count === 1) {
        this.tail = undefined;
      } else {
        this.head.prev = undefined;
      }
    } else if (index === this.count - 1) {
      // 移除最后一项
      current = this.tail;
      this.tail = current.prev;
      this.tail.next = undefined;
    } else {
      current = this.getItemAt(index);
      const prevItem = current.prev;
      prevItem.next = current.next;
      current.next.prev = prevItem;
    }
    this.count--;
    return current.item;
  }
}

循环链表

循环链表可以是普通链表，也可以是双向链表。
普通循环链表将尾部元素的下一项指向头部元素。
双向循环链表将头部元素的前一个元素指向尾部元素，将尾部元素的下一个元素指向头部元素

class CircularLinkedList extends LinkedList {
  constructor() {
    super();
  }
  // 在任意位置插入元素
  insertItem(item, index) {
    // 不存在的索引直接报错
    if (index < 0 || index > this.count) {
      return false;
    }
    const node = new Node(item);
    let current = this.head;
    // 插入到链表头部时
    if (index === 0) {
      if (!this.head) {
        this.head = node;
        node.next = this.head;
      } else {
        node.next = current;
        current = this.getItemAt(this.size() - 1);
        this.head = node;
        current.next = this.head;
      }
    } else {
      const prevItem = this.getItemAt(index - 1);
      current = prevItem.next;
      prevItem.next = node;
      node.next = current;
    }
    this.count++;
  }
  // 根据索引移除某个元素
  removeItemAt(index) {
    // 不存在的索引直接返回undefined
    if (index < 0 || index >= this.count) {
      return undefined;
    }
    // 从第一项开始查找
    let current = this.head;
    // 要移除的是第一项
    if (index === 0) {
      if (this.size() === 1) {
        this.head = undefined;
      } else {
        const removed = this.head;
        current = this.getItemAt(this.size() - 1);
        this.head = this.head.next;
        current.next = this.head;
        current = removed;
      }
    } else {
      // 要移除的不是第一项，找到指定位置的项，将要移除的项的前一项和后一项关联起来
      const prevItem = this.getItemAt(index - 1);
      current = prevItem.next;
      prevItem.next = current.next;
    }
    this.count--;
    return current.item;
  }
}