程式設計師面試必知的8個數據結構

by Fahim ul Haq

瑞士計算機科學家Niklaus Wirth在1976年寫了一本書，名為《算法+數據結構=程序》。

40多年後，這個等式仍然成立。這就是為什麼軟體工程候選人必須證明他們對數據結構及其應用程式的理解。

幾乎所有問題都要求考生表現出對數據結構的深刻理解。無論您剛畢業（從大學還是編程訓練營）畢業，還是有數十年的經驗都沒關係。

有時訪談問題明確提到數據結構，例如「給定二叉樹」。其他時候它是隱式的，例如「我們要跟蹤與每個作者關聯的書籍數量」。

即使您只是想在當前工作中變得更好，學習數據結構也是必不可少的。讓我們從了解基礎開始。

什麼是數據結構？

簡而言之，數據結構是一個以特定布局存儲數據的容器。這種「布局」使數據結構在某些操作中有效，而在另一些操作中效率低下。您的目標是了解數據結構，以便選擇最適合當前問題的數據結構。

為什麼我們需要數據結構？

由於數據結構用於以有組織的形式存儲數據，並且由於數據是計算機科學中最重要的實體，因此數據結構的真正價值顯而易見。

無論您要解決什麼問題，都必須以一種或另一種方式處理數據-無論是員工的薪水，股票價格，購物清單還是簡單的電話簿。

根據不同的場景，數據需要以特定的格式存儲。我們有一些數據結構可以滿足我們以不同格式存儲數據的需求。

常用數據結構

讓我們首先列出最常用的數據結構，然後逐一介紹它們：

數組

堆棧

隊列

鍊表

樹

圖

前綴樹

哈希表

數組

數組是最簡單，使用最廣泛的數據結構。其他數據結構（如堆棧和隊列）是從數組派生的。

這是大小為4的簡單數組的圖像，其中包含元素（1、2、3和4）。

每個數據元素都被分配一個稱為Index的正數值，它對應於該項在數組中的位置。大多數語言將數組的起始索引定義為0。

以下是兩種類型的數組：

陣列的基本操作

插入—在給定索引處插入元素

Get —返回給定索引處的元素

刪除-刪除給定索引處的元素

Size —獲取數組中元素的總數

Array面試常見問題

查找數組的第二個最小元素

數組中的第一個非重複整數

合併兩個排序的數組

重新排列數組中的正值和負值

堆棧

我們都熟悉著名的「撤消」選項，該選項幾乎存在於每個應用程式中。有沒有想過它是如何工作的？想法是：您將工作的先前狀態（限於特定數量）存儲在內存中，順序是最後一個出現在最前面。這不能僅僅通過使用數組來完成。這就是堆棧派上用場的地方。

堆疊的真實示例可能是一堆以垂直順序放置的書。為了獲得位於中間位置的書，您需要刪除所有放在其頂部的書。這就是LIFO（後進先出）方法的工作方式。

這是包含三個數據元素（1、2和3）的堆棧圖像，其中3在頂部，並且將首先刪除：

堆棧的基本操作：

推入—在頂部插入一個元素

Pop —從堆棧中移除後返回頂部元素

isEmpty —如果堆棧為空，則返回true

Top —返回頂部元素，而不從堆棧中移除

堆棧採訪常見問題

使用堆棧評估後綴表達式

對堆棧中的值進行排序

檢查表達式中的平衡括號

隊列

與Stack類似，Queue是另一個線性數據結構，該結構以順序方式存儲元素。堆棧和隊列之間唯一的顯著區別是，隊列使用FIFO 方法代替了LIFO方法，該方法是先進先出的縮寫。

排隊的一個完美的現實例子：排隊的人在售票亭等車。如果有新人來，他們將從頭開始而不是從一開始就加入隊伍—站在最前面的人將是第一個獲得票證並因此離開隊伍的人。

這是包含四個數據元素（1、2、3和4）的Queue圖像，其中1在頂部，並且將首先刪除：

隊列的基本操作

Enqueue（）—將元素插入隊列的末尾

