[数据结构与算法]4__链表__

链表

链表数据结构(普通链表)

// 单向链表
function defaultEquals(a, b) {
  return a === b;
}

class Node {
  constructor(element, next) {
    // 要加入链表元素的值
    this.element = element;
    // 指向链表中下一个元素的指针
    this.next = next;
  }
}

class LinkedList {
  // 类实例化时传入的参数会用作构造函数的参数
  constructor(equalsFn = defaultEquals) {
    // 链表的元素数量
    this.count = 0;
    // 将第一个元素的引用保存下来
    this.head = undefined;
    // 比较链表中的元素是否相等
    this.equalsFn = equalsFn;
  }
  // 向链表尾部添加一个新元素
  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      //  获得最后一项
      while (current.next != null) {
        // 相当于node.next
        current = current.next;
      }
      // 将其next赋为新元素，建立链接
      //相当于上一个对象的next属性指向新的node
      current.next = node;
    }
    this.count++;
  }
  // 从链表中移除元素(两种方法)

  // 1:从特定位置移除一个元素(removeAt)
  removeAt(index) {
    // 检查越界值 元素的index(位置) 是否有效
    if (index >= 0 && index < this.count) {
      // current指向第一个node
      let current = this.head;
      if (index === 0) {
        // 移除第一项 (从链表中移除第一个元素)
        this.head = current.next;
      } else {
        // 移除链表的最后一个或者中间某个元素
        // previous变量是对要移除节点的前一个节点的引用
        let previous;
        for (let i = 0; i < index; i++) {
          previous = current;
          // current变量总是为对所循环列表的当前元素的引用
          current = current.next;
        }
        // 将previous与current的下一项链接起来：跳过current，从而移除它
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
  // 重构removeAt函数
  removeAt_reconsitution(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
  // 循环迭代链表直到目标位置(索引)的函数
  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }
  // 2:根据元素的值移除元素,从链表中移除一个元素
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  // 在任意位置插入元素,向链表的特定位置插入一个新元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      // {1}
      const node = new Node(element);
      if (index === 0) {
        // 在第一个位置添加
        const current = this.head;
        // 当前要插入的node指向链表的第一个元素,现在,老子第一了
        node.next = current;
        // this.head跟过来
        this.head = node;
      } else {
        // 在链表中间或尾部添加一个元素
        // previous表示需要添加新节点位置的前一个位置
        const previous = this.getElementAt(index - 1);
        // previous.next是新插入node的后一位元素
        const current = previous.next;
        node.next = current;
        // node的前一位元素现在指向node
        previous.next = node;
      }
      // 更新链表的长度
      this.count++;
      return true;
    }
    return false;
  }
  // 返回元素在链表中的索引。如果链表中没有该元素则返回-1
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count && current != null; i++) {
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }
  // 返回链表包含的元素个数，与数组的length属性类似
  size() {
    return this.count;
  }
  // 链表是否为空,如果列表中没有元素，isEmpty方法就返回true，否则返回false
  isEmpty() {
    return this.size() === 0;
  }
  // 获取链表第一个元素
  getHead() {
    return this.head;
  }
  // 清空链表
  clear() {
    this.head = undefined;
    this.count = 0;
  }
  // 返回表示整个链表的字符串,toString方法会把LinkedList对象转换成一个字符串
  toString() {
    if (this.head == null) {
      return "";
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

双向链表

class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);
    this.prev = prev; // 新增的
  }
}
class DoublyLinkedList extends LinkedList {
  // {4}
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    // 链表最后一个元素的引用
    this.tail = undefined; // 新增的
  }
  // 向表尾插入元素
  push(element) {
    const node = new DoublyNode(element);
    if (this.head == null) {
      this.head = node;
      this.tail = node; // NEW
    } else {
      // attach to the tail node // NEW
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }
  // 在任意位置插入新元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;
      // 向链表的头插入元素
      if (index === 0) {
        // 链表为空
        if (this.head == null) {
          // 新增的
          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;
        // 现在成倒数第二了,新加的node成倒数第一了(最后的一个元素)
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        // 其他任意位置插入元素
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        // 以下4部更换4个指向,这样,previous和current中间就是新加的node了
        node.next = current;
        previous.next = node;
        current.prev = node; // 新增的
        node.prev = previous; // 新增的
      }
      this.count++;
      return true;
    }
    return false;
  }
  // 从任意位置移除元素
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        //移除首位
        this.head = current.next;
        // 如果只有一项，更新tail 新增的
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
          current.next = undefined;
        }
      } else if (index === this.count - 1) {
        // 移除末位 新增的
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
        current.prev = undefined;
      } else {
        current = this.getElementAt(index);
        // 将previous与current的下一项链接起来——跳过current
        const previous = current.prev;
        previous.next = current.next;
        current.next.prev = previous; // 新增的
        current.next = undefined;
        current.prev = undefined;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
  // 返回元素在链表中的索引
  indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current != null) {
      if (this.equalsFn(element, current.element)) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }
  // 获取链表第一个元素
  getHead() {
    return this.head;
  }
  // 获取链表最后一个元素
  getTail() {
    return this.tail;
  }
  // 清空链表
  clear() {
    super.clear();
    this.tail = undefined;
  }
  // 返回表示整个链表的字符串
  toString() {
    if (this.head == null) {
      return "";
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    while (current != null) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
  // 倒序返回整个链表的字符串
  inverseToString() {
    if (this.tail == null) {
      return "";
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

单向循环链表

class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
  }
  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.getElementAt(this.size() - 1);
      current.next = node;
    }
    // set node.next to head - to have circular list
    node.next = this.head;
    this.count++;
  }
  // 在任意位置插入新元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        // 向表头插入
        if (this.head == null) {
          // if no node  in list
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          // 获取最后一个元素
          current = this.getElementAt(this.size());
          // update last element
          this.head = node;
          current.next = this.head;
        }
      } else {
        //  其他位置插入
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }
  // 从任意位置移除元素
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      // 移除表头的
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          const removed = this.head;
          current = this.getElementAt(this.size() - 1);
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
        //  不需要修改循环链表最后一个元素
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
}

有序链表(保持元素有序的链表结构)

// 什么？为什么要声明这么一个鸡肋的类(Compare)？我听说是为了保证代码优雅
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
};

function defaultCompare(a, b) {
  if (a === b) {
    return 0;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn);
    this.equalsFn = equalsFn;
    this.compareFn = compareFn;
  }
  push(element) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
  }
  insert(element, index = 0) {
    if (this.isEmpty()) {
      return super.insert(element, index === 0 ? index : 0);
    }
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(element, pos);
  }
  getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(element, current.element);
      if (comp === Compare.LESS_THAN) {
        return i;
      }
      current = current.next;
    }
    return i;
  }
}

创建栈数据结构

我们还可以使用 LinkedList 类及其变种作为内部的数据结构来创建其他数据结构，例如栈、队列和双向队列

class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList();
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.removeAt(this.size() - 1);
    return result;
  }
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.getElementAt(this.size() - 1).element;
  }
  isEmpty() {
    return this.items.isEmpty();
  }
  size() {
    return this.items.size();
  }
  clear() {
    this.items.clear();
  }
  toString() {
    return this.items.toString();
  }
}