Shulou(Shulou.com)06/02 Report--

This article mainly explains "what is the implementation of common data structures in Javascript". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn what is the implementation of common data structures in Javascript.

1. Stack (stack)

Stack is characterized by last-in first-out (last in first out). Common examples of Stack in life, such as a pile of books, you will take away the last one you put on it, or the browser's access history. When you click the back button, the last website you visit is the first to pop up from the history.

Stack generally has the following methods:

Push: push an element to the top of the stack

Pop: removes the top element of the stack and returns the removed element

Peek: returns the top element of the stack

Length: returns the number of elements in the stack

Javascript's Array is born with the features of Stack, but we can also implement a Stack class from scratch:

Function Stack () {this.count = 0; this.storage = {}; this.push = function (value) {this.storage [this.count] = value; this.count++;} this.pop = function () {if (this.count = 0) {return undefined;} this.count--; var result = this.storage [this.count]; delete this.storage [this.count]; return result } this.peek = function () {return this.storage [this.count-1];} this.size = function () {return this.count;}}

2. Queue (queue)

Queue and Stack have some similarities, except that Stack is first-in, first-out, while Queue is first-in, first-out. Examples of Queue in life, such as waiting in line to get on the bus, are always the first to get on the bus; another example is the printer's print queue, which prints first.

Queue generally has the following common methods:

Enqueue: queue, adding an element to the end of the queue

Dequeue: dequeue, remove an element from the queue header and return the removed element

Front: get the first element of the queue

IsEmpty: determines whether the queue is empty

Size: gets the number of elements in the queue

Array in Javascript already has some of the features of Queue, so we can implement a Queue type with Array:

Function Queue () {var collection = []; this.print = function () {console.log (collection);} this.enqueue = function (element) {collection.push (element);} this.dequeue = function () {return collection.shift ();} this.front = function () {return collection [0];} this.isEmpty = function () {return collection.length = 0 } this.size = function () {return collection.length;}}

Priority Queue (priority queue)

There is also an upgraded version of Queue that gives priority to each element, and the high-priority elements are listed before the low-priority elements. The main difference is the implementation of the enqueue method:

Function PriorityQueue () {... This.enqueue = function (element) {if (this.isEmpty ()) {collection.push (element);} else {var added = false; for (var I = 0; I

< collection.length; i++) { if (element[1] < collection[i][1]) { collection.splice(i, 0, element); added = true; break; } } if (!added) { collection.push(element); } } } } 测试一下： var pQ = new PriorityQueue(); pQ.enqueue(['gannicus', 3]); pQ.enqueue(['spartacus', 1]); pQ.enqueue(['crixus', 2]); pQ.enqueue(['oenomaus', 4]); pQ.print(); 结果： [ [ 'spartacus', 1 ], [ 'crixus', 2 ], [ 'gannicus', 3 ], [ 'oenomaus', 4 ] ] 3. Linked List(链表) 顾名思义，链表是一种链式数据结构，链上的每个节点包含两种信息：节点本身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构，存储的都是一个序列的数据，但也有很多区别，如下表： 一个单向链表通常具有以下方法： size：返回链表中节点的个数 head：返回链表中的头部元素 add：向链表尾部增加一个节点 remove：删除某个节点 indexOf：返回某个节点的index elementAt：返回某个index处的节点 addAt：在某个index处插入一个节点 removeAt：删除某个index处的节点 单向链表的Javascript实现： /** * 链表中的节点 */ function Node(element) { // 节点中的数据 this.element = element; // 指向下一个节点的指针 this.next = null; } function LinkedList() { var length = 0; var head = null; this.size = function () { return length; } this.head = function () { return head; } this.add = function (element) { var node = new Node(element); if (head == null) { head = node; } else { var currentNode = head; while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; } length++; } this.remove = function (element) { var currentNode = head; var previousNode; if (currentNode.element === element) { head = currentNode.next; } else { while (currentNode.element !== element) { previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; } this.isEmpty = function () { return length === 0; } this.indexOf = function (element) { var currentNode = head; var index = -1; while (currentNode) { index++; if (currentNode.element === element) { return index; } currentNode = currentNode.next; } return -1; } this.elementAt = function (index) { var currentNode = head; var count = 0; while (count < index) { count++; currentNode = currentNode.next; } return currentNode.element; } this.addAt = function (index, element) { var node = new Node(element); var currentNode = head; var previousNode; var currentIndex = 0; if (index >

Length) {return false;} if (index = 0) {node.next = currentNode; head = node;} else {while (currentIndex)

< index) { currentIndex++; previousNode = currentNode; currentNode = currentNode.next; } node.next = currentNode; previousNode.next = node; } length++; } this.removeAt = function (index) { var currentNode = head; var previousNode; var currentIndex = 0; if (index < 0 || index >

= length) {return null;} if (index = 0) {head = currentIndex.next;} else {while (currentIndex)

< index) { currentIndex++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; return currentNode.element; } } 4. Set(集合)

