JavaScript数据结构之链表怎么应用
本篇内容介绍了“JavaScript数据结构之链表怎么应用”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
创新互联公司网站建设服务商,为中小企业提供成都做网站、网站设计服务,网站设计,绵阳服务器托管等一站式综合服务型公司,专业打造企业形象网站,让您在众多竞争对手中脱颖而出创新互联公司。
链表的概念
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量,以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方法。通过前面元素插入的演示可以看出,实现插入简单四步:
1、创建结点
2、找到目标结点
3、修改目标结点的next指向链接
4、将目标结点的next值赋值给要插入的结点的next
function insert(newElement,item){ var newNode = new Node(newElement); var currentNode = this.find(item); newNode.next = currentNode.next; currentNode.next = newNode; }
Remove()方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法frontNode():
function frontNode(item){ var currentNode = this.head; while(currentNode.next.element!=item&¤tNode.next!=null){ currentNode = currentNode.next; } return currentNode; }
简答三步:
1、创建结点
2、找到目标结点的前结点
3、修改前结点的next指向被删除结点的n后一个结点
function remove(item){ var frontNode = this.frontNode(item); //console.log(frontNode.element); frontNode.next = frontNode.next.next; }
Show()方法:
function show(){ var currentNode = this.head,result; while(currentNode.next!=null){ result += currentNode.next.element;//为了不显示head结点 currentNode = currentNode.next; } }
测试程序:
var list = new LinkedList(); list.insert("a","head"); list.insert("b","a"); list.insert("c","b"); console.log(list.show()); list.remove("b"); console.log(list.show());
输出:
双向链表
从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。
首先我们先给Node类增加front属性:
function Node(element){ this.element = element; this.next = null; this.front = null; }
当然,对应的insert()方法和remove()方法我们也需要做相应的修改:
function insert(newElement,item){ var newNode = new Node(newElement); var currentNode = this.find(item); newNode.next = currentNode.next; newNode.front = currentNode;//增加front指向前驱结点 currentNode.next = newNode; } function remove(item){ var currentNode = this.find(item);//找到需要删除的节点 if (currentNode.next != null) { currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点 currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点 currentNode.next = null;//并设置前驱与后继的指向为空 currentNode.front = null; } }
反序显示链表:
需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。
function findLast() {//查找链表的最后一个节点 var currentNode = this.head; while (currentNode.next != null) { currentNode = currentNode.next; } return currentNode; }
实现反序输出:
function showReverse() { var currentNode = this.head, result = ""; currentNode = this.findLast(); while(currentNode.front!=null){ result += currentNode.element + " "; currentNode = currentNode.front; } return result; }
测试程序:
var list = new LinkedList(); list.insert("a","head"); list.insert("b","a"); list.insert("c","b"); console.log(list); list.remove("b"); console.log(list.show()); console.log(list.showReverse());
输出:
循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:
head.next = head
这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。
修改构造方法:
function LinkedList(){ this.head = new Node('head');//初始化 this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表 this.find = find; this.frontNode = frontNode; this.insert = insert; this.remove = remove; this.show = show; }
这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。
function find(item){ var currentNode = this.head;//从头结点开始 while(currentNode.element!=item&¤tNode.next.element!='head'){ currentNode = currentNode.next; } return currentNode;//找到返回结点数据,没找到返回null } function show(){ var currentNode = this.head,result = ""; while (currentNode.next != null && currentNode.next.element != "head") { result += currentNode.next.element + " "; currentNode = currentNode.next; } return result; }
测试程序:
var list = new LinkedList(); list.insert("a","head"); list.insert("b","a"); list.insert("c","b"); console.log(list.show()); list.remove("b"); console.log(list.show());
测试结果:
“JavaScript数据结构之链表怎么应用”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
当前题目:JavaScript数据结构之链表怎么应用
新闻来源:http://scyanting.com/article/psegie.html