每位 Python 程序员都应该知道的 8 种数据结构

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

在解决现实世界的编程问题时，雇主和招聘人员既关注运行效率，也关注资源利用效率。

了解哪种数据结构最适合当前解决方案，可以提高程序性能并缩短开发时间。因此，大多数顶尖公司都要求应聘者对数据结构有深入的理解，并在编程面试中重点考察这方面的能力。

今天我们将讨论以下内容：

• 什么是数据结构？
• Python中的数组
• Python中的队列
• Python中的栈
• Python 中的链表
• Python中的循环链表
• Python中的树
• Python中的图表
• Python中的哈希表
• 接下来要学什么？

第一次就顺利通过Python面试

通过 200 多个实践练习题，巩固你的 Python 编程技能，例如数据结构、递归和并发。

轻松应对 Python 编程面试

什么是数据结构？

数据结构是用于存储和组织数据的代码结构，它使信息的修改、浏览和访问更加便捷。数据结构决定了数据的收集方式、我们可以实现的功能以及数据之间的关系。

数据结构几乎应用于计算机科学和编程的各个领域，从操作系统到前端开发，再到机器学习。

数据结构有助于：

• 管理和利用大型数据集
• 快速从数据库中搜索特定数据
• 在数据点之间建立清晰的层级或关系联系
• 简化并加快数据处理

数据结构是高效解决实际问题的关键基石。它们是经过验证和优化的工具，能够为你提供一个简洁的框架来组织程序。毕竟，你无需每次都重新发明轮子（或结构）。

每种数据结构都有其最适合解决的任务或场景。Python 内置了四种数据结构：列表、字典、元组和集合。这些内置数据结构都带有默认方法和后台优化，使其易于使用。

Python 中的大多数数据结构都是这些结构的修改形式，或者使用内置结构作为其骨架。

• 列表：类似数组的结构，允许你将一组相同类型的可变对象保存到变量中。
• 元组：元组是不可变列表，这意味着其中的元素不能更改。它使用圆括号而不是方括号声明。
• 集合：集合是无序的元素集合，这意味着元素没有索引，也没有固定的顺序。它们用花括号声明。
• 字典（dict）：类似于其他语言中的哈希映射或哈希表，字典是键值对的集合。您可以使用空花括号初始化一个空字典，然后用冒号分隔的键和值填充它。所有键都是唯一的、不可变的对象。

现在，让我们看看如何利用这些结构来创建面试官想要的所有高级结构。

Python中的数组（列表）

Python 没有内置的数组类型，但你可以使用列表来完成所有相同的任务。数组是将相同类型值存储在同一名称下的集合。

数组中的每个值都称为“元素”，索引表示其位置。您可以通过调用数组名称并加上所需元素的索引来访问特定元素。您还可以使用相应方法获取数组的长度len()。

与 Java 等编程语言在声明后数组是静态的不同，Python 的数组在添加/删除元素时会自动向上或向下缩放。

例如，我们可以使用该append()方法在现有数组的末尾添加一个额外的元素，而不是声明一个新数组。

这使得 Python 数组特别易于使用，并且可以随时进行调整。

cars = ["Toyota", "Tesla", "Hyundai"]
print(len(cars))
cars.append("Honda")
cars.pop(1)
for x in cars:
  print(x)

优势：

• 创建和使用数据序列非常简单
• 自动缩放以满足不断变化的尺寸要求
• 用于创建更复杂的数据结构

缺点：

• 不针对科学数据进行优化（与 NumPy 的数组不同）
• 只能操作列表的最右侧部分

应用领域：

• 相关值或对象的共享存储，即myDogs
• 您将循环遍历的数据集合
• 数据结构集合，例如元组列表

Python中常见的数组面试题

• 从列表中移除偶数。
• 合并两个已排序列表
• 找出列表中的最小值
• 最大和子列表
• 所有元素的印刷产品

Python中的队列

