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; };
感想
链表这一节,基本全部都是先按需求写代码,写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑,逻辑也很混乱。看来还是太年轻了。