驾驭Python数据结构与算法：链表、栈、队列与高效排序算法实现

37次阅读

共计 7521 个字符，预计需要花费 19 分钟才能阅读完成。

在编程世界中，数据结构与算法是构建高效、可扩展软件的基石。它们不仅仅是面试的敲门砖，更是解决实际问题的强大工具。对于 Python 开发者而言，尽管 Python 提供了丰富的内置数据类型，但深入理解并能够自己实现核心数据结构与算法，将极大地提升你的编程思维和问题解决能力。

本文将带领你深入探索 Python 中的链表、栈、队列这三大基础数据结构，并详细讲解多种经典的排序算法及其 Python 实现。通过学习，你将不仅掌握这些概念，更能理解它们背后的设计哲学与应用场景。

数据结构是组织和存储数据的方式，它决定了我们如何有效地访问和修改数据。算法则是解决特定问题的一系列步骤。两者相辅相成，选择合适的数据结构能让算法更高效，而优秀的算法则能充分利用数据结构的特性。

Python 以其简洁的语法和丰富的库闻名，这使得学习和实现数据结构与算法变得更加直观。掌握它们，你将能够：

编写更优化的代码，提升程序性能。
更好地理解复杂系统的工作原理。
在面对新问题时，有更清晰的思路去设计解决方案。
轻松应对各类技术面试。

链表是一种线性数据结构，与数组不同，它在内存中不必是连续的。链表通过节点（Node）连接起来，每个节点包含两部分信息：数据本身和指向下一个节点的引用（或指针）。

动态大小：在运行时可以根据需要增减节点。
高效插入和删除：在链表的任意位置插入或删除元素，只需修改少量指针，时间复杂度为 O(1)（如果已知待操作节点）。
随机访问效率低：要访问链表中的某个特定元素，必须从头节点开始遍历，时间复杂度为 O(n)。

我们将实现一个简单的单向链表，包含节点类和链表类，支持添加元素和打印链表。

class Node:
    """链表中的节点"""
    def __init__(self, data):
        self.data = data
        self.next = None  # 指向下一个节点的引用

class LinkedList:
    """单向链表"""
    def __init__(self):
        self.head = None  # 链表的头节点

    def is_empty(self):
        """检查链表是否为空"""
        return self.head is None

    def append(self, data):
        """在链表末尾添加新节点"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def prepend(self, data):
        """在链表开头添加新节点"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        """删除链表中第一个匹配给定数据的节点"""
        if self.is_empty():
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head
        while current.next and current.next.data != data:
            current = current.next

        if current.next: # 找到了要删除的节点
            current.next = current.next.next

    def display(self):
        """打印链表所有节点的数据"""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print("->".join(map(str, elements)))

# 示例使用
my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.prepend(5)
my_list.display() # 输出: 5 -> 10 -> 20

my_list.delete(10)
my_list.display() # 输出: 5 -> 20

my_list.delete(5)
my_list.display() # 输出: 20

my_list.delete(30) # 删除不存在的元素
my_list.display() # 输出: 20

查找 (Search): O(n)
插入 (Insertion): O(1) (如果已知插入位置的前一个节点) 或 O(n) (如果需要查找插入位置)
删除 (Deletion): O(1) (如果已知删除节点的前一个节点) 或 O(n) (如果需要查找删除节点)

栈是一种遵循“后进先出”（LIFO – Last In, First Out）原则的线性数据结构。想象一叠盘子，你最后放上去的盘子，总是你最先拿走的盘子。

Push（入栈）：将元素添加到栈顶。
Pop（出栈）：移除栈顶元素并返回。
Peek/Top（查看栈顶）：返回栈顶元素，但不移除。
IsEmpty（判空）：检查栈是否为空。

Python 的内置 list 类型非常适合实现栈，因为 append() 操作在列表末尾添加元素，而 pop() 操作默认移除并返回列表末尾的元素，完美符合 LIFO 原则。

class Stack:
    """基于 Python 列表实现的栈"""
    def __init__(self):
        self._items = []

    def is_empty(self):
        """检查栈是否为空"""
        return not bool(self._items) # 或者 len(self._items) == 0

    def push(self, item):
        """将元素推入栈顶"""
        self._items.append(item)

    def pop(self):
        """移除并返回栈顶元素"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        """返回栈顶元素，但不移除"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def size(self):
        """返回栈中元素的数量"""
        return len(self._items)

    def display(self):
        """打印栈中所有元素 (从栈顶到底部)"""
        print("Stack (Top to Bottom):", self._items[::-1])

# 示例使用
my_stack = Stack()
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)
my_stack.display() # 输出: Stack (Top to Bottom): [3, 2, 1]

print("Stack size:", my_stack.size()) # 输出: Stack size: 3
print("Top element:", my_stack.peek()) # 输出: Top element: 3

popped_item = my_stack.pop()
print("Popped item:", popped_item) # 输出: Popped item: 3
my_stack.display() # 输出: Stack (Top to Bottom): [2, 1]

函数调用栈：程序中函数调用的管理。
表达式求值：例如后缀表达式求值。
撤销 / 重做功能：存储操作历史。
括号匹配：检查表达式中括号是否正确配对。