队列是一种线性数据结构，它按照“先进先出”（FIFO）的顺序存储数据。与数组不同，队列中不能通过索引访问元素，只能取出下一个最早的元素。这使得队列非常适合对顺序敏感的任务，例如在线订单处理或语音邮件存储。

你可以把排队想象成杂货店里的队伍；收银员不会选择下一个结账的人，而是会优先处理排队时间最长的人。

我们可以使用 Python 列表append()及其pop()方法来实现队列。然而，这种方法效率低下，因为每次向列表开头添加新元素时，列表都必须将所有元素的索引向右移动一位。

相反，最佳实践是使用dequePythoncollections模块中的 `deque` 类。`deque` 针对 `append` 和 `pop` 操作进行了优化。`deque` 的实现还允许你创建双向队列，可以通过 `add` 和 ` popleft()pop`popright()方法访问队列的两端。

from collections import deque

# Initializing a queue
q = deque()

# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')

print("Initial queue")
print(q)

# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())

print("\nQueue after removing elements")
print(q)

# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

优势：

• 自动按时间顺序排列数据
• 满足尺寸要求的秤
• 高效且有deque格调

缺点：

• 只能访问末端数据

应用领域：

• 对共享资源（例如打印机或CPU 核心）进行操作
• 用作批处理系统的临时存储。
• 为同等重要的任务提供一个简单的默认排序方式

Python中常见的队列面试题

• 将队列的前 k 个元素反转
• 使用链表实现队列
• 使用队列实现栈

Python中的栈

栈是一种顺序数据结构，它类似于队列的后进先出（LIFO）版本。最后插入栈中的元素位于栈顶，并且是唯一可访问的元素。要访问栈中间的元素，必须先移除足够的元素，使目标元素位于栈顶。

许多开发者将堆栈想象成一叠餐盘；你可以向堆栈顶部添加或移除餐盘，但要将餐盘放在底部，必须移动整个堆栈。

添加元素称为push，移除元素称为pop。在 Python 中，可以使用内置的列表结构来实现栈。使用列表实现时，push 操作使用 `push`append()方法，pop 操作使用 `pop` 方法pop()。

stack = []

# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack')
print(stack)

# pop() function to pop
# element from stack in 
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

# uncommenting print(stack.pop())  
# will cause an IndexError 
# as the stack is now empty

优势：

• 提供使用 *Applications:* 或数组无法实现的 LIFO 数据管理。
• 自动缩放和对象清理
• 简单可靠的数据存储系统

缺点：

• 堆栈内存有限
• 栈上对象过多会导致栈溢出错误。

应用领域：

• 用于制造高反应性系统
• 内存管理系统使用堆栈来优先处理最近的请求。
• 有助于解答诸如括号匹配之类的问题。

Python 常见技术栈面试题

• 使用栈实现队列。
• 使用栈计算后缀表达式
• 下一个使用堆栈的最大元素
• min()使用栈创建一个函数

Python 中的链表

链表是一种顺序数据集合，它使用每个数据节点上的关系指针链接到列表中的下一个节点。

与数组不同，链表没有客观的节点位置，而是根据其周围节点的关系来确定节点位置。

链表中的第一个节点称为头节点，最后一个节点称为尾节点，尾节点带有一个null指针。

链表可以是单链的，也可以是双链的，这取决于每个节点是否只有一个指向下一个节点的指针，或者它是否还有第二个指向前一个节点的指针。

你可以把链表想象成一条链子；单个链环只与其直接相邻的链环相连，但所有链环组合在一起形成一个更大的结构。

Python 没有内置的链表实现，因此需要您实现一个Node类来保存数据值和一个或多个指针。

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

链表主要用于创建高级数据结构，如图和树，或用于需要频繁地在结构中添加/删除元素的任务。

优势：

• 高效地插入和删除新元素
• 比数组更容易重组
• 可作为学习更高级数据结构（例如图或树）的起点。

