第 75 期(数据结构-链表)：单链表的实现

[wingmeng]

/**
  * 链表构造器
  */
class LinkedList {
  constructor(...list) {
    this._head = new Node('head');  // 头节点

    if (list.length) {
      this.insert('head', list[0]);

      for (let i = 1; i < list.length; i++) {
        this.insert(list[i - 1], list[i])
      }
    }
  }

  // 查找节点
  // 从头节点开始遍历，直至找到目标节点
  find(value) {
    let curNode = this._head;

    while (curNode && curNode.value !== value) {
      curNode = curNode.next
    }

    return curNode;
  }

  // 通过索引值查找对应元素
  findIndex(index) {
    let curNode = this._head;
    let tempIdx = 0;

    while (curNode !== null) {
      if (tempIdx === index + 1) {
        return curNode
      }

      tempIdx += 1;
      curNode = curNode.next;
    }

    return null;
  }

  // 查找目标节点的上一个节点
  findPrev(value) {
    let curNode = this._head;
    
    while (curNode.next !== null && curNode.next.value !== value) {
      curNode = curNode.next
    }
    
    return curNode;
  }

  // 在目标节点的后面插入新节点
  insert(value, newValue) {
    const newNode = new Node(newValue);
    const curNode = this.find(value);

    if (curNode) {
      newNode.next = curNode.next;
      curNode.next = newNode;
    } else {
      console.error(`insert error：链表中不存在 \`${value}\` 节点`)
    }
  }

  // 在目标索引插入新节点
  insertIndex(index, newValue) {
    const newNode = new Node(newValue);
    const curNode = this.findIndex(index);

    if (curNode) {
      newNode.next = curNode.next;
      curNode.next = newNode;
    } else {
      console.error(`insertIndex error：链表中不存在 \`${index}\` 索引节点`)
    }
  }

  // 在链表末尾添加节点
  push(newValue) {
    const newNode = new Node(newValue);
    let curNode = this._head;

    while (curNode.next !== null) {
      curNode = curNode.next
    }

    curNode.next = newNode;
  }

  // 删除指定链表节点
  remove(value) {
    const preNode = this.findPrev(value);
    const curNode = preNode.next;

    if (preNode && curNode) {
      preNode.next = preNode.next.next
    }
  }

  // 删除指定索引对应的节点
  removeIndex(index) {
    const preNode = this.findIndex(index - 1);
    const curNode = this.findIndex(index);

    if (preNode && curNode) {
      preNode.next = curNode.next
    }
  }

  // 获取链表长度（不含头部节点）
  size() {
    let curNode = this._head;
    let tempSize = 0;

    while (curNode.next !== null) {
      tempSize += 1;
      curNode = curNode.next;
    }

    return tempSize;
  }
}

/**
  * 节点构造器
  * value - 当前节点的值
  * next - 指向下一节点的指针
  */
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

上述代码参考自（有改动）：lvwxx/blog#1 (comment)

const linkedList = new LinkedList('节点1', '节点2');

console.group('初始化插入节点："节点1", "节点2"');
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();

console.group('在"节点2"后面插入"节点3"');
linkedList.insert('节点2', '节点3');
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();

console.group('查找节点');
console.log('节点2', linkedList.find('节点2'));
console.log('节点100', linkedList.find('节点100'));
console.log('索引0', linkedList.findIndex(0));
console.log('索引100', linkedList.findIndex(100));
console.groupEnd();

console.group('在索引1后面插入"Node"');
linkedList.insertIndex(0, 'Node');
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();

console.group('在链表末尾插入"节点n"');
linkedList.push('节点n');
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();

console.group('删除"节点1"');
linkedList.remove('节点1');
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();

console.group('删除索引2对应的节点');
linkedList.removeIndex(2);
console.log(linkedList);
console.log('链表长度：', linkedList.size());
console.groupEnd();