JavaScript数据结构之链表的实现
83 浏览量
2020-12-08
17:47:22
上传
评论
收藏 99KB PDF 举报
JavaScript数据结构之链表的实现数据结构之链表的实现
前面楼主分别讨论了数据结构栈与队列的实现，当时所用的数据结构都是用的数组来进行实现，但是数组有的时候并不是最佳
的数据结构，比如在数组中新增删除元素的时候需要将其他元素进行移动，而在javascript中使用spit()方法不需要访问其他元
素。如果你在使用数组的时候发现很慢，就可以考虑使用链表。
链表的概念链表的概念
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量，以head表示，它存放一个地
址，指向一个元素。每个结点都使用一个对象的引用指标它的后继，指向另一个结点的引用叫做链。
数组元素依靠下标（位置）来进行引用，而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高，下图演示
了链表结点d的插入过程：
删除过程：
基于对象的链表基于对象的链表
我们定义2个类，Node类与LinkedList类，Node为结点数据，LinkedList保存操作链表的方法。
首先看Node类：
function Node(element){
this.element = element;
this.next = null;
}
element用来保存结点上的数据，next用来保存指向一下结点的的链接。
LinkedList类:
function LinkedList(){
this.head = new Node('head');
this.find = find;
this.insert = insert;
this.remove = remove;
this.show = show;
}
find()方法，从头结点开始，沿着链表结点一直查找，直到找到与item内容相等的element则返回该结点，没找到则返回空。
function find(item){
var currentNode = this.head;//从头结点开始
while(currentNode.element!=item){
currentNode = currentNode.next;
}
return currentNode;//找到返回结点数据，没找到返回null
}
Insert方法。通过前面元素插入的演示可以看出，实现插入简单四步：
资源评论
