JavaScript doubly linked list definition and usage

This article mainly introduces the definition and use of doubly linked lists in JavaScript data structures. It briefly introduces the principles of doubly linked lists, and analyzes the definition and use of doubly linked lists in the form of examples. Friends who need it can refer to it. I hope it can help. to everyone.

The difference between a doubly linked list and an ordinary linked list is that in a linked list, a node only has a link to the next node, while in a doubly linked list, the links are two-way: one link leads to the next element, and the other Chain to the previous element.

Doubly linked lists provide two methods of iterating the list: from beginning to end, or vice versa. We can also access the next or previous element of a specific node. In a one-way linked list, if you miss the element you are looking for while iterating the list, you need to go back to the starting point of the list and start iterating again. This is an advantage of doubly linked lists.

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

Running results:

Related recommendations:

Detailed explanation of PHP based on examples Member ranking function implemented by doubly linked list and sorting operation

Realization of doubly linked list and doubly circular linked list in JavaScript

PHP short tutorial on implementing doubly linked list _PHP tutorial

#

The above is the detailed content of JavaScript doubly linked list definition and usage. For more information, please follow other related articles on the PHP Chinese website!