Dequeue（）-從隊列的開頭刪除一個元素

isEmpty（）—如果隊列為空，則返回true

Top（）—返回隊列的第一個元素

排隊面試常見問題

使用隊列實現堆棧

反轉隊列的前k個元素

使用隊列生成從1到n的二進位數

鍊表

鍊表是另一種重要的線性數據結構，乍一看可能與數組相似，但在內存分配，內部結構以及插入和刪除的基本操作上有所不同。

鍊表就像一個節點鏈，其中每個節點都包含諸如數據之類的信息以及指向鏈中後續節點的指針。有一個頭指針，它指向連結列表的第一個元素，如果列表為空，則僅指向null或不指向任何內容。

連結列表用於實現文件系統，哈希表和鄰接列表。

這是鍊表內部結構的直觀表示：

以下是連結列表的類型：

鍊表的基本操作：

InsertAtEnd —在鍊表的末尾插入給定元素

InsertAtHead —在連結列表的開頭/開頭插入給定元素

刪除-從連結列表中刪除給定元素

DeleteAtHead —刪除連結列表的第一個元素

搜索-從連結列表中返回給定的元素

isEmpty —如果連結列表為空，則返回true

常見問題鍊表面試問題

反向連結列表

檢測鍊表中的循環

從鍊表的末尾返回第N個節點

從連結列表中刪除重複項

圖（Graph）

圖是一組以網絡形式相互連接的節點。節點也稱為頂點。阿對（x，y）的被稱為邊緣，這表明頂點X被連接到頂點ÿ。一條邊可能包含權重/成本，表示從頂點x到y遍歷需要多少成本。

圖的類型：

在程式語言中，圖形可以使用兩種形式表示：

常見的圖遍歷算法：

Graph面試常見問題

實施廣度和深度優先搜索

檢查圖是否為樹

計算圖中的邊數

查找兩個頂點之間的最短路徑

樹（Tree）

樹是由頂點（節點）和連接它們的邊組成的分層數據結構。樹類似於圖，但是區別圖與樹的關鍵是樹中不能存在循環。

樹在人工智慧和複雜算法中被廣泛使用，以提供有效的存儲機制來解決問題。

這是一棵簡單的樹的圖像，以及樹數據結構中使用的基本術語：

以下是樹的類型：

一元樹

平衡樹

二叉樹

二進位搜索樹

AVL樹

紅黑樹

2–3樹

其中，二叉樹和二叉搜索樹是最常用的樹。

樹面試常見問題

查找二叉樹的高度

在二叉搜索樹中找到第k個最大值

查找距根「 k」距離的節點

在二叉樹中查找給定節點的祖先

前綴樹（Trie）

Trie，也稱為「前綴樹」，是一種類似樹的數據結構，被證明對於解決與字符串有關的問題非常有效。它提供了快速的檢索功能，主要用於在字典中搜索單詞，在搜尋引擎中提供自動建議，甚至用於IP路由。

這是Trie中三個單詞「 top」，「 thus」和「 their」的存儲方式的說明：

單詞以從上到下的方式存儲，其中綠色節點「 p」，「 s」和「 r」分別表示「 top」，「 thus」和「 their」的結尾。

特裡採訪常見問題：

計算Trie中的單詞總數

列印所有存儲在Trie中的單詞

使用Trie排序數組的元素

使用Trie從字典中套用單詞

建立T9字典

哈希表

散列是用於唯一標識對象並將每個對象存儲在一些預先計算的唯一索引（稱為「鍵」）的過程。因此，對象以「鍵值」對的形式存儲，此類項目的集合稱為「字典」。可以使用該鍵搜索每個對象。基於哈希的數據結構不同，但是最常用的數據結構是哈希表。

哈希表通常使用數組來實現。

哈希數據結構的性能取決於以下三個因素：

這是散列如何在數組中映射的說明。該數組的索引是通過哈希函數計算的。

散列面試常見問題

在數組中查找對稱對

追蹤完整的旅程

查找一個數組是否是另一個數組的子集

檢查給定數組是否不相交

