手把手带你用Python实现8种核心数据结构

Array

数组是最简单、最常用的数据结构之一。它将一组元素存储在内存中的一块连续区域内，允许通过索引快速访问任何元素。每个元素都由其位置(即索引)标识，这使得可以直接检索或更新该元素。

使用场景：数组非常适合存储有序列表，尤其适合需要按位置快速访问或修改的情况。但是，在数组中间添加或删除元素可能会比较慢，因为其他元素必须移动位置才能腾出空间。

代码示例：

classArray:
def__init__(self, size):
        self.size = size
        self.data = [None] * size  # 分配固定大小的空间

defset(self, index, value):
if0 <= index < self.size:
            self.data[index] = value
else:
raise IndexError("Index out of bounds")

defget(self, index):
if0 <= index < self.size:
return self.data[index]
else:
raise IndexError("Index out of bounds")

# 使用
arr = Array(5)
arr.set(0, 10)
print(f"Array Index 0: {arr.get(0)}")

Linked List

链表是一种线性数据结构，其中每个元素(称为节点)都包含一个值和一个指向链中下一个节点的引用(或指针)。与数组不同，链表的元素不需要存储在连续的内存位置，因此可以轻松地扩展或缩减。

使用场景：当需要频繁地插入或删除项目时，尤其是在列表中间链表非常有用，因为无需像在数组中那样移动元素。

代码示例：

classListNode:
def__init__(self, val=0, next=None):
        self.val = val
        self.next = next

classLinkedList:
def__init__(self):
        self.head = None

defappend(self, val):
        new_node = ListNode(val)
ifnot self.head:
            self.head = new_node
return

        current = self.head
while current.next:
            current = current.next
        current.next = new_node

defdisplay(self):
        elements = []
        current = self.head
while current:
            elements.append(str(current.val))
            current = current.next
        print(" -> ".join(elements))

# 使用
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print("Linked List:")
ll.display()

HashMap

哈希映射(HashMap)是一种以键值对形式存储数据的数据结构。它使用一种称为哈希函数的特殊函数将键转换为索引，从而可以非常快速地查找值。

使用场景：当您需要使用唯一键快速访问数据时，HashMap 是完美的选择，例如在数据库中查找信息、缓存结果或统计某个内容出现的次数。

代码示例：

classHashMap:
def__init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)] # 每个桶是一个列表（模拟链表）

def_hash(self, key):
return hash(key) % self.size

defput(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
# 如果key已存在，更新value
for i, (k, v) in enumerate(bucket):
if k == key:
                bucket[i] = (key, value)
return
# 不存在则添加
        bucket.append((key, value))

defget(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
returnNone

# 使用
hm = HashMap()
hm.put("name", "Alice")
hm.put("age", 30)
print(f"HashMap get 'name': {hm.get('name')}")

HashSet

HashSet 是一种只存储唯一元素的集合。与 HashMap 类似，它也使用哈希函数将元素放入不同的桶中，但它只存储值，确保不会出现重复项。

使用场景：当您想要保存一组唯一项并快速检查某项是否存在于该集合中时，HashSet 是完美的选择。

示例代码：

classHashSet:
def__init__(self):
        self.map = HashMap() # 复用上面的 HashMap

defadd(self, key):
        self.map.put(key, True) # Value 不重要，设为 True

defcontains(self, key):
return self.map.get(key) isnotNone

# 使用
hs = HashSet()
hs.add("apple")
hs.add("banana")
hs.add("apple") # 重复添加无效
print(f"HashSet contains 'apple': {hs.contains('apple')}")
print(f"HashSet contains 'orange': {hs.contains('orange')}")

Tree

树是一种由节点构成的层次结构数据结构。每个节点包含一个值，并且可以有多个子节点，从而形成分支。最顶层的节点称为根节点，没有子节点的节点称为叶节点。

使用场景：树状图非常适合显示层级关系，例如文件系统、公司结构和其他组织化的数据。

示例代码：

classTreeNode:
def__init__(self, val):
        self.val = val
        self.left = None
        self.right = None

classBinarySearchTree:
def__init__(self):
        self.root = None

definsert(self, val):
ifnot self.root:
            self.root = TreeNode(val)
else:
            self._insert_recursive(self.root, val)

def_insert_recursive(self, node, val):
if val < node.val:
if node.left:
                self._insert_recursive(node.left, val)
else:
                node.left = TreeNode(val)
else:
if node.right:
                self._insert_recursive(node.right, val)
else:
                node.right = TreeNode(val)

definorder_traversal(self, node):
# 中序遍历：左 -> 根 -> 右 (结果是有序的)
if node:
            self.inorder_traversal(node.left)
            print(node.val, end=" ")
            self.inorder_traversal(node.right)

# 使用
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
print("BST Inorder Traversal:")
bst.inorder_traversal(bst.root)
print() # 换行

Stack

堆叠就像一摞盘子。你只能把盘子放到最上面(推)，需要用到盘子的时候，就把最上面的盘子拿下来(取)。最后放上去的盘子，就是最先取下来的。

使用场景：堆栈用于应用程序中的撤销按钮、编程中管理函数调用或计算数学表达式等场景。

示例代码：

classStack:
def__init__(self):
        self.items = []

defpush(self, item):
        self.items.append(item)

defpop(self):
ifnot self.is_empty():
return self.items.pop() # Python list pop() 移除最后一个元素
returnNone

defpeek(self):
ifnot self.is_empty():
return self.items[-1]
returnNone

defis_empty(self):
return len(self.items) == 0

# 使用
stack = Stack()
stack.push(1)
stack.push(2)
print(f"Stack pop: {stack.pop()}") # 输出 2

Queue

队列是一种先进先出(FIFO)数据结构。这意味着第一个添加到队列中的元素也是第一个被移除的元素——就像人们在售票柜台排队一样。

插入(入队)：将元素添加到队列的末尾(后方) 。

移除(出队)：从队列头部移除元素。

使用场景：队列适用于需要按照到达顺序处理项目或任务的情况，例如：

• 管理打印机队列中的打印作业

• 处理客户服务请求

• 在图中执行广度优先搜索(BFS)

示例代码：

classQueue:
def__init__(self):
        self.items = []

defenqueue(self, item):
        self.items.append(item)

defdequeue(self):
ifnot self.is_empty():
return self.items.pop(0) # 移除第一个元素
returnNone

defis_empty(self):
return len(self.items) == 0

# 使用
queue = Queue()
queue.enqueue("First")
queue.enqueue("Second")
print(f"Queue dequeue: {queue.dequeue()}") # 输出 First

Graph

图是一种数据结构，由顶点(节点)和连接这些节点的边(连接)组成。它用于表示不同实体之间的关系或网络，其中不同实体之间的连接至关重要。

顶点(节点)：表示对象或实体。

边：表示它们之间的关系或联系。

使用场景：图表广泛应用于：

• 计算机网络

• 地图和导航系统

• 推荐系统

示例代码：

classGraph:
def__init__(self):
# 字典：Key是节点，Value是该节点的邻居列表
        self.adj_list = {}

defadd_vertex(self, vertex):
if vertex notin self.adj_list:
            self.adj_list[vertex] = []

defadd_edge(self, v1, v2):
# 无向图：两个方向都要添加
if v1 notin self.adj_list: self.add_vertex(v1)
if v2 notin self.adj_list: self.add_vertex(v2)

        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)

defshow_graph(self):
for vertex, neighbors in self.adj_list.items():
            print(f"{vertex} -> {neighbors}")

# 使用
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
print("Graph Adjacency List:")
g.show_graph()