Définition et utilisation de la liste doublement chaînée JavaScript-js tutoriel-php.cn

Définition et utilisation de la liste doublement chaînée JavaScript

小云云

Libérer： 2018-01-20 10:41:32

original

1615 Les gens l'ont consulté

Cet article présente principalement la définition et l'utilisation des listes doublement liées dans les structures de données JavaScript. Il présente brièvement les principes des listes doublement liées et analyse la définition et l'utilisation des listes doublement liées sous forme d'exemples. je peux m'y référer. J'espère que cela pourra aider tout le monde.

La différence entre une liste doublement chaînée et une liste chaînée ordinaire est que dans une liste chaînée, un nœud n'a qu'un lien vers le nœud suivant, tandis que dans une liste doublement chaînée, les liens sont bidirectionnels : un lien mène à l’élément suivant et l’autre Chain à l’élément précédent.

Les listes doublement chaînées offrent deux façons de parcourir la liste : du début à la fin, ou vice versa. Nous pouvons également accéder à l'élément suivant ou précédent d'un nœud spécifique. Dans une liste chaînée unidirectionnelle, si vous manquez l'élément que vous recherchez lors de l'itération de la liste, vous devez revenir au point de départ de la liste et recommencer l'itération. C’est un avantage des listes doublement chaînées.

function DoubleLink(){
  var length=0;//链表长度
  var head=null;//头结点的引用
  var tail=null;//尾节点的引用
  function Node(e){
    this.element=e;
    this.next=null;
    this.previous=null;
  }
  this.insertAt=function(position,e){//在任意位置添加节点
    if(position>=0&&position<=length){//判断边界
      var node=new Node(e);
      var current=head;
      var previous;
      var index=0;
      if(position==0){//在第一个位置添加
        if(!head){//链表为空的时候添加第一个节点
          head=node;
          tail=node;
        }else{
          current=head;
          node.next=current;
          current.previous=node;
          head=node;
        }
      }else if(position==length){//在链表末尾添加
        current=tail;
        current.next=node;
        node.previous=current;
        tail=node;
      }else{
        while(index<position){
          previous=current;
          current=current.next;
          index++;
        }
        previous.next=node;
        node.previous=previous;
        node.next=current;
        current.previous=node;
      }
      length++;
      return true;
    }else{
      return null;
    }
  }
  this.removeAt=function(position){//删除任意位置的节点
    if(position>-1&&position<length){//边界判断
      var current=head;
      var previous;
      var index=0;
      if(position==0){//删除第一个位置的节点
        head=current.next;
        if(length==1){//如果只有一项
          tail=null;
        }else{
          head.previous=null;
        }
      }else if(position==length-1){//删除最后一项
        current=tail;
        tail=current.previous;
        tail.next=null;
      }else{
        while(index<position){
          previous=current;
          current=current.next;
          index++;
        }
        previous.next=current.next;
        current.next.previous=previous;
      }
      length--;
      return current.element;
    }else{
      return null;
    }
  }
  this.indexOf=function(e){//获取节点位置，从头开始数
    var current=head;
    var index=0;
    while(current){
      if(current.element==e){
        return index;
      }
      current=current.next;
      index++;
      if(index>=length)return null;
    }
  }
  this.isEmpty=function(){//判断链表是否为空
    return length==0;
  }
  this.mylength=function(){//链表长度
    return length;
  }
  this.print1=function(){//从头到尾打印链表
    var current=head;
    while(current){
      console.log(current.element);
      current=current.next;
    }
  }
  this.print2=function(){//从尾到头打印链表
    var current=tail;
    while(current){
      console.log(current.element);
      current=current.previous;
    }
  }
  this.getHead=function(){//获取头节点
    return head;
  }
  this.getTail=function(){//获取尾节点
    return tail;
  }
}
var link=new DoubleLink();//实例化一个对象
link.insertAt(0,&#39;d&#39;);
link.insertAt(1,&#39;e&#39;);
link.insertAt(2,&#39;f&#39;);
link.insertAt(3,&#39;g&#39;);
link.insertAt(4,&#39;h&#39;);
link.insertAt(5,&#39;i&#39;);
link.insertAt(6,&#39;j&#39;);
link.insertAt(7,&#39;k&#39;);
link.removeAt(7);
link.removeAt(0);
link.print1();//efghij
link.print2();//jihgfe
console.log(link.getHead());//e
console.log(link.getTail());//j
console.log(link.indexOf(&#39;f&#39;));//1

Copier après la connexion

Résultats en cours :