JavaScript資料結構中雙向鍊錶的使用定義的範例

本文實例講述了JavaScript資料結構之雙向鍊錶定義與使用方法。分享給大家供大家參考，具體如下：

雙向鍊錶和普通鍊錶的區別在於，在鍊錶中，一個節點只有鏈向下一個節點的鏈接，而在雙向鍊錶中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。

雙向鍊錶提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以存取一個特定節點的下一個或前一個元素。在單向鍊錶中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鍊錶的一個優點。

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

執行結果：

以上是JavaScript資料結構中雙向鍊錶的使用定義的範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！