數據結構和算法練習網站_視頻和練習介紹了10種常見數據結構

數據結構和算法練習網站

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds, creator of Linux

“糟糕的程序員擔心代碼。好的程序員擔心數據結構及其關系。” — Linux的創建者Linus Torvalds

**Update** My video course about Algorithms is now live! Check out Algorithms in Motion from Manning Publications. Get 39% off my course by using code ‘39carnes’! Or you can get 50% off my Deep Learning in Motion course with code ‘vlcarnes2’.
**更新** 我有關算法的視頻課程現已上線！ 從Manning出版物中檢驗運動中的算法。 使用代碼“ 39carnes ”可獲得39％的課程折扣！ 或者，您可以使用代碼“ vlcarnes2 ”獲得“ 深度學習運動”課程的 50％折扣。

Data structures are a critical part of software development, and one of the most common topics for developer job interview questions.

數據結構是軟件開發的關鍵部分，也是開發人員求職面試問題的最常見主題之一。

The good news is that they’re basically just specialized formats for organizing and storing data.

好消息是，它們基本上只是組織和存儲數據的專用格式。

I’m going to teach you 10 of the most common data structures — right here in this short article.

我將在這篇簡短的文章中教您10種最常見的數據結構。

I’ve embedded videos that I created for each of these data structures. I’ve also linked to code examples for each of them, which show how to implement these in JavaScript.

我已經嵌入了為每個數據結構創建的視頻。我還鏈接了每個示例的代碼示例，這些示例顯示了如何在JavaScript中實現這些示例。

And to give you some practice, I’ve linked to challenges from the freeCodeCamp curriculum.

為了給您一些實踐，我已經鏈接到freeCodeCamp課程的挑戰。

Note that some of these data structures include time complexity in Big O notation. This isn’t included for all of them since the time complexity is sometimes based on how it’s implemented. If you want to learn more about Big O Notation, check out my article about it or this video by Briana Marie.

請注意，其中一些數據結構在Big O表示法中包括時間復雜度。由于時間復雜度有時取決于實現方式，因此并非所有功能都包含此功能。如果您想了解更多有關Big O Notation的信息，請查看我的相關文章或Briana Marie的視頻。

Also note that even though I show how to implement these data structures in JavaScript, for most of them you would never need to implement them yourself, unless you were using a low-level language like C.

還要注意，即使我展示了如何在JavaScript中實現這些數據結構，對于大多數數據結構，您都不需要自己實現它們，除非您使用的是C之類的低級語言。

JavaScript (like most high-level languages) has built-in implementations of many of these data structures.

JavaScript(像大多數高級語言一樣)具有許多這些數據結構的內置實現。

Still, knowing how to implement these data structures will give you a huge edge in your developer job search, and may come in handy when you’re trying to write high-performance code.

不過，知道如何實現這些數據結構將為您在開發人員的工作搜索中提供巨大的優勢，并且在您嘗試編寫高性能代碼時可能會派上用場。

鏈表 (Linked Lists)

A linked list is one of the most basic data structures. It is often compared to an array since many other data structures can be implemented with either an array or a linked list. They each have advantages and disadvantages.

鏈表是最基本的數據結構之一。通常將其與數組進行比較，因為可以使用數組或鏈表實現許多其他數據結構。它們各有優缺點。

A linked list consists of a group of nodes which together represent a sequence. Each node contains two things: the actual data being stored (which can be basically any type of data) and a pointer (or link) to the next node in the sequence. There are also doubly linked lists where each node has a pointer to both the next item and the previous item in the list.

鏈表由一組節點組成，這些節點一起代表一個序列。每個節點包含兩件事：正在存儲的實際數據(基本上可以是任何類型的數據)和指向序列中下一個節點的指針(或鏈接)。還有雙向鏈接的列表，其中每個節點都有一個指向列表中的下一項和上一項的指針。

The most basic operations in a linked list are adding an item to the list, deleting an item from the list, and searching the list for an item.

鏈接列表中最基本的操作是將項目添加到列表，從列表中刪除項目以及在列表中搜索項目。

