js数据结构-双向链表和循环链表

前言

我们今天来讨论双向链表和循环链表

正文

双向链表

这种数据结构和单向链表的区别在于每个节点有指向前一个节点的引用(指针). 相比于单向链表的优点: 双向链表提供了两种迭代方法, 从头到尾或反过来. 我们也可以访问一个特定节点的下一个或前一个元素. 而在双向链表中, 如果迭代列表时错过了要寻找的元素, 必须从头开始再来一次.

class DoublyLinkedList{

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

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

  //在任意位置插入一个元素
  insert(position,element){
    if(position<=-1 || position > this.length){
      return false
    }
    const node = this._genNode(element);
    //把节点做为第一个元素
    if(position ===0){
      const current = this.head;
      if(!this.head){//如果链表中没有任何元素
        this.head = node;
        this.tail = node;
      }else{//如果链表中有其他元素
        node.next = current;
        current.prev = node;
        this.head = node;
      }
      this.length++;
      return true;
    }
    //把节点做为最后一个元素
    if(position === this.length){
      current = this.tail;
      current.next = node;
      node.prev = current;
      this.tail = node;
      this.length++;
      return true;
    }
    //把节点插入中间
    const next = this._findCurrentByPosition(position)
    const previous = this._findPreviousByPosition(position)
    node.next = next;
    node.prev = previous;
    previous.next = node;
    next.prev = node;
    this.length++;
    return true
  }

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

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

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

  //...其他方法省略...
}

循环链表

循环链表既可以是单向也可以是双向, 循环链表只不过让第一个节点的和末尾节点相连, 如果是单向循环链表, 只需要让末尾的节点指向开头节点就行. 如果是双向则开头节点也同时指向末尾节点.

结尾

我们今天学习了双向链表和循环链表, 其中双向链表在应用中是非常广泛的, 大家要重点掌握.