Javascript中有哪些常見(jiàn)的數據結構

本篇文章為大家展示了Javascript中有哪些常見(jiàn)的數據結構，內容簡(jiǎn)明扼要并且容易理解，絕對能使你眼前一亮，通過(guò)這篇文章的詳細介紹希望你能有所收獲。

1.Stack(棧)

堆棧遵循LIFO(后進(jìn)先出)的原則。如果你把書(shū)堆疊起來(lái)，上面的書(shū)會(huì )比下面的書(shū)先拿?；蛘弋斈阍诰W(wǎng)上瀏覽時(shí)，后退按鈕會(huì )引導你到最近瀏覽的頁(yè)面。

Stack具有以下常見(jiàn)方法：

• push：輸入一個(gè)新元素

• pop：刪除頂部元素，返回刪除的元素

• peek：返回頂部元素

• length：返回堆棧中元素的數量

Javascript中的數組具有Stack的屬性，但是我們使用 function Stack() 從頭開(kāi)始構建Stack

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與Stack類(lèi)似。唯一不同的是，Queue使用的是FIFO原則(先進(jìn)先出)。換句話(huà)說(shuō)，當你排隊等候公交車(chē)時(shí)，隊列中的第一個(gè)總是先上車(chē)。

隊列具有以下方法：

• enqueue：輸入隊列，在最后添加一個(gè)元素

• dequeue：離開(kāi)隊列，刪除前元素并返回

• front：得到第一個(gè)元素

• isEmpty：確定隊列是否為空

• size：獲取隊列中元素的數量

JavaScript中的數組具有Queue的某些屬性，因此我們可以使用數組來(lái)構造Queue的示例：

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;   } }

優(yōu)先隊列

隊列還有另一個(gè)高級版本。為每個(gè)元素分配優(yōu)先級，并將根據優(yōu)先級對它們進(jìn)行排序：

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(鏈表)

從字面上看，鏈表是一個(gè)鏈式數據結構，每個(gè)節點(diǎn)由兩個(gè)信息組成：節點(diǎn)的數據和指向下一個(gè)節點(diǎn)的指針。鏈表和傳統數組都是線(xiàn)性數據結構，具有序列化的存儲方式。當然，它們也有差異：

單邊鏈表通常具有以下方法：

• size：返回節點(diǎn)數

• head：返回頭部的元素

• add：在尾部添加另一個(gè)節點(diǎn)

• remove：刪除某些節點(diǎn)

• indexOf：返回節點(diǎn)的索引

• elementAt：返回索引的節點(diǎn)

• addAt：在特定索引處插入節點(diǎn)

• removeAt：刪除特定索引處的節點(diǎn)

