学习过数据结构的人都应该清楚,链表是一种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩容。链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个链表的结构:
相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。
在我们现实生活中类似于链表这种数据结构的有很多,比如手表的表链,坦克的履带,火车等。想在其中插入一节需要先断开两节之间的联系,插入之后,将新插入的和之前的两个节点分别在联系起来。
在原生的js中没有链表这么一个存储结构,需要我们来进行手动创建,下面我们来创建一下链表的基本骨架:
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
}
在骨架中,我们需要一个Node类来作为基础节点,每一个节点都是通过new Node来实现的,length用来存储整个链表的长度,head指向链表的头。
然后我们需要实现以下链表的基本功能:
append方法实现的是向链表的末尾添加一个元素,如果链表长度为0,则直接首元素就是该添加的元素,具体实现方式如下:
this.append = function(element){
var node = new Node(element);
var current = null;
if(head==null){
//此时链接长度为空,直接插入为首元素
head = node;
}else{
current = head;
while(current.next!=null){
//遍历查找链表,直到找到最后一个元素
current = current.next;
}
current.next = node;
}
//更新链表长度
length++;
}
添加时首先要判断的是链表长度是否为空,也就是head首元素是否为null,也可以判断length是否为0。我们创建的Node类中next始终null,代表的是新创建的元素为末尾元素,其next为null,如果next不为空,则说明该值不是末尾元素,这为添加末尾元素时提供了判断依据。
向列表的特定位置插入一个新的项,返回最终插入的位置,我们来看一下实现代码:
this.insert = function(position,element){
try{
position = parseInt(position);
if(isNaN(position)||position>length){
//position为非数字或者长度大于链表长度,则position位置为末尾插入
position = length;
}else if(position<0){
//如果小于0,则默认插入链表顶部
position = 0;
}
var node = new Node(element);
var current = head,index = 0,previous = null;
if(position==0){
node.next = current;
head = node;
}else{
while(index++<position){
previous = current;
current = previous.next;
}
node.next = current;
previous.next = node;
}
length++;
return position;
}catch(e){
console.log(e)
}
}
插入方法需要检测判断一下这个position是否合法,如果是非数字或者数值大于链表长度,则默认添加到链表的尾部,如果数值小于0,则默认添加到链表的头部,然后则是创建一个节点,之后遍历链表,查找到其合适位置进行插入,最后更新链表长度,并将插入位置返回。
实现效果如图所示:
从链表中特定位置移除元素和插入元素一样都需要判断position是否合法,但是该方法不能默认值,只要不合法就不能进行删除操作,以防误删数据,不存在的位置直接返回false,否则返回true,具体实现代码如下:
this.removeAt(position){
try{
position = parseInt(position);
if(isNaN(position)||position>length||position<0){
return false
}
var current = head,index = 0,previous = null;
if(length==0){
return false;
}else if(position==0){
head = current.next;
}else{
while(index++<position){
previous = current;
current = previous.next;
}
previous.next = current.next;
}
length--;
return true;
}catch(e){
console.log(e);
return false;
}
}
indexOf方法返回元素在列表中的索引,如果列表中没有该元素则返回-1。传入的参数是元素本身,我们需要对元素本身进行查找匹配,这里的元素有可能存储的是基本数据类型,也有可能是引用数据类型,这里我们需要进行区分。我们来看一下实现代码:
this.indexOf = function(element){
var current = head;
var index = -1;
while(current){
index++;
if(current.element instanceof Object&& JSON.stringify(current.element)==JSON.stringify(element)){
return index
}else if(!(current.element instanceof Object)&¤t.element==element){
return index;
}
current = current.next;
}
return index;
}
remove方法就很简单了,我们可以借助上面的indexOf和removeAt方法来进行实现,首先通过indexOf来获取元素位置,然后通过removeAt方法来进行删除操作,下面来看示例代码:
this.remove = function(element){
var index = this.indexOf(element);
if(index = -1){
return false;
}
return this.removeAt(index);
}
这个方法很容易实现了,只需要判断他的length即可:
this.isEmpyt = function(){
return length==0
}
这个方法和上面那个判断类似,只需要将length返回即可:
this.size = function(){
return length;
}