缺点：

• 将指针与每个数据点一起存储会增加内存占用。
• 必须始终从头节点开始遍历链表才能找到特定元素。

应用领域：

• 高级数据结构的构建模块
• 需要频繁添加和删除数据的解决方案

Python中常见的链表面试题

• 打印给定链表的中间元素
• 从已排序的链表中移除重复元素
• 检查单链表是否为回文
• 合并 K 个已排序链表
• 找出两个链表的交点

Python中的循环链表

标准链表的主要缺点是必须始终从头节点开始遍历。循环链表通过将尾节点的null指针替换为指向头节点的指针来解决这个问题。遍历时，程序会沿着指针一直遍历到它最初所在的节点。

这种设置的优势在于，您可以从任意节点开始遍历整个链表。它还允许您通过设置所需的循环次数，将链表用作可循环结构。循环链表非常适合长时间循环的进程，例如操作系统中的 CPU 分配。

优势：

• 可以从任意节点开始遍历整个列表。
• 使链表更适合循环结构

缺点：

• null如果没有标记，就很难找到列表的头节点和尾节点。

应用领域：

• 定期循环的解决方案，例如 CPU 调度

Python中常见的循环链表面试题

• 检测链表中的循环
• 反转循环链表
• 给定大小的反向循环链表组

继续温习Python数据结构

熟练掌握数据结构对于任何面试者都至关重要。Educative 的文字课程提供数百道实践练习题，确保您在面试时做好充分准备。
轻松应对 Python 编程面试

Python中的树

树是另一种基于关系的数据结构，专门用于表示层级结构。与链表类似，树由对象构成，每个Node对象包含一个数据值以及一个或多个指针，用于定义该数据值与其直接节点之间的关系。

每棵树都有一个根节点，所有其他节点都从根节点分支而出。根节点包含指向其正下方所有元素的指针，这些元素被称为它的子节点。这些子节点还可以拥有自己的子节点。二叉树的节点最多只能有两个子节点。

同一层级的节点称为兄弟节点。没有相连子节点的节点称为叶节点。

二叉树最常见的应用是二叉搜索树。二叉搜索树擅长搜索大型数据集，因为其时间复杂度取决于树的深度而不是节点的数量。

二叉搜索树有四条严格的规则：

• 左子树仅包含元素小于根节点的节点。
• 右子树仅包含元素大于根节点的节点。
• 左右子树也必须是二叉搜索树。它们必须遵循上述规则，且其根节点必须与树的根节点重合。
• 不能有重复的节点，即任何两个节点都不能具有相同的值。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

优势：

• 适用于表示层级关系
• 动态尺寸，非常适合大规模应用
• 快速插入和删除操作
• 在二叉搜索树中，插入的节点会立即按顺序排列。
• 二叉搜索树搜索效率很高；长度仅为 $O(高度)$。

缺点：

• 修改或“平衡”树或从已知位置检索元素耗时很长，为 O(logn)4。
• 子节点不包含关于其父节点的任何信息，因此很难向后遍历。
• 仅适用于已排序的列表。对于未排序的数据，搜索将退化为线性搜索。

应用领域：

• 非常适合存储层级数据，例如文件位置
• 用于实现诸如二叉搜索树和二叉堆之类的顶部搜索和排序算法。

Python 中的公共树面试题

• 检查两棵二叉树是否相同
• 实现二叉树的层序遍历
• 打印二叉搜索树的周长
• 对路径上的所有节点求和
• 连接二叉树的所有兄弟节点

Python中的图表

图是一种数据结构，用于直观地表示数据顶点（图中的节点）之间的关系。连接顶点的链接称为边。

边定义了哪些顶点相互连接，但不表示它们之间的方向性流动。每个顶点都与其他顶点相连，这些连接以逗号分隔的列表形式保存在该顶点上。

