第四课：Python数组与链表（动态数据结构的深度探索）

在编程中，数组和链表是两种基础且重要的数据结构，它们各自具有独特的特性和适用场景。本文将深入探讨动态数组的实现原理、链表节点操作以及collections.deque的原理，并通过一个链表反转算法的案例，展示链表操作的实践应用。

一、动态数组实现原理

动态数组（如Python中的列表）是一种可以根据需要自动调整大小的数组。其核心思想是在数组容量不足时，分配一个更大的数组，并将原数组的内容复制到新数组中。这种机制使得动态数组在提供随机访问的同时，也能高效地处理动态增删元素的需求。

动态数组的关键操作

1. 追加元素：当数组容量足够时，直接在末尾添加元素；否则，分配更大的数组并复制元素。
2. 插入元素：在指定位置插入元素，需要移动后续元素以腾出空间。
3. 删除元素：移除指定位置的元素，并将后续元素前移以填补空缺。

Python的列表底层实现类似于动态数组，以下是一个简化的动态数组实现示例（仅用于演示原理，实际Python列表实现更为复杂）：

class DynamicArray:
    def __init__(self):
        # 初始化数组
        self.array = []
        # 初始化数组的容量
        self.capacity = 1
        # 当前数组的元素数量
        self.size = 0

    # 重新对数组的容量和默认值进行处理
    def _resize(self, new_capacity):
        # 根据容量生成新的数组
        new_array = [None] * new_capacity

        # 把现有数组中的数据拷贝到新数组中
        for i in range(self.size):
            new_array[i] = self.array[i]

        # 重置数组和容量数据
        self.array = new_array
        self.capacity = new_capacity + 1

    def append(self, item):
        # 如果当前当前数组的元素数量和容量不对称，那就容量容器
        if self.size != self.capacity:
            # 容量+1来支持当前数据存储
            self._resize(self.size + 1)

        self.array[self.size] = item
        self.size += 1

    def __getitem__(self, index):
        if 0 <= index < self.size:
            return self.array[index]
        raise IndexError('Index out of bounds')

    def __len__(self):
        return self.size


# 示例使用
arr = DynamicArray()
arr.append(1)
arr.append(2)
print(arr[0])
print(len(arr))

二、链表节点操作

链表是一种由节点（Node）组成的数据结构，每个节点包含数据域和指向下一个节点的指针。链表的主要优点是插入和删除操作的高效性，但随机访问性能较差。

链表节点类定义

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

链表的基本操作

1. 追加节点：在链表末尾添加新节点。
2. 插入节点：在指定位置插入新节点。
3. 删除节点：移除指定位置的节点。
4. 遍历链表：访问链表中的每个节点。

三、collections.deque原理

collections.deque是Python标准库提供的一个双端队列实现，它基于双向链表，支持在两端高效地添加和删除元素。deque的设计使得其性能优于列表在头部和尾部的插入和删除操作，适用于需要频繁在两端操作的场景。

deque的关键特性

1. 双端操作：支持在两端添加和删除元素，时间复杂度为O(1)。
2. 线程安全：对deque的并发访问是安全的，但修改操作不是原子的。
3. 动态大小：deque会根据需要自动调整其内部存储结构的大小。

四、链表反转算法案例

链表反转是一个经典的算法问题，它要求将链表的节点顺序完全颠倒。以下是一个迭代实现的链表反转算法：

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next  # 暂存下一个节点
        current.next = prev       # 反转当前节点的指针
        prev = current            # 移动prev和current指针
        current = next_node
    return prev  # 新的头节点是原链表的尾节点
 
# 辅助函数：打印链表
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> ")
        current = current.next
    print("None")
 
# 创建链表 1 -> 2 -> 3 -> None
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3
 
print("Original linked list:")
print_linked_list(node1)
 
# 反转链表
reversed_head = reverse_linked_list(node1)
 
print("Reversed linked list:")
print_linked_list(reversed_head)

输出结果

Original linked list:
1 -> 2 -> 3 -> None
Reversed linked list:
3 -> 2 -> 1 -> None

结语

数组和链表是编程中不可或缺的数据结构，它们各自具有独特的优势和适用场景。动态数组通过自动调整大小提供了高效的随机访问和动态增删能力，而链表则以其灵活的插入和删除操作见长。collections.deque作为双端队列的实现，为需要在两端高效操作的场景提供了便利。通过链表反转算法的案例，我们展示了链表操作的实际应用。理解这些数据结构的原理和操作，对于编写高效、可维护的代码至关重要。

关注我！！🫵 持续为你带来Python算法相关内容。