前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在 javascript 中使用 spit() 方法不需要访问其他元素。如果你在使用数组的时候发现很慢,就可以考虑使用链表。
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个 "头指针" 变量,以 head 表示,它存放一个地址,指向一个元素。每个结点都使用一个对象的引用指标它的后继,指向另一个结点的引用叫做链。
数组元素依靠下标(位置)来进行引用,而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高,下图演示了链表结点 d 的插入过程:
删除过程:
我们定义 2 个类,Node 类与 LinkedList 类,Node 为结点数据,LinkedList 保存操作链表的方法。
首先看 Node 类:
- 1
- function Node(element) {
- 2 this.element = element;
- 3 this.next = null;
- 4
- }
element 用来保存结点上的数据,next 用来保存指向一下结点的的链接。
LinkedList 类:
- 1 function LinkedList(){
- 2
- 3 this.head = new Node('head');
- 4
- 5 this.find = find;
- 6
- 7 this.insert = insert;
- 8
- 9 this.remove = remove;
- 10
- 11 this.show = show;
- 12
- 13 }
find() 方法,从头结点开始,沿着链表结点一直查找,直到找到与 item 内容相等的 element 则返回该结点,没找到则返回空。
- 1
- function find(item) {
- 2
- var currentNode = this.head; //从头结点开始
- 3
- while (currentNode.element != item) {
- 4 currentNode = currentNode.next;
- 5
- }
- 6
- return currentNode; //找到返回结点数据,没找到返回null
- 7
- }
Insert 方法。通过前面元素插入的演示可以看出,实现插入简单四步:
1、创建结点
2、找到目标结点
3、修改目标结点的 next 指向链接
4、将目标结点的 next 值赋值给要插入的结点的 next
- 1
- function insert(newElement, item) {
- 2
- var newNode = new Node(newElement);
- 3
- var currentNode = this.find(item);
- 4 newNode.next = currentNode.next;
- 5 currentNode.next = newNode;
- 6
- }
Remove() 方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法 frontNode():
- 1
- function frontNode(item) {
- 2
- var currentNode = this.head;
- 3
- while (currentNode.next.element != item & ¤tNode.next != null) {
- 4 currentNode = currentNode.next;
- 5
- }
- 6
- return currentNode;
- 7
- }
简答三步:
1、创建结点
2、找到目标结点的前结点
3、修改前结点的 next 指向被删除结点的 n 后一个结点
- 1
- function remove(item) {
- 2
- var frontNode = this.frontNode(item);
- 3 //console.log(frontNode.element);
- 4 frontNode.next = frontNode.next.next;
- 5
- }
Show() 方法:
- 1
- function show() {
- 2
- var currentNode = this.head,
- result;
- 3
- while (currentNode.next != null) {
- 4 result += currentNode.next.element; //为了不显示head结点
- 5 currentNode = currentNode.next;
- 6
- }
- 7
- }
测试程序:
- 1
- var list = new LinkedList();
- 2 list.insert("a", "head");
- 3 list.insert("b", "a");
- 4 list.insert("c", "b");
- 5 console.log(list.show());
- 6 list.remove("b");
- 7 console.log(list.show());
输出:
从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。
首先我们先给 Node 类增加 front 属性:
- 1
- function Node(element) {
- 2 this.element = element;
- 3 this.next = null;
- 4 this.front = null;
- 5
- }
当然,对应的 insert() 方法和 remove() 方法我们也需要做相应的修改:
- 1
- function insert(newElement, item) {
- 2
- var newNode = new Node(newElement);
- 3
- var currentNode = this.find(item);
- 4 newNode.next = currentNode.next;
- 5 newNode.front = currentNode; //增加front指向前驱结点
- 6 currentNode.next = newNode;
- 7
- }
- 8 9 10
- function remove(item) {
- 11
- var currentNode = this.find(item); //找到需要删除的节点
- 12
- if (currentNode.next != null) {
- 13 currentNode.front.next = currentNode.next; //让前驱节点指向需要删除的节点的下一个节点
- 14 currentNode.next.front = currentNode.front; //让后继节点指向需要删除的节点的上一个节点
- 15 currentNode.next = null; //并设置前驱与后继的指向为空
- 16 currentNode.front = null;
- 17
- }
- 18
- }
反序显示链表:
需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。
- 1
- function findLast() { //查找链表的最后一个节点
- 2
- var currentNode = this.head;
- 3
- while (currentNode.next != null) {
- 4 currentNode = currentNode.next;
- 5
- }
- 6
- return currentNode;
- 7
- }
实现反序输出:
- 1
- function showReverse() {
- 2
- var currentNode = this.head,
- result = "";
- 3 currentNode = this.findLast();
- 4
- while (currentNode.front != null) {
- 5 result += currentNode.element + " ";
- 6 currentNode = currentNode.front;
- 7
- }
- 8
- return result;
- 9
- }
测试程序:
- 1
- var list = new LinkedList();
- 2 list.insert("a", "head");
- 3 list.insert("b", "a");
- 4 list.insert("c", "b");
- 5 console.log(list);
- 6 list.remove("b");
- 7 console.log(list.show());
- 8 console.log(list.showReverse());
输出:
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的域指向,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:
- 1 head.next = head
这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表:
修改构造方法:
- 1
- function LinkedList() {
- 2 this.head = new Node('head'); //初始化
- 3 this.head.next = this.head; //直接将头节点的next指向头节点形成循环链表
- 4 this.find = find;
- 5 this.frontNode = frontNode;
- 6 this.insert = insert;
- 7 this.remove = remove;
- 8 this.show = show;
- 9
- }
这时需要注意链表的输出方法 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());
测试结果:
本文用到的示例代码地址:
来源: http://www.cnblogs.com/qq503665965/p/6576576.html