第二十九题：什么是链表？

[Ray-56]

什么是链表？

构建单向列表

// 链表单元
function ListNode(val) {
    this.val = val;
    this.next = null;
}

写一个方法
输入：[1, 2, 3]
输出：3 -> 2 -> 1

[MMmaXingXing]

什么是链表

链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列节点组成，节点可以在运行时动态生成。每个节点包含两个部分： 一个是存储节点的数据域（当前的数据），另一个是节点地址的指针域（next）。链表允许插入和移除表上任意位置的节点，但是不允许随机存取。

链表有，单向链表、双向链表、循环链表等。

实现一个链表

// 简易单向链表
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());