常见的数据结构包括数组、链表、队列、栈、树、堆、哈希表和图，每种数据结构都有其特点，如下：
常见数据结构
1.数组
2.链表
3.队列
4.栈
5.树
6.图
7.哈希表
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个有序链表问题。
