怎么在JavaScript中利用线性表表示链式？很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素。所以，每一个数据元素除了存储自身的信息之外，还需要存储一个指向其后继的存储位置的信息。这两部分信息组成了元素的存储映像，称为结点。
结点包括两个域：数据域和指针域。
数据域是元素中存储数据元素的信息。
指针域是元素中存储的后继存储位置的信息。
n个结点链接成为链表，就是线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，所有又称为线性链表或单链表。
举一个例子
上图表示的线性表为
ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG
这样应该就好理解多了吧。
下面我们通过js代码来实现链表的插入和删除还有查找操作
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
var Node = function(newData){//创建节点对象
this.next = null;
this.data = null;
this.Init = function(){
this.data = newData;
};
this.Init();
}
//定义链表类
var List = function(){
this.head = null;
this.size = 0;
this.Init = function(){
this.head = null;
this.size = 0;
}
this.Init();
this.Insert = function(newData){//初始批量插入操作
this.size += 1;
var newNode = new Node(newData);
if(this.head == null){
this.head = newNode;
return;
}
var tempNode = this.head;
while(tempNode.next != null)
tempNode = tempNode.next;//找到链表尾部
tempNode.next = newNode;//将新元素插入到链表尾部
};
this.GetData = function(pos){//查找操作
if(pos >= this.size || pos < 0)
return null;
else{
tempNode = this.head;
for(i = 0;i < pos;i++)
tempNode = tempNode.next; //找到所处位置
return tempNode.data;
}
};
this.Remove = function(pos){//移除某一位置节点
if(pos >= this.size || pos < 0)
return null;
this.size -= 1;
tempNode = this.head;
if(pos == 0){
this.head = this.head.next;
return this.head;
}
for(i = 0;i < pos - 1;i++){
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
return tempNode.next;
};
this.InsertBefore=function(data,pos){//从某一位置前插入节点
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//将数据创造节点
if(pos==0){
newNode.next=tempNode;
return newNode.next;
}
for(i=0;i<pos-1;i++){
tempNode=tempNode.next;//找到插入的位置
}
newNode.next=tempNode.next;//插入操作
tempNode.next=newNode;
return newNode.next;
};
this.Print = function(){//输出
document.write("链表中元素: <br>");
tempNode = this.head;
while(tempNode != null){
document.write(tempNode.data + " ");
tempNode = tempNode.next;
}
document.write("<br>");
};
};
//运行测试:
var list = new List();
var array = new Array(1,2,3,4,5,6);
for(i = 0;i < array.length;i++){
list.Insert(array[i]);
}
list.Print();
document.write("查找操作下标为4的元素: <br>");
var data= list.GetData(4);
document.write(data+"<br>");
document.write("删除操作: <br>");
list.Remove(5);
list.Print();
document.write("插入操作: <br>");
list.InsertBefore(8,3);
list.Print();
document.write("链表大小: " + list.size);
</script>
</head>
<body>
</body>
</html>运行得到结果为
先分析一下插入和删除的代码。
this.InsertBefore=function(data,pos){//从某一位置前插入节点
if(pos>=this.size||pos<0)
return null;
this.size+=1;
tempNode=this.head;
var newNode = new Node(data);//将数据创造节点
if(pos==0){
newNode.next=tempNode;
return newNode.next;
}
for(i=0;i<pos-1;i++){
tempNode=tempNode.next;//找到插入的位置
}
newNode.next=tempNode.next;//插入操作
tempNode.next=newNode;
return newNode.next;
};
this.Remove = function(pos){//移除某一位置节点
if(pos >= this.size || pos < 0)
return null;
this.size -= 1;
tempNode = this.head;
if(pos == 0){
this.head = this.head.next;
return this.head;
}
for(i = 0;i < pos - 1;i++){
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
return tempNode.next;
};可以看出，插入和删除的世界复杂度都为o(n)。因为在第i个结点前插入或删除都得找到第i-1个元素。
再来看看初始化方法Insert，
this.Insert = function(newData){//初始批量插入操作
this.size+= 1;
var newNode = new Node(newData);
if(this.head == null){
this.head = newNode;
return;
}
var tempNode = this.head;
while(tempNode.next != null)
tempNode = tempNode.next;//找到链表尾部
tempNode.next= newNode;//将新元素插入到链表尾部
};初始的插入Insert方法的时间复杂度也是o(n)。
下面介绍一下另外一种形式的链式存储结构，就是循环链表。它的特点就表中的最后一个结点的指针域指向头结点，整个链表形成一个环。有时候，在循环链表中设立尾指针而不设立头指针，可以简化操作。比如两个线性表集合为一个表时，仅需将一个表的表尾和另一个表的表头相接。这个操作的时间复杂度是o(1)。
如下图所示
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
