链表入门

节点

节点是链表中的基本最小单元，由两个基本属性组成，data是数据，next为指向。

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

有头链表，无头链表

指的是头部是否存放数据，图解如下：

代码实现

基本结构

function LinkList(){
    function Node(data){
      this.data = data;
    this.next = null
  }
  let length = 0;
  let head = null;
  let tail = null;
  //链表尾部加入数据
    this.append = function(data){
    let newNode = new Node(data);
      if(head === null){
          head = newNode
            tail = newNode;
    }else{
        tail.next = newNode;
      tail = newNode;
    }
    length +=1;
  }
  //打印节点数据 遍历链表
  this.print = function(){
      let currentNode = head;
    while(currentNode){
        console.log(currentNode.data);
      currentNode = currentNode.next
    }
  }
}

insert插入方法

 // 指定位置加入一个元素
  this.insert = funnction(index,data){
    if(index < 0 || index > length){
        return false;
    }
      if(index === length){
        this.append(data);
    } else {
        let newNode = new Node(data);
      if(index === 0 ){
        newNode.next = head;
        head = newNode;
      } else {
          let currentNode = head;
        let currentIndex = 1;
        while(currentIndex < index){
          currentIndex += 1;
            currentNode = currentNode.next;
        }
        newNode.next = currentNode.next;
        currentNode.next = newNode;
      }
    }
    length += 1
  }

指定位置删除一个元素

与增加逻辑差不多，这里只重点理解循环部分的逻辑

 // 指定位置一个元素
  this.remove = funnction(index){
    if(index < 0 || index > length){
        return false;
    }
      if(index === length){
        this.pop(length);
    } else {
        let newNode = new Node(data);
      if(index === 0 ){
        head = head.next;
      } else {
          let currentNode = head;
        let currentIndex = 1;
        while(currentIndex < index){
          currentIndex += 1;
            currentNode = currentNode.next;
        }
        currentNode.next = currentNode.next.next;
      }
    }
    length--
  }