用JS[经典数据结构]实现的线性表链式表示方法示例

本文通过一个实例描述了用JS实现的线性表的链式表示方法。分享给大家参考，如下：

从上一节可以看出，顺序存储结构的弱点是在插入或删除操作时需要移动大量的元素。因此，我们需要在这里介绍链式存储结构。因为它不要求逻辑上相邻的元素在物理位置上相邻，所以它没有顺序存储结构的弱点，但也没有顺序表可以随机访问的优点。

下面描述什么是链表。

线性表的链式存储结构使用一组任意的存储单元来存储线性表的数据元素。因此，每个数据元素不仅需要存储自己的信息，还需要存储指向其后续存储位置的信息。这两部分信息构成了元素的存储图像，称为节点。

节点包括两个字段：数据字段和指针字段。

数据字段是存储在元素中的数据元素的信息。

指针字段是存储在元素中的后续存储位置的信息。

n个节点链接成链表，是线性表的链式存储结构。因为这个链表中的每个节点只包含一个指针字段，所以所有节点也被称为线性链表或单链表。

举个例子。

上面显示的线性表是

赵、钱、孙、李、周、吴、郑、王

这应该更容易理解。

下面我们用js代码来实现链表的插入和删除以及搜索操作

！doctype html heartheta charset=' utf-8 '/script type=' text/JavaScript ' var node=function(新数据){//创建一个node对象this.next=nullthis.data=null这个。init=function(){ this . data=new DATa；};这个。init()；}//定义链表类varlist=function () {this。head=nullthis . size=0；这个。init=function(){ this . head=null；this . size=0；}这个。init()；这个。insert=function(new data){//初始大容量插入操作this . size=1；var newNode=new Node(新数据)；if(this . head==null){ this . head=new node；返回；} var tempNode=this.headwhile(tempNode.next！=null)TempNode=TempNode . next；//在链表末尾找到tempNode.next=newNode//将新元素插入链表尾部}；这个。GetData=function(pos){//搜索操作if (pos=this。size | | pos0)返回nullelse { tempNode=this.headfor(I=0；i posI)TempNode=TempNode . next；//查找位置返回tempNode.data} };这个。Remove=function(pos){//如果(pos=this)则移除位置节点。size | | pos0)返回nullthis . size-=1；tempNode=this.headif(pos==0){ this . head=this . head . next；把这个还给我。} for(I=0；I位置-1；I){ tempNode=tempNode . next；} TempNode . next=TempNode . next . next；返回tempNode.next};这个。insertbefore=函数(数据，位置){//插入节点if(位置=this。size | | pos0)并返回nullthis . size=1；tempNode=this.headvar newNode=new Node(数据)；//如果(pos==0) {newnode，则将数据创建到节点中。next=tempnode返回new node . next；} for(I=0；IPOs-1；I){ tempNode=tempNode . next；//找到插入位置} new node . next=tempnode . next；//插入操作tempNode.next=newNode返回new node . next；};这个。print=function(){//output document . write('链表中的元素： br ')；tempNode=this.headwhile(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.lengthi ){列表。插入(数组[I])；}列表。print()；Document.write('搜索操作中索引为4的元素： br ')；var数据=列表。GetData(4)；document.write(数据“br”)；Document.write('删除操作： br ')；名单。移除(5)；名单。print()；Document.write('插入操作： br ')；名单。InsertBefore(8，3)；名单。print()；Document.write('链接表大小： ' list . size)；运行/脚本/床头/正文/html，结果是

首先分析插入和删除的代码。

这个。insertbefore=函数(数据，位置){//插入节点if(位置=this。size | | pos0)并返回nullthis . size=1；tempNode=this.headvar newNode=new Node(数据)；//如果(pos==0) {newnode，则将数据创建到节点中。next=tempnode返回new node . next；} for(I=0；IPOs-1；I){ tempNode=tempNode . next；//找到插入位置} new node . next=tempnode . next；//插入操作tempNode.next=newNode返回new node . next；};这个。Remove=function(pos){//如果(pos=this)则移除位置节点。size | | pos0)返回nullthis . size-=1；tempNode=this.headif(pos==0){ this . head=this . head . next；把这个还给我。} for(I=0；I位置-1；I){ tempNode=tempNode . next；} TempNode . next=TempNode . next . next；返回tempNode.next};可见，插入和删除的世界复杂度为o(n)。因为必须在插入或删除第(I)个节点之前找到第(i-1)个元素。

让我们看看初始化方法Insert。

这个。insert=function(new data){//初始大容量插入操作this . size=1；var newNode=new Node(新数据)；if(this . head==null){ this . head=new node；返回；} var tempNode=this.headwhile(tempNode.next！=null)TempNode=TempNode . next；//在链表末尾找到tempNode.next=newNode//将新元素插入链表尾部}；初始插入方法的时间复杂度也是o(n)。

这是链式存储结构的另一种形式，即循环链表。其特点是表中最后一个节点的指针字段指向头节点，整个链表形成一个环。有时，在循环链表中设置尾指针而不是头指针可以简化操作。例如，当两个线性表被设置成一个表时，只需要将一个表的页脚与另一个表的页眉连接起来。这个操作的时间复杂度是o(1)。

如下图所示

上述链表只能通过某个节点找到以下节点。也就是说，在单个链表中，查找下一个节点的时间复杂度为o(1)，而查找上一个节点的时间复杂度为o(n)。为了克服单链表的单向性，可以使用双链表。

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》、0103010。

希望本文对JavaScript编程有所帮助。