6 【单向链表】单向链表

昨天写链表出现了一些问题，而且现有教材有些代码陈旧，没有使用ES6语法，于是啃了一天的ES6，笔记还在整理，整理好了会发上来。
这个单向链表开始理解很难，但彻底理解了之后就茅塞顿开，写起来很顺畅，而且获取链节点，删除链节点，获取位置等代码方法之间可以来回复用，真的太舒服了！！！

"use strict"

class ListNode {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class List {
  
  // 构造函数
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // 在链表尾插入节点（√）
  append (element) {
    // 定义插入的节点
    let node = new ListNode(element)
    let current

    if (this.head === null) {
      this.head = node
    } else {
      current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }

    this.length ++
  }

  // 从链表中移除元素
  removeAt (position) {
    
    // 检测输入是否合法
    if (position <= 0 || position > this.length) {
      return 'ERROR'
    } else {
      let current = this.head
      let previous
      let index = 1

      // 寻找需要删除的节点
      while (index++ < position ) {
        previous = current
        current = current.next
      }

      // 将此节点的next截断
      // 将上一节点的next改为下一节点
      previous.next = current.next
      current.next = null

      // 返回数组长度
      this.length --

      return current.element
    }
  }

  // 从固定位置插入元素
  // 插入位置为position 的前一位
  insert (position, element) {
    
    if (position < 1 || position > this.length) {
      
      return 'ERROR'

    } else {
      
      let current = this.head
      let previous
      let index = 1
      let node = new ListNode(element)

      // 找到节点
      while (index ++ < position) {
        previous = current
        current = current.next
      }

      previous.next = node
      node.next = current
      
      this.length ++

      return '追加节点完成!'
    
    }

  }

  // 将所有节点变成字符串输入、
  // 可用于检查
  toString () {
    let current = this.head
    let string = ''
    let index = 1

    while (index++ <= this.length) {
      string += current.element
      current = current.next
    }

    return string
  }

  // 根据元素内容查找节点，有则范围序号，无则返回-1
  indexOf (element) {
    let current = this.head
    let index = 1
    let output = -1

    while (index++ <= this.length) {
      if (current.element === element) {
        // 此时index已经++
        output = index - 1
        break;
      }
      current = current.next
    }

    return output
  }

  // 查找元素并删除
  // 代码复用
  remove (element) {
    let index = this.indexOf(element)
    return this.removeAt(index)
  }

  // 返回链表长度
  size () {
    return this.length
  }

  // 检查是否为空
  isEmpty () {
    return this.length === 0 ? 'is null' : 'not null'
  }

  // 获取头文件
  getHead () {
    return this.head
  }

  // 测试用
  // 显示所有链表节点
  showAll () {
    let current = this.head
    let index = 1

    console.log("----开始显示节点----");
    while ( index ++ < this.length) {
      console.log(current.element);
      current = current.next
    }
    console.log(current.element);
    return '----节点显示完成----'
  }
}

// 测试
let list = new List()
for (let i = 1; i <= 5 ; i++) {
  list.append(i)
}
console.log('链表长度为' + list.length);
console.log('测试开始===================');
console.log('====  1. 测试移除节点  ====');
console.log(list.removeAt(3));
console.log('链表长度为：' + list.length);
console.log(list.showAll());
console.log('===========================');
console.log('====  2. 测试追加节点  ====');
console.log(list.insert(2, 9999));
console.log('链表长度为：' + list.length);
console.log(list.showAll());
console.log('===========================');
console.log('====  3. 测试toString  ====');
console.log(list.toString());
console.log('链表长度为：' + list.length);
console.log(list.showAll());
console.log('===========================');
console.log('====  4. 测试indexOf  ====');
console.log(list.indexOf(9999));
console.log('链表长度为：' + list.length);
console.log(list.showAll());
console.log('===========================');
console.log('====  5. 测试remove  ====');
console.log(list.remove(9999));
console.log('链表长度为：' + list.length);
console.log(list.showAll());
console.log('===========================');
console.log('====  6. 测试size  ====');
console.log(list.size());
console.log('===========================');
console.log('====  7. 测试isEmpty  ====');
console.log(list.isEmpty());
console.log('===========================');
console.log('====  8 测试getHead  ====');
console.log(list.getHead());
console.log('===========================');
console.log('测试完成!');