队列是一种遵循“先进先出”（FIFO – First In, First Out）原则的线性数据结构。想象一个排队的队伍，第一个进入队伍的人总是第一个离开。

Enqueue（入队）：将元素添加到队列尾部。
Dequeue（出队）：移除队列头部元素并返回。
Front/Peek（查看队头）：返回队列头部元素，但不移除。
IsEmpty（判空）：检查队列是否为空。

使用 Python 的 list 实现队列时，如果频繁地在列表开头进行 pop(0) 操作，效率会很低，因为它需要移动所有后续元素。因此，Python 标准库的 collections 模块提供了一个deque（双端队列），它是专门为两端快速添加和删除设计的。

from collections import deque

class Queue:
    """基于 collections.deque 实现的队列"""
    def __init__(self):
        self._items = deque()

    def is_empty(self):
        """检查队列是否为空"""
        return not bool(self._items)

    def enqueue(self, item):
        """将元素添加到队列尾部"""
        self._items.append(item)

    def dequeue(self):
        """移除并返回队列头部元素"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft() # deque 的特有方法，高效移除左端元素

    def front(self):
        """返回队列头部元素，但不移除"""
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self._items[0]

    def size(self):
        """返回队列中元素的数量"""
        return len(self._items)

    def display(self):
        """打印队列中所有元素 (从队头到队尾)"""
        print("Queue (Front to Rear):", list(self._items))

# 示例使用
my_queue = Queue()
my_queue.enqueue("Task 1")
my_queue.enqueue("Task 2")
my_queue.enqueue("Task 3")
my_queue.display() # 输出: Queue (Front to Rear): ['Task 1', 'Task 2', 'Task 3']

print("Queue size:", my_queue.size()) # 输出: Queue size: 3
print("Front element:", my_queue.front()) # 输出: Front element: Task 1

dequeued_item = my_queue.dequeue()
print("Dequeued item:", dequeued_item) # 输出: Dequeued item: Task 1
my_queue.display() # 输出: Queue (Front to Rear): ['Task 2', 'Task 3']

任务调度：操作系统中的进程调度。
广度优先搜索 (BFS)：图遍历算法。
缓冲池：消息队列、打印队列等。

排序算法是将一组数据按照特定顺序（升序或降序）排列的算法。它们是计算机科学中最基本、最重要的一类算法。

时间复杂度：算法运行时间与输入大小的关系。
空间复杂度：算法运行时所需的额外内存空间。
稳定性：如果两个相等元素的相对顺序在排序后保持不变，则称该算法是稳定的。

我们将实现几种经典的排序算法。

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换，也就是说该数列已经排序完成。

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1): # 外层循环控制遍历次数
        swapped = False # 优化：如果没有发生交换，说明已经有序
        for j in range(n - 1 - i): # 内层循环进行比较和交换
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # 交换元素
                swapped = True
        if not swapped:
            break # 如果一趟下来没有发生交换，说明数组已经有序
    return arr

# print("冒泡排序:", bubble_sort([64, 34, 25, 12, 22, 11, 90]))

选择排序的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i # 假设当前元素是最小的
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j # 找到更小的元素，更新最小元素的索引
        arr[i], arr[min_idx] = arr[min_idx], arr[i] # 将最小元素与当前位置交换
    return arr

# print("选择排序:", selection_sort([64, 34, 25, 12, 22, 11, 90]))

插入排序的工作方式像我们整理扑克牌。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度：平均 O(n²)，最好 O(n) (当数组基本有序时)
空间复杂度：O(1)
稳定性：稳定

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n): # 从第二个元素开始遍历
        key = arr[i] # 待插入的元素
        j = i - 1 # 已排序部分的最后一个元素的索引
        while j >= 0 and key < arr[j]: # 从后向前比较
            arr[j + 1] = arr[j] # 将比 key 大的元素向后移动
            j -= 1
        arr[j + 1] = key # 将 key 插入到正确位置
    return arr

# print("插入排序:", insertion_sort([64, 34, 25, 12, 22, 11, 90]))

归并排序是“分治法”的一个典型应用。它将一个大问题分解成若干个小问题，递归地解决这些小问题，然后将小问题的解合并起来形成原始问题的解。

时间复杂度：O(n log n) (最好、平均、最坏都是)
空间复杂度：O(n) (需要额外空间存储合并结果)
稳定性：稳定

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half) # 递归排序左半部分
    right_half = merge_sort(right_half) # 递归排序右半部分

    return merge(left_half, right_half) # 合并已排序的两个半部分

def merge(left, right):
    merged_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged_arr.append(left[i])
            i += 1
        else:
            merged_arr.append(right[j])
            j += 1

    # 添加剩余元素 (如果存在)
    while i < len(left):
        merged_arr.append(left[i])
        i += 1
    while j < len(right):
        merged_arr.append(right[j])
        j += 1
    return merged_arr

# print("归并排序:", merge_sort([64, 34, 25, 12, 22, 11, 90]))

快速排序也是一种分治算法。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度：平均 O(n log n)，最坏 O(n²) (取决于枢轴元素的选择)
空间复杂度：O(log n) (递归栈空间)
稳定性：不稳定

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2] # 选择中间元素作为枢轴 (pivot)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# print("快速排序:", quick_sort([64, 34, 25, 12, 22, 11, 90]))

算法名称	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定