以上是進入編碼面試之前您絕對應該知道的前八個數據結構。

【英語能力提升】英文原文：

Niklaus Wirth, a Swiss computer scientist, wrote a book in 1976 titled Algorithms + Data Structures = Programs.

40+ years later, that equation still holds true. That’s why software engineering candidates have to demonstrate their understanding of data structures along with their applications.

Almost all problems require the candidate to demonstrate a deep understanding of data structures. It doesn’t matter whether you have just graduated (from a university or coding bootcamp), or you have decades of experience.

Sometimes interview questions explicitly mention a data structure, for example, 「given a binary tree.」 Other times it’s implicit, like 「we want to track the number of books associated with each author.」

Learning data structures is essential even if you’re just trying to get better at your current job. Let’s start with understanding the basics.

What is a Data Structure?

Simply put, a data structure is a container that stores data in a specific layout. This 「layout」 allows a data structure to be efficient in some operations and inefficient in others. Your goal is to understand data structures so that you can pick the data structure that’s most optimal for the problem at hand.

Why do we need Data Structures?

As data structures are used to store data in an organized form, and since data is the most crucial entity in computer science, the true worth of data structures is clear.

No matter what problem are you solving, in one way or another you have to deal with data — whether it’s an employee’s salary, stock prices, a grocery list, or even a simple telephone directory.

Based on different scenarios, data needs to be stored in a specific format. We have a handful of data structures that cover our need to store data in different formats.

Commonly used Data Structures

Let’s first list the most commonly used data structures, and then we』ll cover them one by one:

Arrays

Stacks

Queues

Linked Lists

Trees

Graphs

Tries (they are effectively trees, but it’s still good to call them out separately).

Hash Tables

Arrays

An array is the simplest and most widely used data structure. Other data structures like stacks and queues are derived from arrays.

Here’s an image of a simple array of size 4, containing elements (1, 2, 3 and 4).

Each data element is assigned a positive numerical value called the Index, which corresponds to the position of that item in the array. The majority of languages define the starting index of the array as 0.

The following are the two types of arrays:

Basic Operations on Arrays

Insert — Inserts an element at a given index

Get — Returns the element at a given index

Delete — Deletes an element at a given index

Size — Gets the total number of elements in an array

Commonly asked Array interview questions

Find the second minimum element of an array

First non-repeating integers in an array

Merge two sorted arrays

Rearrange positive and negative values in an array

Stacks

We are all familiar with the famous Undo option, which is present in almost every application. Ever wondered how it works? The idea: you store the previous states of your work (which are limited to a specific number) in the memory in such an order that the last one appears first. This can’t be done just by using arrays. That is where the Stack comes in handy.

A real-life example of Stack could be a pile of books placed in a vertical order. In order to get the book that’s somewhere in the middle, you will need to remove all the books placed on top of it. This is how the LIFO (Last In First Out) method works.

Here’s an image of stack containing three data elements (1, 2 and 3), where 3 is at the top and will be removed first:

Basic operations of stack:

Push — Inserts an element at the top

Pop — Returns the top element after removing from the stack

isEmpty — Returns true if the stack is empty

Top — Returns the top element without removing from the stack

Commonly asked Stack interview questionsQueues

Similar to Stack, Queue is another linear data structure that stores the element in a sequential manner. The only significant difference between Stack and Queue is that instead of using the LIFO method, Queue implements the FIFO method, which is short for First in First Out.

A perfect real-life example of Queue: a line of people waiting at a ticket booth. If a new person comes, they will join the line from the end, not from the start — and the person standing at the front will be the first to get the ticket and hence leave the line.

Here’s an image of Queue containing four data elements (1, 2, 3 and 4), where 1 is at the top and will be removed first:

Basic operations of Queue

Enqueue() — Inserts an element to the end of the queue

Dequeue() — Removes an element from the start of the queue

isEmpty() — Returns true if the queue is empty

Top() — Returns the first element of the queue

Commonly asked Queue interview questions

Implement stack using a queue

Reverse first k elements of a queue

