LinkedList实现方式：
因为js没有LinkedList，以下是自己实现的LinkedList：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | function LinkedList() { var Node = function(element) { this.element = element; this.next = null; } var length = 0; var head = null; this.add = function(element) { var node = new Node(element),current; if (head==null) { head = node; } else { current = head; while(current.next) { current = current.next; } current.next = node; } length++; } this.set = function(index, element) { var a = this.get(index); a = element; } // 删除最顶端元素 this.remove = function() { if (this.isEmpty()) { return undefined; } var h = head.element; head = head.next; length --; return h; } this.isEmpty = function() { return length == 0; } this.get = function(index) { var num = 0, current; if (index < 0) throw new RangeError("Index out of range"); current = head; while(num++ < index) { current = current.next; } var a = current.element; return a; }}module.exports = LinkedList; |
以下是自己实现的队列queue类：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | function Queue() { var queue = {}; var count = 0; var lowCount = 0; // 入队 this.add = function(value) { queue[count++] = value; } // 出队 this.remove = function() { if (this.isEmpty()) { return undefined; } var result = queue[lowCount]; delete queue[lowCount]; lowCount++; return result; } this.isEmpty = function() { return this.size() == 0; } this.peek = function() { if (this.isEmpty()) { return null; } return queue[lowCount]; } this.clear = function() { count = 0; lowCount = 0; queue = {}; } this.size = function() { return count - lowCount; }}module.exports = Queue; |
以下是图的广度优先遍历方式：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | const LinkedList = require("../util/LinkedList");const Queue = require("../util/Queue");const Graph = require("../graph/Graph");function GraphBFS($g) { var G = $g, visited = new Array(G.V()).fill(false), queue = new LinkedList(), order = []; var bfs = function ($v) { visited[$v] = true; queue.add($v); while (!queue.isEmpty()) { var v = queue.remove(); order.push(v); for (var w of G.adj(v)) { if (!visited[w]) { queue.add(w); visited[w] = true; } } } } for (var v = 0; v < G.V(); v++) { if (!visited[v]) { bfs(v); } } this.order=function () { return order; }}var g = new Graph('data/图的BFS实现/g.txt');var graphBFS = new GraphBFS(g);console.log('图的广度优先遍历结果：', graphBFS.order()) |
上面GraphBFS中的queue不管是实现的Queue还是LinkedList都能实现图的广度优先遍历。从代码上看Queue的性能是优于LinkedList的，不知道老师为何在实现这个queue采用的是链表呢？还是因为JAVA中关于LinkedList是跟我这里是有本质区别的？
Java 中 Queue 是一个接口（而不是一个具体的数据结构。）开发者可以选择用链表实例化这个接口，也可以选择用动态数组实例化这个接口。对于小数据量，基本没有区别；对于大数据量，确实链表的性能是差的。
===========
但是我简单看了一下你的代码，你所看到的性能差距，大概率不是这两种数据结构在大规模数据下产生的性能差距。
对于 js，你这样手动写一个链表，效率肯定低于你手写的这个 queue。这是因为你手写的这个queue，本质是对 js 数组的一次在封装，背后的数据结构，本质使用的是数组；而你手写的这个链表，是真正的没有使用 js 的任何原生数据结构，从底层搭建了一个数据结构的增删改查和所有的内存的声明和销毁。
对于大多数脚本语言，前者一定远远快于后者。这是因为前者通常都是被类似 C/C++ 这样的语言在底层被实现优化出来的，而后者是你在上层实现出来的，运行时再被解释器解析，效率远远低于前者，即使是同样的复杂度。
这就是为什么，对于算法和数据结构的底层性能的考察，我是不建议使用脚本语言的。（当然，学习逻辑是没有问题的）。因为使用脚本语言，性能的优劣很有可能关键因素并非是算法，而是具体的实现。同样的算法思路，在脚本语言上，一个“好的实现”，很有可能是比“差的实现”快几十倍甚至上百倍的，而在大多数编译型语言中，通常是不会有这么大的性能差距的。而所谓的“好的实现”，在通常情况下，更多的是是否足够了解这个脚本语言提供的标准库，并且充分利用这个标准库。
继续加油！：）
登录后可查看更多问答，登录/注册