See the code for a linked list in JavaScript here.

在此處查看JavaScript中的鏈表的代碼。

鏈表時間復雜度 (Linked list time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(n)	0(n)
Insert	0(1)	0(1)
Delete	0(1)	0(1)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(n)	0(n)
插	0(1)	0(1)
刪除	0(1)	0(1)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Work with Nodes in a Linked List
處理鏈接列表中的節點
Create a Linked List Class
創建一個鏈接列表類
Remove Elements from a Linked List
從鏈接列表中刪除元素
Search within a Linked List
在鏈接列表中搜索
Remove Elements from a Linked List by Index
通過索引從鏈接列表中刪除元素
Add Elements at a Specific Index in a Linked List
在鏈接列表的特定索引處添加元素
Create a Doubly Linked List
創建一個雙向鏈接列表
Reverse a Doubly Linked List
反轉雙鏈表

堆棧 (Stacks)

A stack is a basic data structure where you can only insert or delete items at the top of the stack. It is kind of similar to a stack of books. If you want to look at a book in the middle of the stack you must take all of the books above it off first.

堆棧是一種基本的數據結構，您只能在其中插入或刪除堆棧頂部的項目。這有點像一堆書。如果要看書架中間的一本書，則必須先取走書架上方的所有書。

The stack is considered LIFO (Last In First Out) — meaning the last item you put in the stack is the first item that comes out of the stack

堆棧被認為是LIFO(后進先出)-意味著您放入堆棧中的最后一個項目是從堆棧中出來的第一個項目

There are three main operations that can be performed on stacks: inserting an item into a stack (called ‘push’), deleting an item from the stack (called ‘pop’), and displaying the contents of the stack (sometimes called ‘pip’).

可以在堆棧上執行三個主要操作：將項目插入堆棧(稱為“推”)，從堆棧中刪除項目(稱為“ pop”)以及顯示堆棧的內容(有時稱為“ pip”) ')。

See the code for a stack in JavaScript here.

在此處查看JavaScript中的堆棧代碼。

堆棧時間復雜度 (Stack time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(n)	0(n)
Insert	0(1)	0(1)
Delete	0(1)	0(1)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(n)	0(n)
插	0(1)	0(1)
刪除	0(1)	0(1)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Learn how a Stack Works
了解堆棧如何工作
Create a Stack Class
創建一個堆棧類

Queue列 (Queues)

You can think of a queue as a line of people at a grocery store. The first one in the line is the first one to be served. Just like a queue.

您可以將隊列視為雜貨店中的一排人。該行中的第一個是要投放的第一個。就像一個隊列。

A queue is considered FIFO (First In First Out) to demonstrate the way it accesses data. This means that once a new element is added, all elements that were added before have to be removed before the new element can be removed.

隊列被視為FIFO(先進先出)以演示其訪問數據的方式。這意味著一旦添加了新元素，則必須先刪除之前添加的所有元素，然后才能刪除新元素。

A queue has just two main operations: enqueue and dequeue. Enqueue means to insert an item into the back of the queue and dequeue means removing the front item.

隊列只有兩個主要操作：入隊和出隊。入隊意味著將項目插入隊列的后面，而出隊則意味著除去前項。

See the code for a queue in JavaScript here.

在此處查看JavaScript中的隊列代碼。

隊列時間復雜度 (Queue time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(n)	0(n)
Insert	0(1)	0(1)
Delete	0(1)	0(1)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(n)	0(n)
插	0(1)	0(1)
刪除	0(1)	0(1)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Create a Queue Class
創建一個隊列類
Create a Priority Queue Class
創建一個優先隊列類
Create a Circular Queue
創建循環隊列

套裝 (Sets)

The set data structure stores values without any particular order and with no repeated values. Besides being able to add and remove elements to a set, there are a few other important set functions that work with two sets at once.

設置的數據結構存儲的值沒有任何特定的順序，并且沒有重復的值。除了能夠向集合中添加和刪除元素外，還有一些其他重要的集合函數可以同時處理兩個集合。

Union — This combines all the items from two different sets and returns this as a new set (with no duplicates).
聯合—合并來自兩個不同集合的所有項目，并將其作為新集合返回(沒有重復項)。
Intersection — Given two sets, this function returns another set that has all items that are part of both sets.
交集-給定兩個集合，此函數將返回另一個集合，該集合具有兩個集合中的所有項。
Difference — This returns a list of items that are in one set but NOT in a different set.
差異—這將返回一組中的項目列表，但不在另一組中。
Subset — This returns a boolean value that shows if all the elements in one set are included in a different set.
子集-返回一個布爾值，該值顯示一個集中的所有元素是否包含在另一個集中。

View the code to implement a set in JavaScript here.

在此處查看代碼以在JavaScript中實現集合。

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Create a Set Class
創建一個集合類
Remove from a Set
從集合中刪除
Size of the Set
套裝的大小
Perform a Union on Two Sets
在兩個集合上執行并集
Perform an Intersection on Two Sets of Data
在兩組數據上執行交集
Perform a Difference on Two Sets of Data
對兩組數據執行差異
Perform a Subset Check on Two Sets of Data
對兩組數據執行子集檢查
Create and Add to Sets in ES6
在ES6中創建和添加到集合
Remove items from a set in ES6
從ES6中的集合中刪除項目
Use .has and .size on an ES6 Set
在ES6集上使用.has和.size
Use Spread and Notes for ES5 Set() Integration
使用Spread和Notes進行ES5 Set()集成

地圖 (Maps)

A map is a data structure that stores data in key / value pairs where every key is unique. A map is sometimes called an associative array or dictionary. It is often used for fast look-ups of data. Maps allow the following things:

映射是將數據存儲在鍵/值對中的數據結構，其中每個鍵都是唯一的。映射有時稱為關聯數組或字典。它通常用于快速查找數據。地圖允許以下內容：

the addition of a pair to the collection
在收藏中增加一對
the removal of a pair from the collection
從集合中刪除一對
the modification of an existing pair
現有對的修改
the lookup of a value associated with a particular key
與特定鍵關聯的值的查找

View the code to implement a map in JavaScript here.

在此處查看代碼以在JavaScript中實現地圖。

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Create a Map Data Structure
創建地圖數據結構
Create an ES6 JavaScript Map
創建一個ES6 JavaScript映射

哈希表 (Hash Tables)

A hash table is a map data structure that contains key / value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

哈希表是一種包含鍵/值對的地圖數據結構。它使用哈希函數來計算存儲桶或插槽數組的索引，從中可以找到所需的值。

The hash function usually takes a string as input and it outputs an numerical value. The hash function should always give the same output number for the same input. When two inputs hash to the same numerical output, this is called a collision. The goal is to have few collisions.

哈希函數通常將字符串作為輸入，并輸出一個數值。散列函數應始終為相同的輸入提供相同的輸出編號。當兩個輸入哈希到相同的數字輸出時，這稱為沖突。目標是幾乎沒有碰撞。

So when you input a key / value pair into a hash table, the key is run through the hash function and turned into a number. This numerical value is then used as the actual key that the value is stored by. When you try to access the same key again, the hashing function will process the key and return the same numerical result. The number will then be used to look up the associated value. This provides very efficient O(1) lookup time on average.

因此，當您在哈希表中輸入鍵/值對時，鍵將通過哈希函數運行并轉換為數字。然后將此數字值用作存儲該值的實際鍵。當您嘗試再次訪問相同的鍵時，哈希函數將處理該鍵并返回相同的數字結果。然后，該數字將用于查找關聯的值。平均而言，這提供了非常有效的O(1)查找時間。

View the code for a hash table here.

在此處查看哈希表的代碼。

哈希表時間復雜度 (Hash table time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(1)	0(n)
Insert	0(1)	0(n)
Delete	0(1)	0(n)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(1)	0(n)
插	0(1)	0(n)
刪除	0(1)	0(n)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Create a Hash Table
創建哈希表

二進制搜索樹 (Binary Search Tree)

A tree is a data structure composed of nodes It has the following characteristics:

樹是由節點組成的數據結構，具有以下特征：

Each tree has a root node (at the top).
每棵樹都有一個根節點(在頂部)。
The root node has zero or more child nodes.
根節點具有零個或多個子節點。
Each child node has zero or more child nodes, and so on.
每個子節點都有零個或多個子節點，依此類推。

A binary search tree adds these two characteristics:

二進制 搜索樹添加了以下兩個特征：

Each node has up to two children.
每個節點最多有兩個孩子。
For each node, its left descendents are less than the current node, which is less than the right descendents.
對于每個節點，其左后代小于當前節點，而當前節點小于右后代。

Binary search trees allow fast lookup, addition and removal of items. The way that they are set up means that, on average, each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree.

二進制搜索樹允許快速查找，添加和刪除項目。設置它們的方式意味著，平均而言，每個比較都允許操作跳過樹的大約一半，因此每次查找，插入或刪除所花的時間與樹中存儲的項目數的對數成正比。

View the code for a binary search tree in JavaScript here.

在此處查看JavaScript中的二進制搜索樹的代碼。

二進制搜索時間復雜度 (Binary search time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(log n)	0(n)
Insert	0(log n)	0(n)
Delete	0(log n)	0(n)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(log n)	0(n)
插	0(log n)	0(n)
刪除	0(log n)	0(n)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Find the Minimum and Maximum Value in a Binary Search Tree
在二分搜索樹中找到最小值和最大值
Add a New Element to a Binary Search Tree
向二進制搜索樹添加新元素
Check if an Element is Present in a Binary Search Tree
檢查二進制搜索樹中是否存在元素
Find the Minimum and Maximum Height of a Binary Search Tree
查找二叉搜索樹的最小和最大高度
Use Depth First Search in a Binary Search Tree
在二分搜索樹中使用深度優先搜索
Use Breadth First Search in a Binary Search Tree
在二分搜索樹中使用廣度優先搜索
Delete a Leaf Node in a Binary Search Tree
刪除二叉搜索樹中的葉節點
Delete a Node with One Child in a Binary Search Tree
刪除二叉搜索樹中有一個孩子的節點
Delete a Node with Two Children in a Binary Search Tree
刪除二叉搜索樹中有兩個孩子的節點
Invert a Binary Tree
倒二叉樹

特里 (Trie)

The trie (pronounced ‘try’), or prefix tree, is a kind of search tree. A trie stores data in steps where each step is a node in the trie. Tries are often used to store words for quick lookup, such as a word auto-complete feature.

trie(讀作“ try”)或前綴樹是一種搜索樹。特里樹按步驟存儲數據，其中每個步驟都是特里樹中的一個節點。嘗試通常用于存儲單詞以進行快速查找，例如單詞自動完成功能。

Each node in a language trie contains one letter of a word. You follow the branches of a trie to spell a word, one letter at a time. The steps begin to branch off when the order of the letters diverge from the other words in the trie, or when a word ends. Each node contains a letter (data) and a boolean that indicates whether the node is the last node in a word.

語言特里里的每個節點都包含一個單詞的一個字母。您按照特里的分支來拼寫一個單詞，一次拼一個字母。當字母的順序與特里中的其他單詞不同或單詞結束時，步驟開始分支。每個節點包含一個字母(數據)和一個布爾值，指示該節點是否是單詞中的最后一個節點。

Look at the image and you can form words. Always start at the root node at the top and work down. The trie shown here contains the word ball, bat, doll, do, dork, dorm, send, sense.

查看圖像，您可以形成單詞。始終從頂部的根節點開始，然后向下進行。此處顯示的特里包含單詞ball，bat，doll，do，dork，dorm，send，sense。

View the code for a trie in JavaScript here.

在此處查看JavaScript的代碼。

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Create a Trie Search Tree
創建一個Trie搜索樹

二進制堆 (Binary Heap)

A binary heap is another type of tree data structure. Every node has at most two children. Also, it is a complete tree. This means that all levels are completely filled until the last level and the last level is filled from left to right.

二進制堆是樹數據結構的另一種類型。每個節點最多有兩個孩子。而且，它是一棵完整的樹。這意味著所有級別都被完全填充，直到最后一個級別，并且最后一個級別從左到右被填充。

A binary heap can be either a min heap or a max heap. In a max heap, the keys of parent nodes are always greater than or equal to those of the children. In a min heap, the keys of parent nodes are less than or equal to those of the children.

二進制堆可以是最小堆，也可以是最大堆。在最大堆中，父節點的鍵始終大于或等于子節點的鍵。在最小堆中，父節點的密鑰小于或等于子節點的密鑰。

The order between levels is important but the order of nodes on the same level is not important. In the image, you can see that the third level of the min heap has values 10, 6, and 12. Those numbers are not in order.

級別之間的順序很重要，但是同一級別上的節點的順序并不重要。在該圖像中，您可以看到最小堆的第三級具有值10、6和12。這些數字沒有順序。

View the code for a heap in JavaScript here.

在此處查看JavaScript中的堆代碼。

二進制堆時間復雜度 (Binary heap time complexity)

Algorithm	Average	Worst Case
Space	0(n)	0(n)
Search	0(1)	0(log n)
Insert	0(log n)	0(log n)
Delete	0(1)	0(1)

算法	平均	最糟糕的情況
空間	0(n)	0(n)
搜索	0(1)	0(log n)
插	0(log n)	0(log n)
刪除	0(1)	0(1)

freeCodeCamp的挑戰 (freeCodeCamp challenges)

Insert an Element into a Max Heap
將元素插入最大堆
Remove an Element from a Max Heap
從最大堆移除元素
Implement Heap Sort with a Min Heap
用最小堆實現堆排序

圖形 (Graph)

Graphs are collections of nodes (also called vertices) and the connections (called edges) between them. Graphs are also known as networks.

圖是節點(也稱為頂點)及其之間的連接(稱為邊)的集合。圖也稱為網絡。

One example of graphs is a social network. The nodes are people and the edges are friendship.

圖的一個示例是社交網絡。節點是人，邊緣是友誼。

There are two major types of graphs: directed and undirected. Undirected graphs are graphs without any direction on the edges between nodes. Directed graphs, in contrast, are graphs with a direction in its edges.

圖有兩種主要類型：有向圖和無向圖。無向圖是節點之間的邊緣上沒有任何方向的圖。相反，有向圖是在其邊緣具有方向的圖。

Two common ways to represent a graph are an adjacency list and an adjacency matrix.

表示圖形的兩種常見方法是鄰接表和鄰接矩陣。

An adjacency list can be represented as a list where the left side is the node and the right side lists all the other nodes it’s connected to.

鄰接表可以表示為一個列表，其中左側為節點，右側列出其連接到的所有其他節點。

An adjacency matrix is a grid of numbers, where each row or column represents a different node in the graph. At the intersection of a row and a column is a number that indicates the relationship. Zeros mean there is no edge or relationship. Ones mean there is a relationship. Numbers higher than one can be used to show different weights.

鄰接矩陣是一個數字網格，其中每一行或每一列代表圖中的一個不同節點。在行和列的交點處是一個數字，指示關系。零表示不存在邊或關系。有人表示有關系。大于1的數字可用于顯示不同的權重。

Traversal algorithms are algorithms to traverse or visit nodes in a graph. The main types of traversal algorithms are breadth-first search and depth-first search. One of the uses is to determine how close nodes are to a root node. See how to implement breadth-first search in JavaScript in the video below.

遍歷算法是遍歷或訪問圖中節點的算法。遍歷算法的主要類型是廣度優先搜索和深度優先搜索。用途之一是確定節點與根節點的距離。在下面的視頻中，了解如何在JavaScript中實現廣度優先搜索。

See the code for breadth-first search on an adjacency matrix graph in JavaScript.

有關在JavaScript中對鄰接矩陣圖進行廣度優先搜索的代碼，請參見。