还有一种特殊的图叫做有向图，它定义了关系的方向，类似于链表。有向图在对单向关系或类似流程图的结构进行建模时非常有用。

它们主要用于以代码形式传达可视化的网络结构。这些结构可以模拟多种不同类型的关系，例如层级结构、分支结构，或者仅仅是无序的关系网络。图的通用性和直观性使其成为数据科学领域的热门工具。

用纯文本编写时，图包含顶点和边的列表：

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

在 Python 中，图的最佳实现方式是使用字典，其中每个顶点的名称作为键，边的列表作为值。

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
                 "b" : ["a", "d"],
                 "c" : ["a", "d"],
                  "d" : ["e"],
                  "e" : ["d"]
         }

# Print the graph          
print(graph)

优势：

• 通过代码快速传递视觉信息
• 可用于模拟各种现实世界的问题
• 语法简单易学

缺点：

• 在大型图中，顶点之间的连接很难理解。
• 从图中解析数据非常耗时。

应用领域：

• 非常适合用于模拟网络或网状结构。
• 用于模拟Facebook等社交网站

Python中常见的图论面试题

• 检测有向图中的环
• 在有向图中找出“母顶点”
• 计算无向图中的边数
• 检查两个顶点之间是否存在路径
• 找出两顶点之间的最短路径

Python中的哈希表

哈希表是一种复杂的数据结构，能够存储大量信息并高效地检索特定元素。

这种数据结构使用键/值对，其中键是所需元素的名称，值是存储在该名称下的数据。

每个输入键都会经过一个哈希函数，将其从原始形式转换为一个整数值，称为哈希值。哈希函数必须始终从相同的输入生成相同的哈希值，计算速度必须快，并且生成的值长度必须固定。Python 包含一个内置hash()函数，可以加快实现速度。

然后，该表利用哈希值找到所需值的大致位置，即存储桶。程序随后只需在该子组中搜索所需值，而无需在整个数据池中搜索。

除了上述通用框架之外，哈希表会根据不同的应用场景而有很大差异。有些哈希表允许使用不同数据类型的键，而有些哈希表则可能采用不同的存储桶设置或不同的哈希函数。

以下是一个用 Python 编写的哈希表示例：

import pprint
class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)
    def _assign_buckets(self, elements):
        for key, value in elements: #calculates the hash of each key
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size # positions the element in the bucket using hash
            self.buckets[index].append((key, value)) #adds a tuple in the bucket
    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None
    def __str__(self):
        return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
if __name__ == "__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")

优势：

• 可以将任何形式的键转换为整数索引
• 对大型数据集极其有效
• 搜索功能非常有效
• 每次搜索的步骤数固定，添加或删除元素的效率也固定。
• 使用Python 3进行了优化

缺点：

• 哈希值必须唯一，两个键转换成相同的哈希值会导致冲突错误。
• 碰撞错误需要对哈希函数进行全面改造。
• 对于初学者来说，搭建起来比较困难。

应用领域：

• 用于大型、频繁搜索的数据库
• 使用输入键的检索系统

Python中常见的哈希表面试题

• 从零开始构建哈希表（不使用内置函数）
• 使用哈希表进行单词构成
• 找出两个和为“k”的数。
• 实现开放寻址以处理冲突
• 使用哈希表检测列表是否循环

接下来要学什么？

针对这八种数据结构，每一种都有数十种面试题和题型。准备面试的最佳方法就是不断练习实际问题。

为了帮助你成为数据结构专家，Educative 创建了“Python 编程面试制胜之道”学习路径。这条精心设计的学习路径包含了所有热门概念的实践练习材料，例如数据结构、递归和并发。

到最后，你将完成超过 250 道练习题，并获得破解任何面试问题的实践经验。

学习愉快！

继续阅读有关 Python 面试的内容。

• 50 道 Python 面试题及答案
• 软件工程师面试中最常见的 5 道并发编程问题
• 掌握Python算法，轻松应对编程面试