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();//efghij
link.print2();//jihgfe
console.log(link.getHead());//e
console.log(link.getTail());//j
console.log(link.indexOf('f'));//1