常见8种数据结构

常见的数据结构包括数组、链表、队列、栈、树、堆、哈希表和图，每种数据结构都有其特点，如下：

1.数组

特点：

• 固定大小的线性数据结构
• 支持快速随机访问
• 插入和删除效率比较低

一般应用于需要快速随机访问元素的场景。
案例：

# 定义一个数组
arr = [1, 2 , 3, 4, 5]
# 访问数组元素
print(arr[2])  # 输出: 3

# 修改数组元素
arr[2] = 10
print(arr)  # 输出: [1, 2, 10, 4, 5]

# 添加元素
arr.append(6)
print(arr)  # 输出: [1, 2, 10, 4, 5, 6]

# 删除元素
arr.pop(2)
print(arr)  # 输出: [1, 2, 4, 5, 6]

2.链表

特点：

• 动态大小的数据结构
• 插入和删除效率比较高
• 不支持快速随机访问

适用于需要频繁插入和删除元素的场景
案例：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data, end=" -> ")
            curr = curr.next
        print("None")

# 使用链表
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()  # 输出: 1 -> 2 -> 3 -> None

3.队列

特点：

• 先进先出
• 插入操作在队尾进行，删除操作在队头进行

应用于需要先进先出访问元素的场景，如任务调度、消息队列等
案例：

from collections import deque

# 使用 deque 实现队列
queue = deque()

# 入队
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # 输出: deque([1, 2, 3])

# 出队
print(queue.popleft())  # 输出: 1
print(queue)  # 输出: deque([2, 3])

4.栈

特点：

• 先进后出
• 插入和删除在栈顶进行

应用于需要后进先出访问元素的场景，如函数调用栈、表达式求值等
案例：

# 使用列表实现栈
stack = []

# 入栈
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # 输出: [1, 2, 3]

# 出栈
print(stack.pop())  # 输出: 3
print(stack)  # 输出: [1, 2]

5.树

特点：

• 非线性，由节点和边组成
• 树中的节点有层次关系，一个节点可以有多个子节点

应用于需要表示层次结构的场景，比如文件系统、组织结构等
案例：

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

    def print_tree(self, level=0):
        prefix = " " * (level * 4)
        print(prefix + self.data)
        for child in self.children:
            child.print_tree(level + 1)

# 创建树
root = TreeNode("Root")
child1 = TreeNode("Child1")
child2 = TreeNode("Child2")
child3 = TreeNode("Child3")
root.add_child(child1)
root.add_child(child2)

child1.add_child(TreeNode("Grandchild1"))
child1.add_child(TreeNode("Grandchild2"))
root.print_tree()

6.图

特点：

• 非线性，由节点和边组成
• 图中的节点可以通过边来相互连接

应用于需要表示网络结构的场景，如社交网络、交通网络等。
案例：

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def print_graph(self):
        for node in self.graph:
            print(f"{node} -> {', '.join(self.graph[node])}")

# 创建图
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.print_graph()

7.哈希表

特点：

• 基于哈希函数实现的键值对数据结构
• 支持快速的插入、删除和查找操作

应用于需要快速查找和插入操作的场景，如字典、缓存等。
案例：

# 使用字典实现哈希表
hash_table = {}

# 插入键值对
hash_table["name"] = "John"
hash_table["age"] = 30
hash_table["city"] = "New York"
print(hash_table)  # 输出: {'name': 'John', 'age': 30, 'city': 'New York'}

# 查找键值对
print(hash_table["name"])  # 输出: John

# 删除键值对
del hash_table["age"]
print(hash_table)  # 输出: {'name': 'John', 'city': 'New York'}

8.堆

特点：

• 堆是一颗完全二叉树
• 分为最大堆和最小堆
  • 最大堆：每个节点的值都大于或等于其子节点的值。
  • 最小堆：每个节点的值都小于或等于其子节点的值。
• 支持快速获取最大值或最小值的操作。

适用于优先队列，堆排序和实现高效的合并K个有序链表问题。
案例：

import heapq

# 创建一个最小堆
min_heap = []

# 插入元素
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 2)
print(min_heap)  # 输出: [1, 2, 4, 3]

# 弹出最小元素
print(heapq.heappop(min_heap))  # 输出: 1
print(min_heap)  # 输出: [2, 3, 4]

# 创建一个最大堆（通过将元素取反实现）
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -2)
print([-x for x in max_heap])  # 输出: [4, 2, 3, 1]

# 弹出最大元素
print(-heapq.heappop(max_heap))  # 输出: 4
print([-x for x in max_heap])  # 输出: [3, 2, 1]