JavaScript数据结构与算法之链表
链表简介
链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
接下来就是介绍两种常见的链表:单向链表，双向链表在JavaScript中的实现。
单向链表
链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL:
JavaScipt中单向链表的实现
首先，创建一个构造函数。
/**
*单向链表构造函数
*/
functionLinkedList(){
/**
*单向链表中节点的构造函数
*@param{Any}element要传入链表的节点
*/
varNode=function(element){
this.element=element;
//下个节点的地址
this.next=null;
}
//单向链表的长度
varlength=0;
//单向链表的头结点，初始化为NULL
varhead=null;
}
不难看出，单向链表构造函数比栈与队列要复杂许多。
单向链表需要有如下的方法:
- append(element):添加元素到链表尾部
- insert(position,element):向单向链表中某个位置插入元素
- indexOf(element):寻找某个元素在单向链表中的位置
- remove(element):移除给定的元素
- removeAt(position):移除单向链表中某个位置的元素
- getHead():获取单向链表的头部
- isAmpty():检查单向链表是否为空，为空则返回true
- toString():将链表所有内容以字符串输出
- size():返回单向链表长度
append方法:
说明:向单向链表尾部添加元素。
实现:
/**
*向单向链表尾部添加元素
*@param{Any}element要加入链表的节点
*/
this.append=function(element){
varnode=newNode(element);
varcurrent;
if(head==null){
head=node;
}else{
//当前项等于链表头部元素.
//while循环到最后一个，从而将该节点加入链表尾部。
current=head;
//当next为null时，判定为false。退出循环。
while(current.next){
current=current.next;
}
current.next=node;
}
length++;
};
insert方法:
说明:向单向链表中某个位置插入元素。
实现:
/**
*向单向链表中插入某个元素
*@param{Number}position要插入的位置
*@param{Any}element要插入的元素
*@return{Boolean}插入成功返回true，失败返回false
*/
this.insert=function(position,element){
if(position>=0&&position<=length){
varnode=newNode(element);
varcurrent=head;
varprevious;
varindex=0;
if(position==0){
node.next=current;
head=node;
}else{
while(index++<position){
previous=current;
current=current.next;
}
previous.next=node;
node.next=current;
}
length++;
returntrue;
}else{
returnfalse;
}
};
indexOf方法:
说明：寻找某个元素在单向链表中的位置。
实现:
/**
*寻找某个元素在单向链表中的位置
*@param{Any}element要寻找的元素
*@return{Number}返回值>=0则代表找到相应位置
*/
this.indexOf=function(element){
varcurrent=head;
varindex=-1;
while(current){
if(element===current.element){
returnindex;
}
index++;
current=current.next;
}
return-1;
};
remove方法:
说明:移除给定的元素。
实现:
/**
*移除给定的元素
*@param{Any}element要移除的元素
*@return{Number}返回值>=0表示移除成功
*/
this.remove=function(element){
varindex=this.indexOf(element);
returnthis.removeAt(index);
};
removeAt方法:
说明:移除单向链表中某个位置的元素。
实现:
/**
*移除单向链表中某一个元素
*@param{Number}position要移除元素的位置
*@return{Any}移除成功返回被移除的元素，不成功则返回NULL
*/
this.removeAt=function(position){
if(position>-1&&position<length){
varcurrent=head;
varprevious;
varindex=0;
if(position==0){
//因为之前head指向第一个元素，现在把head修改为指向第二个元素。
//核心概念在于链表前后全靠指针链接，而非数组一般。
//所以只需要改变head的元素。
head=current.next;
}else{
while(index++<position){
//previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
previous=current;
current=current.next;
}
previous.next=current.next;
}
length--;
returncurrent.element;
}else{
returnnull;
}
};
getHead方法:
说明:获取单向链表的头部。
实现:
/**
*获取单向链表的头部
*@return{Any}单向链表的头部
*/
this.getHead=function(){
returnhead;
}
isAmpty、toString、size方法
实现:
/**
*判断单向链表是否为空
*@return{Boolean}为空则返回true，不为空则返回false
*/
this.isAmpty=function(){
returnlength===0
};
/**
*将链表所有内容以字符串输出
*@return{String}要输出的字符串
*/
this.toString=function(){
varcurrent=head;
varstring='';
while(current){
string+=current.element;
current=current.next;
}
returnstring;
};
/**
*返回单向链表长度
*@return{Number}单向链表的长度
*/
this.size=function(){
returnlength;
};
双向链表
双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。
JavaScipt中双向链表的实现
首先，依然是构造函数:
/**
*双向链表的构造函数
*/
functionDoublyLinkedList(){
/**
*双向链表中节点的构造函数
*@param{Any}element要传入链表的元素
*/
varNode=function(element){
this.element=element;
this.prev=null;
this.next=null;
}
//双向链表的长度
varlength=0;
//双向链表的头结点，初始化为NULL
varhead=null;
//双向链表的尾结点，初始化为NULL
vartail=null;
}
双向链表需要有如下的方法:
- append(element):添加元素到双向链表尾部
- insert(position,element):向双向链表中某个位置插入元素
- removeAt(position):移除双向链表中某个位置的元素
- showHead():获取双向链表的头部
- showLength():获取双向链表长度
- showTail():获取双向链表尾部
append方法:
说明:添加元素到双向链表尾部
实现:
/**
*向链表尾部添加元素
*@param{Any}element要加入链表的节点
*@return{Any}加入链表的节点
*/
this.append=function(element){
varnode=newNode(element);
if(head===null){
head=node;
tail=node;
}else{
varprevious;
varcurrent=head;
while(current.next){
current=current.next;
}
current.next=node;
node.prev=current;
tail=node;
}
length++;
returnnode;
};
insert方法:
说明:向双向链表中某个位置插入元素。
实现:
/**
*向链表中插入某个元素
*@param{Number}position要插入的位置
*@return{Boolean}插入成功返回true，失败返回false
*/
this.insert=function(position,element){
if(position>=0&&position<=length){
varnode=newNode(element);
varindex=0;
varprevious;
varcurrent=head;
if(position===0){
if(head===null){
head=node;
tail=node;
}else{
current.prev=node;
node.next=current;
head=node;
}
}elseif(position===length){
current=tail;
current.next=node;
node.prev=current;
tail=node;
}else{
while(index++<position){
previous=current;
current=current.next;
}
previous.next=node;
node.prev=previous;
current.prev=node;
node.next=current;
}
length++;
returntrue;
}else{
returnfalse;
}
};
removeAt方法:
说明:移除双向链表中某个位置的元素。
实现:
/**
*移除链表中某一个元素
*@param{Number}position要移除元素的位置
*@return{Any}移除成功返回被移除的元素，不成功则返回false
*/
this.removeAt=function(position){
if(position>-1&&position<length){
varcurrent=head;
varindex=0;
varprevious;
if(position===0){
head=current.next;
if(length===1){
tail=null;
head.prev=null;
}
}elseif(position===length-1){
current=tail;
tail=current.prev;
tail.next=null;
}else{
while(index++<position){
previous=current.prev;
current=current.next;
}
previous.next=current.next;
current.next.prev=previous;
}
length--;
returncurrent.element;
}else{
returnfalse;
}
};
showHead、showLength、showTail方法
实现:
/**
*获取链表的头部
*@return{Any}链表的头部
*/
this.showHead=function(){
returnhead;
};
/**
*获取链表长度
*@return{Number}链表长度
*/
this.showLength=function(){
returnlength;
};
/**
*获取链表尾部
*@return{Any}链表尾部
*/
this.showTail=function(){
returntail;
};
感想
链表这一节，基本全部都是先按需求写代码，写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑，逻辑也很混乱。看来还是太年轻了。