Set is a basic concept in mathematics, which represents the collective of objects with certain characteristics. It is also introduced in ES6 that the set types Set,Set and Array are similar to each other to a certain extent, except that duplicate elements are not allowed in Set and are unordered.

A typical Set should have the following methods:

Values: returns all elements in the collection

Size: returns the number of elements in the collection

Has: determines whether an element exists in the collection

Add: adding elements to the collection

Remove: removes an element from the collection

Union: returns the union of two sets

Intersection: returns the intersection of two sets

Difference: returns the difference between two sets

Subset: determines whether a set is a subset of another set

Using Javascript, you can implement Set as follows, which is named MySet in order to distinguish it from the Set in ES6:

Function MySet () {var collection = []; this.has = function (element) {return (collection.indexOf (element)! =-1);} this.values = function () {return collection;} this.size = function () {return collection.length;} this.add = function (element) {if (! this.has (element)) {collection.push (element); return true } return false;} this.remove = function (element) {if (this.has (element)) {index = collection.indexOf (element); collection.splice (index, 1); return true;} return false;} this.union = function (otherSet) {var unionSet = new MySet (); var firstSet = this.values (); var secondSet = otherSet.values () FirstSet.forEach (function (e) {unionSet.add (e);}); secondSet.forEach (function (e) {unionSet.add (e);}); return unionSet;} this.intersection = function (otherSet) {var intersectionSet = new MySet (); var firstSet = this.values () FirstSet.forEach (function (e) {if (otherSet.has (e)) {intersectionSet.add (e);}}); return intersectionSet;} this.difference = function (otherSet) {var differenceSet = new MySet (); var firstSet = this.values (); firstSet.forEach (function (e) {if (! otherSet.has (e)) {differenceSet.add (e) }}); return differenceSet;} this.subset = function (otherSet) {var firstSet = this.values (); return firstSet.every (function (value) {return otherSet.has (value);});}}

5. Hash Table (hash table / hash table)

Hash Table is a data structure used to store key-value pairs (key value pair). Because Hash Table queries value based on key very fast, it is often used to implement Map, Dictinary, Object and other data structures. As shown in the figure above, Hash Table internally uses a hash function to convert the incoming key into a string of numbers, and this string of numbers will be used as the actual key of the key value pair. The corresponding value through this key query is very fast, and the time complexity will reach O (1). The Hash function requires that the output corresponding to the same input must be equal, while the output corresponding to different input must be different, which is equivalent to a unique fingerprint on each pair of data.

A Hash Table usually has the following methods:

Add: add a set of key-value pairs

Remove: deletes a set of key-value pairs

Lookup: find the value corresponding to a key

A Javascript implementation of a simple version of Hash Table:

Function hash (string, max) {var hash = 0; for (var I = 0; I

< string.length; i++) { hash += string.charCodeAt(i); } return hash % max; } function HashTable() { let storage = []; const storageLimit = 4; this.add = function (key, value) { var index = hash(key, storageLimit); if (storage[index] === undefined) { storage[index] = [ [key, value] ]; } else { var inserted = false; for (var i = 0; i < storage[index].length; i++) { if (storage[index][i][0] === key) { storage[index][i][1] = value; inserted = true; } } if (inserted === false) { storage[index].push([key, value]); } } } this.remove = function (key) { var index = hash(key, storageLimit); if (storage[index].length === 1 && storage[index][0][0] === key) { delete storage[index]; } else { for (var i = 0; i < storage[index]; i++) { if (storage[index][i][0] === key) { delete storage[index][i]; } } } } this.lookup = function (key) { var index = hash(key, storageLimit); if (storage[index] === undefined) { return undefined; } else { for (var i = 0; i < storage[index].length; i++) { if (storage[index][i][0] === key) { return storage[index][i][1]; } } } } } 6. Tree(树) 顾名思义，Tree的数据结构和自然界中的树极其相似，有根、树枝、叶子，如上图所示。Tree是一种多层数据结构，与Array、Stack、Queue相比是一种非线性的数据结构，在进行插入和搜索操作时很高效。在描述一个Tree时经常会用到下列概念： Root(根)：代表树的根节点，根节点没有父节点 Parent Node(父节点)：一个节点的直接上级节点，只有一个 Child Node(子节点)：一个节点的直接下级节点，可能有多个 Siblings(兄弟节点)：具有相同父节点的节点 Leaf(叶节点)：没有子节点的节点 Edge(边)：两个节点之间的连接线 Path(路径)：从源节点到目标节点的连续边 Height of Node(节点的高度)：表示节点与叶节点之间的最长路径上边的个数 Height of Tree(树的高度)：即根节点的高度 Depth of Node(节点的深度)：表示从根节点到该节点的边的个数 Degree of Node(节点的度)：表示子节点的个数 我们以二叉查找树为例，展示树在Javascript中的实现。在二叉查找树中，即每个节点最多只有两个子节点，而左侧子节点小于当前节点，而右侧子节点大于当前节点，如图所示： 一个二叉查找树应该具有以下常用方法： add：向树中插入一个节点 findMin：查找树中最小的节点 findMax：查找树中最大的节点 find：查找树中的某个节点 isPresent：判断某个节点在树中是否存在 remove：移除树中的某个节点 以下是二叉查找树的Javascript实现： class Node { constructor(data, left = null, right = null) { this.data = data; this.left = left; this.right = right; } } class BST { constructor() { this.root = null; } add(data) { const node = this.root; if (node === null) { this.root = new Node(data); return; } else { const searchTree = function (node) { if (data < node.data) { if (node.left === null) { node.left = new Node(data); return; } else if (node.left !== null) { return searchTree(node.left); } } else if (data >

Node.data) {if (node.right = = null) {node.right = new Node (data); return;} else if (node.right! = = null) {return searchTree (node.right);}} else {return null;}}; return searchTree (node) }} findMin () {let current = this.root; while (current.left! = = null) {current = current.left;} return current.data;} findMax () {let current = this.root; while (current.right! = = null) {current = current.right;} return current.data;} find (data) {let current = this.root While (current.data! = = data) {if (data)

< current.data) { current = current.left } else { current = current.right; } if (current === null) { return null; } } return current; } isPresent(data) { let current = this.root; while (current) { if (data === current.data) { return true; } if (data < current.data) { current = current.left; } else { current = current.right; } } return false; } remove(data) { const removeNode = function (node, data) { if (node == null) { return null; } if (data == node.data) { // node没有子节点 if (node.left == null && node.right == null) { return null; } // node没有左侧子节点 if (node.left == null) { return node.right; } // node没有右侧子节点 if (node.right == null) { return node.left; } // node有两个子节点 var tempNode = node.right; while (tempNode.left !== null) { tempNode = tempNode.left; } node.data = tempNode.data; node.right = removeNode(node.right, tempNode.data); return node; } else if (data < node.data) { node.left = removeNode(node.left, data); return node; } else { node.right = removeNode(node.right, data); return node; } } this.root = removeNode(this.root, data); } } 测试一下： const bst = new BST(); bst.add(4); bst.add(2); bst.add(6); bst.add(1); bst.add(3); bst.add(5); bst.add(7); bst.remove(4); console.log(bst.findMin()); console.log(bst.findMax()); bst.remove(7); console.log(bst.findMax()); console.log(bst.isPresent(4)); 打印结果： 1 7 6 false 7. Trie(字典树，读音同try) Trie也可以叫做Prefix Tree(前缀树)，也是一种搜索树。Trie分步骤存储数据，树中的每个节点代表一个步骤，trie常用于存储单词以便快速查找，比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母，跟着树的分支可以可以拼写出一个完整的单词，每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。 Trie一般有以下方法： add：向字典树中增加一个单词 isWord：判断字典树中是否包含某个单词 print：返回字典树中的所有单词 /** * Trie的节点 */ function Node() { this.keys = new Map(); this.end = false; this.setEnd = function () { this.end = true; }; this.isEnd = function () { return this.end; } } function Trie() { this.root = new Node(); this.add = function (input, node = this.root) { if (input.length === 0) { node.setEnd(); return; } else if (!node.keys.has(input[0])) { node.keys.set(input[0], new Node()); return this.add(input.substr(1), node.keys.get(input[0])); } else { return this.add(input.substr(1), node.keys.get(input[0])); } } this.isWord = function (word) { let node = this.root; while (word.length >

1) {if (! node.keys.has (word [0])) {return false;} else {node = node.keys.get (word [0]); word = word.substr (1);}} return (node.keys.has (word) & & node.keys.get (word). IsEnd ())? True: false;} this.print = function () {let words = new Array (); let search = function (node = this.root, string) {if (node.keys.size! = 0) {for (let letter of node.keys.keys ()) {search (node.keys.get (letter), string.concat (letter)) } if (node.isEnd ()) {words.push (string);}} else {string.length > 0? Words.push (string): undefined; return;}}; search (this.root, new String ()); return words.length > 0? Words: null;}}

