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,'d');link.insertAt(1,'e');link.insertAt(2,'f');link.insertAt(3,'g');link.insertAt(4,'h');link.insertAt(5,'i');link.insertAt(6,'j');link.insertAt(7,'k');link.removeAt(7);link.removeAt(0);link.print1();//efghijlink.print2();//jihgfeconsole.log(link.getHead());//econsole.log(link.getTail());//jconsole.log(link.indexOf('f'));//1