之前的文章中，我们介绍了数组，我们也知道数组虽然可以随机访问，但是数组在插入、删除的时候会耗费比较多的时间，而且有时候会出现，系统剩余的连续内存不够用的情况。
那么有什么办法可以解决这个问题？当然是链表了。
链表是一组节点的集合。每个节点由两部分组成，前面的盒子用于存储数据，后面的盒子存储着下一个元素的地址。
所以链表中的元素可以存储在内存的任何地方，不需要每个元素连续排列。
链表分为单链表，双链表，循环链表。
下面是一个简单的单链表的结构，由图中可以看出，单链表的最后一个节点(又叫尾节点)的指针为空。
链表基本结构.png
接下来我们实现一个基于对象的单链表。
首先，我们创建一个节点类。
function Node(element)
{
this.element=element;
this.next=null;
}
接下来，我们创建一个链表类。
function linkedList()
{
this.head=new Node("head");
this.find=find;
this.insert=insert;
this.remove=remove;
this.display=display;
this.findLast=findLast;
this.findPrev=findPrev;
}
接下来我们先看看怎么查找已知数据的位置。
function find(element)
{
var curNode=this.head;
while(curNode.element!=element&&curNode)
{
curNode=curNode.next;
}
return curNode;
}
查找最后一个节点
function findLast()
{
var curNode=this.head;
while(curNode.next)
{
curNode=curNode.next;
}
return curNode;
}
展示所有的元素
function display()
{
var curNode=this.head;
while(curNode.next)
{
console.log(curNode.next.element);
curNode=curNode.next;
}
}
链表查找操作会比较浪费时间，因为链表不能随机访问，查找某个节点的数据必须从头开始(单链表而言)。
先找到头节点，才能获得下个节点的地址，进而找到接下来的节点的地址，以此类推。
小贴士：
可能你在我上面的代码中发现了，我创建链表类的时候，默认有一个头节点，你可能会想，为什么要添加这个“多余”的节点呢？不加不行吗？
其实不加是可以的。但是不加的话，当你添加新节点或者删除节点的时候，你就要考虑，链表中是不是存在节点？如果不存在的话，直接添加，不需要处理指针，但是如果存在的话，那么我们就要处理指针这个“头疼”的问题。
接下来我们看看链表里面是怎么插入数据的？
链表的插入.png
由上图可以看出，只需要将插入元素前的指针，和新元素的指针进行修改，即可实现链表插入操作。
function insert(newData,item)
{
var curNode=new Node(newData);
if(item)
{
//在指定的位置插入
var finder=this.find(item);
if(finder)
{
//插入操作
curNode.next=finder.next;
finder.next=curNode;
}
}
else
{
//在链表的最后位置插入
var finder=this.findLast();
curNode.next=finder.next;
finder.next=curNode;
}
}
在进行插入操作的时候，我们首先考虑两者情况：
(1) 在指定的位置插入；
(2) 在链表的最后位置插入；
如果在指定的位置插入元素的话，先要找到对应的节点，如果没找到就不执行插入元素操作。
像上面的插入操作的两行代码，我们能不能交换顺序呢？答案是肯定不行。交换顺序之后，由上面的图片可以得知，mongo节点挂到了apple之后，那么 apple之后的节点就是mongo，但是我们又要将mongo节点挂在了自己的后面，这样会出现指针丢失。所以这里代码的执行顺序尤为重要。
接下来我们看一下链表的节点的删除
链表的删除.png
在了解删除元素之前，我们先看一下，怎么寻找某个元素的前一个元素。
function findPrev(item)
{
var curNode=this.head;
while(curNode&&curNode.next&&curNode.next.element!=item)
{
curNode=curNode.next;
}
if(curNode.next)
{
return curNode;
}
else
{
return null;
}
}
接下来，我们看看具体怎么删除节点。
function remove(item)
{
var curNode=this.head;
var finder=this.findPrev(item);
if(finder)
{
finder.next=finder.next.next;
}
}
最后我们测试一下这个单链表。
var linkList=new linkedList();
linkList.display();
linkList.insert("apple");
linkList.display();
linkList.insert("pear","apple");
linkList.display();
linkList.insert("mongo");
linkList.display();
linkList.remove("pear");
linkList.display();
接下来我们看一道leecode的算法题目(移除链表元素)：
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
首先这道题有多种解法，第一种我们直接删除。
var removeElements = function(head, val) {
//假设头节点不为空
//删除头节点值相同的节点后
//有可能新的头节点值还是相等，用循环处理
while(head!=null&&head.val==val)
{
head=head.next;
}
//处理头节点为空的情况
if(!head)
{
return head;
}
var listNode=head;
//最后，我们处理一般情况
while(listNode.next!=null)
{
if(lastNode.next.val===val)
{
lastNode.next=lastNode.next.next;
}
else
{
lastNode=lastNode.next;
}
}
return head;
};
第二种方法就是我们之前说的，加个头节点，这样，我们就不需要再去单独考虑头节点的删除问题。
var removeElements = function(head, val) {
//将头节点放入链表中
var new_head=new ListNode(0);
new_head.next=head;
var listNode;
listNode=new_head;
while(listNode!=null)
{
if(listNode.next.val===val)
{
listNode.next=listNode.next.next;
}
else
{
listNode=listNode.next;
}
}
return new_head.next;
}
网友评论