Generate binary numbers from 1 to n using a queue

Linked List

A linked list is another important linear data structure which might look similar to arrays at first but differs in memory allocation, internal structure and how basic operations of insertion and deletion are carried out.

A linked list is like a chain of nodes, where each node contains information like data and a pointer to the succeeding node in the chain. There’s a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.

Linked lists are used to implement file systems, hash tables, and adjacency lists.

Here’s a visual representation of the internal structure of a linked list:

Following are the types of linked lists:

Basic operations of Linked List:

InsertAtEnd — Inserts a given element at the end of the linked list

InsertAtHead — Inserts a given element at the start/head of the linked list

Delete — Deletes a given element from the linked list

DeleteAtHead — Deletes the first element of the linked list

Search — Returns the given element from a linked list

isEmpty — Returns true if the linked list is empty

Commonly asked Linked List interview questions

Reverse a linked list

Detect loop in a linked list

Return Nth node from the end in a linked list

Remove duplicates from a linked list

Graphs

A graph is a set of nodes that are connected to each other in the form of a network. Nodes are also called vertices. A pair(x,y) is called an edge, which indicates that vertex x is connected to vertex y. An edge may contain weight/cost, showing how much cost is required to traverse from vertex x to y.

Types of Graphs:

Undirected Graph

Directed Graph

In a programming language, graphs can be represented using two forms:

Adjacency Matrix

Adjacency List

Common graph traversing algorithms:

Breadth First Search

Depth First Search

Commonly asked Graph interview questions

Implement Breadth and Depth First Search

Check if a graph is a tree or not

Count the number of edges in a graph

Find the shortest path between two vertices

Trees

A tree is a hierarchical data structure consisting of vertices (nodes) and edges that connect them. Trees are similar to graphs, but the key point that differentiates a tree from the graph is that a cycle cannot exist in a tree.

Trees are extensively used in Artificial Intelligence and complex algorithms to provide an efficient storage mechanism for problem-solving.

Here’s an image of a simple tree, and basic terminologies used in tree data structure:

The following are the types of trees:

N-ary Tree

Balanced Tree

Binary Tree

Binary Search Tree

AVL Tree

Red Black Tree

2–3 Tree

Out of the above, Binary Tree and Binary Search Tree are the most commonly used trees.

Commonly asked Tree interview questions

Find the height of a binary tree

Find kth maximum value in a binary search tree

Find nodes at 「k」 distance from the root

Find ancestors of a given node in a binary tree

Trie

Trie, which is also known as 「Prefix Trees」, is a tree-like data structure which proves to be quite efficient for solving problems related to strings. It provides fast retrieval, and is mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.

Here’s an illustration of how three words 「top」, 「thus」, and 「their」 are stored in Trie:

The words are stored in the top to the bottom manner where green colored nodes 「p」, 「s」 and 「r」 indicates the end of 「top」, 「thus」, and 「their」 respectively.

Commonly asked Trie interview questions:

Count total number of words in Trie

Print all words stored in Trie

Sort elements of an array using Trie

Form words from a dictionary using Trie

Build a T9 dictionary

Hash Table

Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its 「key.」 So, the object is stored in the form of a 「key-value」 pair, and the collection of such items is called a 「dictionary.」 Each object can be searched using that key. There are different data structures based on hashing, but the most commonly used data structure is the hash table.

Hash tables are generally implemented using arrays.

The performance of hashing data structure depends upon these three factors:

Here’s an illustration of how the hash is mapped in an array. The index of this array is calculated through a Hash Function.

Commonly asked Hashing interview questions

Find symmetric pairs in an array

Trace complete path of a journey

Find if an array is a subset of another array

Check if given arrays are disjoint

The above are the top eight data structures that you should definitely know before walking into a coding interview.

https://www.freecodecamp.org/news/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3/

最後，附上數據結構與算法的基本知識點：

數據結構與算法數據結構什麼是數據結構？邏輯、存儲、運算

數據（data）

結構（structure）

數據結構（data structure）

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。

