使用javascript实现一个链表结构

单向链表

链表包含一些基础功能，在此只会简单的实现几个功能点。

创建链表节点

链表包含一个数据域和指针域

class Node {
  constructor(data){
    this.data = data;
    this.next = null;
  }
}
复制代码

生成一条单向链表

function createNode(){
  const head = new Node(1);
  let node = head;
  for (let i = 2; i < 6 ; i++) {
    node.next = new Node(i);
    node = node.next;
  }
  return head;
}
复制代码

创建一个操作单向链表的类

创建类

接收一个链表

constructor(nodeList){
  this.nodeList = nodeList;
}
复制代码

查找链表节点

遍历链表，如果链表值不等于当前节点，那么就往下走一步。

  findNode(val){
    let currentList = this.nodeList;
    while (currentList && currentList.data !== val) {
      currentList = currentList.next;
    }
    return currentList;
  }
复制代码

添加节点

接收一个节点，并添加节点到头节点位置之后，原节点赋值给当前添加节点的下一个指针域，如果链表中没有节点，则直接赋值。

  addNode(node){
    if(!this.nodeList){
      this.nodeList = node;
      this.getNodeList();
      return;
    }
    const next = this.nodeList.next;
    node.next = next;
    this.nodeList.next = node;
    this.getNodeList();
  }
复制代码

删除节点

如果删除头节点，那么直接将节点往后走一步，删除其他节点，就遍历链表结构，找到当前节点位置，和上一个节点位置，将上一个节点位置指向下下个节点位置，就完成了当前节点的删除。

  deleteNode(val){
    let currentList = this.nodeList;
    let prev;
    if(currentList.data === val){
      currentList = currentList.next && currentList.next;
      this.nodeList = currentList;
    }
    while (currentList && currentList.data !== val) {
      prev = currentList;
      currentList = currentList.next;
    }
    if(prev && prev.next){
      prev.next = prev.next.next;
    }
    this.getNodeList();
  }
复制代码

获取当前链表

返回当前链表，并输出所有链表的值。

  getNodeList(){
    let node = this.nodeList;
    let resultVal = '';
    while (node) {
      resultVal += `-> ${node.data} `;
      node = node.next;
    }
    console.log(resultVal);
    return this.nodeList;
  }
复制代码

整体代码

效果截图

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

function createNode(){
  const head = new Node(1);
  let node = head;
  for (let i = 2; i < 6 ; i++) {
    node.next = new Node(i);
    node = node.next;
  }
  return head;
}

class SingleLinkedList{

  constructor(nodeList){
    this.nodeList = nodeList;
  }

  getNodeList(){
    let node = this.nodeList;
    let resultVal = '';
    while (node) {
      resultVal += `-> ${node.data} `;
      node = node.next;
    }
    console.log(resultVal);
    return this.nodeList;
  }

  findNode(val){
    let currentList = this.nodeList;
    while (currentList && currentList.data !== val) {
      currentList = currentList.next;
    }
    return currentList;
  }

  addNode(node){
    if(!this.nodeList){
      this.nodeList = node;
      this.getNodeList();
      return;
    }
    const next = this.nodeList.next;
    node.next = next;
    this.nodeList.next = node;
    this.getNodeList();
  }

  deleteNode(val){
    let currentList = this.nodeList;
    let prev;
    if(currentList.data === val){
      currentList = currentList.next && currentList.next;
      this.nodeList = currentList;
    }
    while (currentList && currentList.data !== val) {
      prev = currentList;
      currentList = currentList.next;
    }
    if(prev && prev.next){
      prev.next = prev.next.next;
    }
    this.getNodeList();
  }
}

let nodeList = new SingleLinkedList(createNode());
nodeList.addNode(new Node(10));
nodeList.addNode(new Node(11));
nodeList.addNode(new Node(12));
nodeList.deleteNode(1);
nodeList.deleteNode(2);
nodeList.deleteNode(5);
复制代码