链表

1. 链表数据结构

概念：链表存储有序数据集合，每个元素由一个存储元素本身数据的节点和指向下一个元素的引用（指针）组成。

数组：访问数据效率高，添加删除元素需要移动元素，开销大。

链表：添加删除元素时不需要移动元素，效率更高，但访问数据时要从第一个节点开始迭代，开销更大。

1.1 创建链表

为了表示链表中的元素，需要一个助手类 Node：

class Node {
  constructor(element) {
    // 保持当前元素数据
    this.element = element;
    // 指向下一元素
    this.next = undefined;
  }
}

链表 LinkedList 类，包含一些方法：

• push(element)：向链表尾部添加一个元素。
• insert(element, position)：向链表特定位置插入新元素。
• getElementAt(index)：返回链表中特定位置的元素。如果不存在则返回 undefined。
• remove(element)：从链表中移除一个元素。
• indexOf(element)：返回元素在链表中的索引。不存在则返回 -1。
• removeAt(position)：从链表的特定位置移除一个元素。
• isEmpty()：如果链表不包含任何元素则返回 true，否则返回 false。
• size()：返回链表中元素个数。
• toString()：返回表示整个链表的字符串。

export default class LinkedList {
  constructor() {
    this.count = 0;
    // 头指针
    this.head = undefined;
  }

  // 向尾部添加元素
  push(element) {
    const node = new Node(element);
    let current;
    if(this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      while(current.next != null) {
        current = current.next;
      }
      // 将 next 赋为新元素
      current.next = node;
    }
    this.count++;
  }

  // 从链表中移除元素
  removeAt(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 current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
      return current;
    } 
    return undefined;
  }

  // 在任意位置插入元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node;
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        const current = previous.next;
        node.next = current;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  // 返回第一个匹配元素的位置
  indexOf(element) {
    let current = this.head;
    for(let i = 0; i < this.count; i++) {
      if(element === current.element) {
        return i;
      }
    }
    return -1;
  }

  // 从链表中移除第一个匹配元素
  remove(element) {
    let index = indexOf(element);
    return this.removeAt(index)
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.size() === 0;
  }

  getHead() {
    return this.head;
  }

  toString() {
    if(this.head == null) {
      return ''
    } 
    let result = this.head.element;
    let current = this.head.next;
    for(let i = 1; i < this.count; i++) {
      result = `${result},${current.element}`
      current = current.next
    }
    return result;
  }
}

2. 双向链表

双向链表中每个节点有两个指针，一个指向下一个元素，一个指向上一个元素。

DoublyLinkedList 类：

class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);
    this.prev = prev;
  }
}

class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    this.tail = undefined;
  }
}

2.1 在任意位置插入新元素

双向链表插入与单链表类似：

insert(element, index) {
  if (index >= 0 && index <= this.count) {
    const node = new DoublyLinkedList(element);
    let current = 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;
      current.next = node;
      node.prev = current;
      this.tail = node;
    } else {
      const previous = this.getElementAt(index - 1);
      current = previous.next;
      node.next = current;
      current.prev = node;
      previous.next = node;
      node.prev = previous;
    }
    this.count++;
    return true;
  }
  return false;
}

2.2 从任意位置移除元素

removeAt(index) {
  if (index >= 0 && index < this.count) {
    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.getElementAt(index);
      current.prev.next = current.next;
      current.next.prev = current.prev;
    }
    this.count--;
    return current.element;
  }
  return false;
}

3. 循环链表

循环链表与普通链表的唯一区别就是循环链表最后一个节点的 next 指向第一个节点。

CircularLinkedList 类：

class CircularLinkedList extends LinkedList {
  // 不需要任何额外属性
  constructor() {
    super()
  }
}

3.1 在任意位置插入新元素

插入逻辑跟普通链表一样，只不过需要将最后一个元素的 next 指向第一个节点：

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) {
        this.head = node;
        node.next = this.head;
      } else {
        node.next = this.head;
        // 处理最后一个元素
        current = this.getElementAt(this.count - 1);
        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;
}

3.2 从任意位置移除元素

removeAt(index) {
  if(index >= 0 && index < this.count) {
    let current = this.head;
    if(index == 0) {
      if(this.count == 1) {
        this.head = undefined;
      } else {
        const removed = this.head;
        current = this.getElemmentAt(this.count - 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 false;
}

4. 有序链表

元素插入到正确的位置来保证有序性。

SortedLinkedList 类：

const Compare = {
  LESS_TAEN: -1,
  BIGGER_TAEN: 1
}

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

class SortedLinkedList extends LinkedList {
  constructor(compareFn = defaultCompare) {
    super();
    this.compareFn = compareFn
  }
}

4.1 有序插入元素

// 重写 insert 方法
insert(element, index = 0) {
  if (this.isEmpty()) {
    return super.insert(element, 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;
}

5. 创建 StackLinkedList 类

可以使用链表作为内部数据结构来创建其它数据结构，如栈、队列和双向队列。

StackLinkedList 类：

class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList();
  }

  push(element) {
    this.item.push(element);
  }

  pop() {
    if(this.isEmpty()) {
      return undefined;
    }
    return this.items.removeAt(this.size() - 1);
  }

  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();
  }
}

说明

对于 StackLinkedList 类，使用双向列表 DoublyLinkedList 来存储数据，相比单链表，双向链表可以直接获取头尾元素，减少过程消耗，时间复杂度与原始栈实现相同，均为 O(1)。