第二十九题：什么是链表？ about daily HOT 1 OPEN

// 简易单向链表
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class NodeList {
  constructor(item) {
    this.head = new Node(item); // 初始化链表的头节点
  }

  append(item) {
    let newNode = new Node(item);
    let lastNode = this.findLastNode();
    lastNode.next = newNode;
  }

  insert(newItem, beforeItem) {
    let newNode = new Node(newItem);

    if (beforeItem) {
      let currNode = this.findNode(beforeItem);
      newNode.next = currNode.next;
      currNode.next = newNode;
    } else {
      let lastNode = this.findLastNode();
      lastNode.next = newNode;
    }
  }

  findNode(item) {
    // 根据元素查找节点
    let currNode = this.head;
    while (currNode.element != item && currNode) {
      if (currNode.next) {
        currNode = currNode.next;
      } else {
        currNode = null;
      }
    }

    return currNode;
  }

  findLastNode() {
    let currNode = this.head;
    while (currNode.next) {
      currNode = currNode.next;
    }
    return currNode;
  }

  remove(item) {
    let preNode = this.findNode(item);
    if (preNode.next != null) {
      preNode.next = preNode.next.next;
    }
  }

  findPreNode(item) {
    let currNode = this.head;
    while (currNode & currNode.next & (currNode.next.element != item)) {
      if (currNode.next) {
        currNode = currNode.next;
      } else {
        currNode = null;
      }
    }
    return currNode;
  }

  toString() {
    let currNode = this.head;
    let strList = [];
    while (currNode.next) {
      strList.push(JSON.stringify(currNode.element));
      currNode = currNode.next;
    }
    strList.push(JSON.stringify(currNode.element));
    return strList.join("->");
  }

  toReverseString() {
    let currNode = this.head;
    let strList = [];
    while (currNode.next) {
      strList.push(JSON.stringify(currNode.element));
      currNode = currNode.next;
    }
    strList.push(JSON.stringify(currNode.element));
    strList.reverse();
    return strList.join("->");
  }
}

// toReverseString 可用于倒序输出链表（可用双向链表实现 待续）

class LNode {
  constructor(element, previous) {
    this.element = element;
    this.next = null;
    this.previous = null;
  }
}

class NodeLList {
  constructor(item) {
    this.head = new LNode(item); // 初始化链表的头节点
  }

  findNode(item) {
    // 根据元素查找节点
    let currNode = this.head;
    while (currNode.element != item && currNode) {
      if (currNode.next) {
        currNode = currNode.next;
      } else {
        currNode = null;
      }
    }

    return currNode;
  }

  findLastNode() {
    let currNode = this.head;
    while (currNode.next) {
      currNode = currNode.next;
    }
    return currNode;
  }

  insert(newItem, beforeItem) {
    let newNode = new LNode(newItem);

    if (beforeItem) {
      let currNode = this.findNode(beforeItem);
      newNode.next = currNode.next;
      newNode.previous = currNode;
      currNode.next = newNode;
    } else {
      let lastNode = this.findLastNode();
      newNode.previous = lastNode;
      lastNode.next = newNode;
    }
  }

  revertToString() {
    let currNode = this.findLastNode();
    console.log(currNode);
    let strList = [];
    while (currNode.previous) {
      strList.push(JSON.stringify(currNode.element));
      currNode = currNode.previous;
    }
    strList.push(JSON.stringify(currNode.element));
    return strList.join("->");
  }
}

let index1 = 1;
let index2 = 2;
let index3 = 3;

let nList = new NodeLList(index1);

nList.insert(index2);
nList.insert(index3);

console.log("" + nList.revertToString());