JS数据结构之单向链表

1、链表的优缺点

优点：

• 插入删除速度快
• 内存利用率高，不会浪费内存
• 大小没有固定，拓展很灵活。

缺点：

• 不能随机查找，必须从第一个开始遍历，查找效率低

2、 链表的JS实现

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  append(element) {
    let node = new Node(element);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
    return true;
  }
  insert(position, element) {
    let node = new Node(element);
    if (position < 0 || position > this.length) {
      return false;
    }
    let current = this.head;
    let previous;
    let index = 0;
    if (position === 0) {
      node.next = current;
      this.head = node;
    } else {
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = node;
      node.next = current;
    }
    this.length++;
    return true;
  }
  update(position, element) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    let index = 0;
    let current = this.head;
    while (index < position) {
      current = current.next;
      index++;
    }
    current.data = element;
    return true;
  }
  indexOf(element) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.data === element) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }
  removeAt(position) {
    if (position < 0 || position >= this.length) {
      return null;
    }
    let current = this.head;
    if (position === 0) {
      this.head = current.next;
    } else {
      let index = 0;
      let previous;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
    }
    this.length--;
    return current.data;
  }
  remove(element) {
    const position = this.indexOf(element);
    return this.removeAt(position);
  }
  isEmpty() {
    return this.length === 0;
  }
  size() {
    return this.length;
  }
  toString() {
    let current = this.head;
    let restult = '';
    while (current) {
      restult += current.data + (current.next ? ' > ' : ' ');
      current = current.next;
    }
    return restult;
  }
}