/** 鏈表中的節點(diǎn) **/ function Node(element) {     // 節點(diǎn)中的數據     this.element = element;     // 指向下一個(gè)節點(diǎn)的指針     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(集合)

集合是數學(xué)的基本概念：定義明確且不同的對象的集合。ES6引入了集合的概念，它與數組有一定程度的相似性。但是，集合不允許重復元素，也不會(huì )被索引。

一個(gè)典型的集合具有以下方法：

• values：返回集合中的所有元素

• size：返回元素個(gè)數

• has：確定元素是否存在

• add：將元素插入集合

• remove：從集合中刪除元素

• union：返回兩組交集

• difference：返回兩組的差

• subset：確定某個(gè)集合是否是另一個(gè)集合的子集

為了區分ES6中的 set，我們在以下示例中聲明為 MySet：

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. Hast table(哈希表)

哈希表是一種鍵值數據結構。由于通過(guò)鍵值查詢(xún)的速度快如閃電，所以常用于Map、Dictionary或Object數據結構中。如上圖所示，哈希表使用哈希函數(hash  function)將鍵轉換為數字列表，這些數字作為對應鍵的值。要快速使用鍵獲取價(jià)值，時(shí)間復雜度可以達到O(1)。相同的鍵必須返回相同的值——這是哈希函數的基礎。

哈希表具有以下方法：

• add：添加鍵值對

• remove：刪除鍵值對

• lookup：使用鍵查找對應的值

一個(gè)Javascript中簡(jiǎn)化的哈希表的例子：

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(樹(shù))

Tree(樹(shù))數據結構是多層結構。與Array，Stack和Queue相比，它也是一種非線(xiàn)性數據結構。這種結構在插入和搜索操作時(shí)效率很高。我們來(lái)看看樹(shù)型數據結構的一些概念。

• root：樹(shù)的根節點(diǎn)，無(wú)父節點(diǎn)

• parent node：上層的直接節點(diǎn)，只有一個(gè)

• child node：下層的直接節點(diǎn)可以有多個(gè)

• siblings：共享同一個(gè)父節點(diǎn)

• leaf：沒(méi)有孩子的節點(diǎn)

• Edge：節點(diǎn)之間的分支或鏈接

• path：從起始節點(diǎn)到目標節點(diǎn)的邊

• Height of Nod：特定節點(diǎn)到葉節點(diǎn)的最長(cháng)路徑的邊數

• Height of Tree：根節點(diǎn)到葉節點(diǎn)的最長(cháng)路徑的邊數

• Depth of Node：從根節點(diǎn)到特定節點(diǎn)的邊數

• Degree of Node：子節點(diǎn)數

這里以二叉樹(shù)為例。每個(gè)節點(diǎn)最多有兩個(gè)節點(diǎn)，左邊節點(diǎn)比當前節點(diǎn)小，右邊節點(diǎn)比當前節點(diǎn)大。

二叉樹(shù)中的常用方法：

• add：將節點(diǎn)插入樹(shù)

• findMin：獲取最小節點(diǎn)

• findMax：獲取最大節點(diǎn)

• find：搜索特定節點(diǎn)

• isPresent：確定某個(gè)節點(diǎn)的存在

• remove：從樹(shù)中刪除節點(diǎn)

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) {         // no child node         if (node.left == null && node.right == null) {           return null;         }         // no left node         if (node.left == null) {           return node.right;         }         // no right node         if (node.right == null) {           return node.left;         }         // has 2 child nodes         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 (發(fā)音為 “try”)

Trie或“前綴樹(shù)”也是搜索樹(shù)的一種。Trie分步存儲數據——樹(shù)中的每個(gè)節點(diǎn)代表一個(gè)步驟。Trie是用來(lái)存儲詞匯的，所以它可以快速搜索，特別是自動(dòng)完成功能。

Trie中的每個(gè)節點(diǎn)都有一個(gè)字母——分支之后可以組成一個(gè)完整的單詞。它還包括一個(gè)布爾指示符，以顯示這是否是最后一個(gè)字母。

Trie具有以下方法：

• add：在字典樹(shù)中插入一個(gè)單詞

• isWord：確定樹(shù)是否由某些單詞組成

• print：返回樹(shù)中的所有單詞

/** Node in 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(圖)

Graph(有時(shí)稱(chēng)為網(wǎng)絡(luò ))是指具有鏈接(或邊)的節點(diǎn)集。根據聯(lián)系是否有方向性，可以進(jìn)一步分為兩組(即定向圖和不定向圖)。Graph在我們的生活中被廣泛使用——在導航應用中計算最佳路線(xiàn)，或者在社交媒體中推薦朋友，舉兩個(gè)例子。

圖有兩種表示形式：

鄰接清單

在此方法中，我們在左側列出所有可能的節點(diǎn)，并在右側顯示已連接的節點(diǎn)。

鄰接矩陣

相鄰矩陣以行和列的形式顯示節點(diǎn)，行和列的交點(diǎn)詮釋了節點(diǎn)之間的關(guān)系，0表示沒(méi)有聯(lián)系，1表示有聯(lián)系，>1表示權重不同。

要查詢(xún)圖中的節點(diǎn)，必須用 “寬度優(yōu)先搜索"(BFS)方法或 "深度優(yōu)先搜索"(DFS)方法在整個(gè)樹(shù)網(wǎng)中進(jìn)行搜索。

讓我們看一個(gè)例子的BFS在Javascript：

function bfs(graph, root) {   var nodesLen = {};   for (var i = 0; i < graph.length; i++) {     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; j++) {       if (nodesLen[neighborIdx[j]] == Infinity) {         nodesLen[neighborIdx[j]] = nodesLen[current] + 1;         queue.push(neighborIdx[j]);       }     }   }   return nodesLen; }

測試一下：

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));  // 結果 {   0: 2,   1: 0,   2: 1,   3: 3,   4: Infinity }