Dieser Artikel stellt hauptsächlich die Definition und Verwendung doppelt verknüpfter Listen in JavaScript-Datenstrukturen vor. Er stellt kurz die Prinzipien doppelt verknüpfter Listen vor und analysiert die Definition und Verwendung doppelt verknüpfter Listen anhand von Beispielen Ich kann mich darauf beziehen. Ich hoffe, es kann jedem helfen.
Der Unterschied zwischen einer doppelt verknüpften Liste und einer gewöhnlichen verknüpften Liste besteht darin, dass in einer verknüpften Liste ein Knoten nur einen Link zum nächsten Knoten hat, während in einer doppelt verknüpften Liste die Links bidirektional sind: ein Link führt zum nächsten Element und die andere Kette zum vorherigen Element.
Doppelt verknüpfte Listen bieten zwei Möglichkeiten, die Liste zu iterieren: vom Anfang bis zum Ende oder umgekehrt. Wir können auch auf das nächste oder vorherige Element eines bestimmten Knotens zugreifen. Wenn Sie in einer einseitig verknüpften Liste beim Iterieren der Liste das gesuchte Element verpassen, müssen Sie zum Startpunkt der Liste zurückkehren und erneut mit der Iteration beginnen. Dies ist ein Vorteil doppelt verknüpfter Listen.
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'));//1Laufergebnisse:
Verwandte Empfehlungen:
Implementierung von PHP kleines Tutorial Double Linked List_PHP Tutorial
Das obige ist der detaillierte Inhalt vonDefinition und Verwendung einer doppelt verknüpften JavaScript-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
