JS数据结构-单项链表

前言

数组这种数据结构是非常普遍的, 但是它有一个缺点: 从数组开头或中间插入元素是非常不方便的, 因为需要移动后面的所有元素. 于是就有了链表这种数据结构.

链表的每一个节点存储元素本身和指向下一个节点的引用(指针). 但链表也有一个缺点: 链表访问任何元素, 必须从第一个节点开始遍历, 直到找到元素为止. 而数组可以直接访问.

所以说如果要频繁插入或删除元素的时候适合使用链表, 而频繁访问的时候适合使用数组.

实现

class LinkedList{

  length = 0; //记录链表长度
  head = null; //记录第一个元素

  //生成节点
  _genNode(element){
    return {
      element,
      next:null,//生成的节点在没有插入链表时, 指针不指向任何元素
    }
  }

  //链表末尾添加一个元素
  append(element){
    const node = this._genNode(element);
    //如果链表为空, 直接作为第一个元素
    if(this.head === null){ 
      this.head = node;
      this.length++;
      return
    }
    let current = this.head; //记录当前元素
    //循环遍历找到链表中最后一个元素插入
    while(current.next){
      current = current.next;
    }
    //让最后一个元素指向节点
    current.next = node;
    this.length++;
  }

  //根据节点在链表中位置移除节点
  removeAt(position){
    //检查位置的正确性, 不能小于等于-1, 大于链表本身长度
    if(position<=-1 || position > this.length){
      return null
    }
    let current = this.head; //存放当前节点
    let previous = null; //存放上一个节点
    let index = 0; //存放当前节点位置
    //删除元素的本质就是让某个节点不被任何元素引用也不引用任何节点
    //移除第一个元素
    if(position === 0){
      this.head = current.next;
      this.length--;
      return current.element
    }
    //移除其他位置的元素, 也就是让需要被移除的元素的上一个节点和下一个节点相连
    while(index++<position){
      previous = current;
      current = current.next;
    }
    previous.next = current.next;
    this.length--;
    return current.element;
  }

  //在任意位置插入一个元素
  insert(position,element){
    if(position<=-1 || position > this.length){
      return false
    }
    const node = this._genNode(element);
    if(position ===0){
      const current = this.head;
      node.next = current;
      this.head = node;
      this.length++;
      return true
    }
    const current = this._findCurrentByPosition(position)
    const previous = this._findPreviousByPosition(position)
    node.next = current;
    previous.next = node;
    this.length++;
    return true
  }

  //找出给定位置的当前元素
  _findCurrentByPosition(position){
    let current = this.head;
    let previous = null;
    let index = 0;
    while(index++<position){
      previous = current;
      current = current.next;
    }
    return current;
  } 

  //找出给定位置的上一个元素
  _findPreviousByPosition(position){
    let current = this.head;
    let previous = null;
    let index = 0;
    while(index++<position){
      previous = current;
      current = current.next;
    }
    return previous;
  }

  toString(){
    let res = ''
    let current = this.head;
    while(current){
      res+=`,${current.element}`
      current = current.next
    }
    return res.slice(1);
  }

  //找出元素位置
  indexOf(element){
    let current = this.head;
    let index = 0;
    while(current){
      if(element === current.element){
        return index
      }
      index++;
      current = current.next;
    }
  }

  //根据元素删除该节点
  remove(element){
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  isEmpty(){
    return this.length === 0
  }

  size(){
    return this.length
  }

  //获取第一个节点
  getHead(){
    return this.head
  }
}

结尾

我们今天实现了单项链表, 也就是当前节点可以指向下一个节点, 但是不能指向上一个节点. 下一篇我们来实现双向链表和循环链表.