8. Graph (figure)

A Graph is a collection of nodes (or vertices) and the connections (or edges) between them. Graph can also be called Network (network). According to whether the connection between nodes has direction or not, it can be divided into Directed Graph (directed graph) and Undrected Graph (undirected graph). Graph has many uses in real life, such as navigation software to calculate the best path, social software to recommend friends, and so on.

Graph is usually expressed in two ways:

Adjaceny List (adjacency list):

The adjacency list can be represented as a list of nodes on the left and a list of all other nodes to which it is connected on the right.

And Adjacency Matrix (adjacency matrix):

The adjacency matrix uses a matrix to represent the connection between nodes, each row or column represents a node, and the number at the intersection of rows and columns indicates the relationship between nodes: 0 indicates no connection, 1 indicates there is a connection, and more than 1 indicates different weights.

Access to nodes in Graph requires a traversal algorithm, which is divided into breadth-first and depth-first, which is mainly used to determine the distance between the target node and the root node.

In Javascript, Graph can be represented by a matrix (two-dimensional array), and the breadth-first search algorithm can be implemented as follows:

Function bfs (graph, root) {var nodesLen = {}; for (var I = 0; I < graph.length; iTunes +) {nodesLen [I] = Infinity;} nodesLen [root] = 0; var queue = [root]; var current; while (queue.length! = 0) {current = queue.shift (); var curConnected = graph [current]; var neighborIdx = []; var idx = curConnected.indexOf (1) While (idx! =-1) {neighborIdx.push (idx); idx = curConnected.indexOf (1, idx + 1);} for (var j = 0; j < neighborIdx.length; if +) {if (NodesLen [current]] = Infinity) {nodesLenn [current] + 1; queue.push (neighboridx [j]);}} return nodesLen;}

Test it:

Var graph = [0,1,1,1,0], [0,0,1,0,0], [1,1,0,0,0], [0,0,0,1,0], [0,1,0,0,0]; console.log (bfs (graph, 1))

Print:

{0: 2, 1: 0, 2: 1, 3: 3, 4: Infinity} Thank you for reading, the above is the content of "what is the implementation of common data structures in Javascript". After the study of this article, I believe you have a deeper understanding of what is the implementation of common data structures in Javascript, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.