Javascript数据结构之链表

链表数据结构

存储多个元素，数组或者列表是常用的数据结构。而这种数据结构有一个缺点：在大多数语言中数组的大小是固定的，从数组的起点或中间插入或移除值所成本很高，因为需要移动元素。Javascript 有 array 类的方法，很方便做这些事，但背后的实现是一样的。

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

head->[value, next]->[value,next]->[value,undefined]

功能

• push(element)：向链表尾部插入一个新元素
• insert(element, position)：向链表的特定位置插入一个新元素
• getElementAt(index)：返回链表中特定位置的元素，如果链表中不存在这样的元素，则返回 undefined
• remove(element)：从链表中移除一个元素
• indexOf(element)：返回元素在链表中的索引，如果链表中没有该元素则返回-1
• removeAt(position)：从链表中特定位置移除一个元素
• isEmpty()：如果链表里没有任何元素就返回 true，否则返回 false
• clear()：移除链表里所有元素
• size()：返回链表里的元素个数，该方法和数组的 length 属性很类似

function defaultEquals(a, b) {
  return a === b;
}

class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

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) {
        current = current.next;
      }
      current.next = node
    }
    this.count++
  }

  // 向链表中特定位置插入元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      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;
  }

  // 从链表中移除元素
  removeAt(index) {
    // 检查越界值
    if (index >=0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        let previous;
        for (let i = 0; i < index; i++) {
          previous = current;
          current = current.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;
  }

  // 重构 remove 方法
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  // 返回一个元素的位置
  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;
  }

  // 链表元素个数
  size() {
    return this.count;
  }

  // 链表是否包含元素
  isEmpty() {
    return this.size() === 0;
  }

  // 链表表头元素
  getHead() {
    return this.head;
  }

  // 清除数据
  clear() {
    this.count = 0;
    this.head = undefined;
  }

  // toString方法
  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;
  }
}

const list = new LinkedList();
list.push(15);
list.push(10);
console.log(list.toString()); // 15,10
console.log(list.getHead()); // Node { element: 15, next: Node { element: 10, next: undefined } }
console.log(list.getElementAt(1)) // Node { element: 10, next: undefined }
list.push(20);
list.push(30);
console.log(list.removeAt(1)) // 10
console.log(list.toString()); // 15,20,30
console.log(list.indexOf(30)) // 2
list.insert(100, 1);
console.log(list.toString()); // 15,100,20,30
console.log(list.getHead());

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个子节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，别一个链向前一个元素。

head -> [prev,value,next] -> [prev,value,next] -> [prev,value,tail]

function defaultEquals(a, b) {
  return a === b;
}

class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

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) {
        current = current.next;
      }
      current.next = node
    }
    this.count++
  }

  // 向链表中特定位置插入元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      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;
  }

  // 从链表中移除元素
  removeAt(index) {
    // 检查越界值
    if (index >=0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        let previous;
        for (let i = 0; i < index; i++) {
          previous = current;
          current = current.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;
  }

  // 重构 remove 方法
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  // 返回一个元素的位置
  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;
  }

  // 链表元素个数
  size() {
    return this.count;
  }

  // 链表是否包含元素
  isEmpty() {
    return this.size() === 0;
  }

  // 链表表头元素
  getHead() {
    return this.head;
  }

  // 清除数据
  clear() {
    this.count = 0;
    this.head = undefined;
  }

  // toString方法
  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 {
  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;
    } else {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

  // 双向链表从任意位置区别：要同时控制 next 和 prev 两个指针
  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;
          this.head.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;
        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 = this.head.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);
        const previous = current.prev;
        previous.next = current.next;
        previous.next.prev = previous;
      }
      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},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

const doublyList = new DoublyLinkedList();
doublyList.push(15);
doublyList.push(10);
console.log(doublyList.toString()); // 15,10
console.log(doublyList.getHead()); // DoublyNode { element: 15, next: DoublyNode { element: 10 }, prev: undefined }
console.log(doublyList.getElementAt(1)) // DoublyNode { element: 10, next: undefined, prev: DoublyNode { element: 15 } }
doublyList.push(20);
doublyList.push(30);
console.log(doublyList.removeAt(1)) // 10
console.log(doublyList.toString()); // 15,20,30
console.log(doublyList.indexOf(30)) // 2
doublyList.insert(100, 1);
console.log(doublyList.toString()); // 15,100,20,30
console.log(doublyList.getHead());

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在一，最后一个元素指向下一个元素的指针 tail.next，不是引用 undefined，而是指向第一个元素 head。

head -> [value,next] -> [value,next] -> [value,next]

有序链表

有序链表是指保持元素有序的链表结构。除了使用排序算法之外，还可以将元素插入到正确的位置来保证链表的有序性。