數據結構(data structure)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關係，並對這種結構定義相適應的運算，設計出相應的算法，並確保經過這些運算以後所得到的新結構仍保持原來的結構類型。簡而言之，數據結構是相互之間存在一種或多種特定關係的數據元素的集合，即帶「結構」的數據元素的集合。「結構」就是指數據元素之間存在的關係，分為邏輯結構和存儲結構。[2]

數據的邏輯結構和物理結構是數據結構的兩個密切相關的方面，同一邏輯結構可以對應不同的存儲結構。算法的設計取決於數據的邏輯結構，而算法的實現依賴於指定的存儲結構。[2]

數據結構的研究內容是構造複雜軟體系統的基礎，它的核心技術是分解與抽象。通過分解可以劃分出數據的3個層次；再通過抽象，捨棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象捨棄實現細節，就得到運算的定義。上述兩個方面的結合可以將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然後，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。[3]

數據結構研究對象

數據的結構有哪些類型？

數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的物理結構(也稱為存儲結構)。一般來說，一種數據結構的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等。

指數據的邏輯結構在計算機存儲空間的存放形式。[1]

數據的物理結構是數據結構在計算機中的表示（又稱映像），它包括數據元素的機內表示和關係的機內表示。由於具體實現的方法有順序、連結、索引、散列等多種，所以，一種數據結構可表示成一種或多種存儲結構。[1]

數據元素的機內表示（映像方法）：用二進位位（bit）的位串表示數據元素。通常稱這種位串為節點（node）。當數據元素有若干個數據項組成時，位串中與各個數據項對應的子位串稱為數據域（data field）。因此，節點是數據元素的機內表示（或機內映像）。[1]

關係的機內表示（映像方法）：數據元素之間的關係的機內表示可以分為順序映像和非順序映像，常用兩種存儲結構：順序存儲結構和鏈式存儲結構。順序映像藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係。非順序映像藉助指示元素存儲位置的指針（pointer）來表示數據元素之間的邏輯關係。[1]

指反映數據元素之間的邏輯關係的數據結構，其中的邏輯關係是指數據元素之間的前後間關係，而與他們在計算機中的存儲位置無關。邏輯結構包括：[1]

1.集合：數據結構中的元素之間除了「同屬一個集合」 的相互關係外，別無其他關係；[1]

2.線性結構：數據結構中的元素存在一對一的相互關係；[1]

3.樹形結構：數據結構中的元素存在一對多的相互關係；[1]

4.圖形結構：數據結構中的元素存在多對多的相互關係。[1]

數據的邏輯結構

數據的物理結構

數據存儲結構

常用的數據結構有哪些？

數組(Array)

棧( Stack)

隊列(Queue)

鍊表( Linked List)

樹( Tree)

圖(Graph)

堆(Heap)

散列表(Hash)

跳表

數據結構的分類（按照數據的邏輯結構）

線性結構

非線性結構

樹( Tree)

圖(Graph)

非線性結構就是表中各個結點之間具有多個對應關係。如果從數據結構的語言來描述，非線性結構應該包括如下幾點：[5]

1、非線性結構是非空集。[5]

2、非線性結構的一個結點可能有多個直接前趨結點和多個直接後繼結點。[5]

在實際應用中，數組、廣義表、樹結構和圖結構等數據結構都屬於非線性結構。[5]

特性

例子

數據結構主要用來解決怎樣的問題的？怎麼解決的？算法什麼是算法？常用的算法有哪些算法的目的算法的應用場景程序=數據結構+算法程序設計是什麼？程序設計的藝術參考資料

彭軍、向毅主編．數據結構預算法：人民郵電出版社，2013年

石玉強，閆大順主編．數據結構與算法：中國農業大學出版社，2017.02：第5頁

張青，王囡囡著．工程軟體開發技術：北京理工大學出版社，2016.08：第133頁

孟朝霞主編．大學計算基礎（第2版）：西安電子科技大學出版社，2012.02：第75頁

劉亞東；曲心慧編．C/C++常用算法手冊：中國鐵道出版社，2017.09：第21頁