Python静态链表详解（手把手教你用数组模拟链表结构）

什么是静态链表？

静态链表是一种用数组来模拟链表结构的数据结构。它不像动态链表那样使用指针连接节点，而是通过数组下标（索引）来表示“指针”关系。每个数组元素包含两部分：

• data：存储实际数据；
• next：存储下一个节点在数组中的下标（即“指针”）。

这种结构特别适合在不支持指针的语言（如早期BASIC）或嵌入式系统中使用。虽然Python本身支持动态链表，但理解静态链表有助于深入掌握数据结构的本质。

为什么学习Python静态链表？

学习静态链表实现有以下好处：

• 加深对链表逻辑的理解；
• 掌握如何用数组模拟指针；
• 为算法竞赛或面试题打基础（有些题目明确要求用静态方式实现）；
• 提升对Python数据结构的灵活运用能力。

静态链表的基本结构设计

我们可以用一个列表（list）来表示整个静态链表，其中每个元素是一个字典，包含 data 和 next 字段。

# 示例：静态链表节点结构node = {    'data': None,   # 存储数据    'next': -1      # 下一个节点的索引，-1 表示空（NULL）}

整个静态链表就是一个由多个这样的节点组成的列表。

完整实现：Python静态链表类

下面是一个完整的静态链表实现，包含初始化、插入、删除和遍历功能：

class StaticLinkedList:    def __init__(self, size=100):        """        初始化静态链表        :param size: 预分配的节点数量        """        self.size = size        # 创建节点池，每个节点包含 data 和 next        self.nodes = [{'data': None, 'next': i + 1} for i in range(size)]        self.nodes[-1]['next'] = -1  # 最后一个节点的 next 为 -1                self.head = -1      # 头节点索引，初始为空        self.free_head = 0  # 空闲链表头，指向第一个可用节点    def _alloc_node(self):        """从空闲链表中分配一个节点"""        if self.free_head == -1:            raise Exception("No free node available")        node_index = self.free_head        self.free_head = self.nodes[node_index]['next']        return node_index    def _free_node(self, index):        """释放节点，归还到空闲链表"""        self.nodes[index]['next'] = self.free_head        self.free_head = index    def insert_at_head(self, data):        """在链表头部插入新节点"""        new_index = self._alloc_node()        self.nodes[new_index]['data'] = data        self.nodes[new_index]['next'] = self.head        self.head = new_index    def delete_by_value(self, data):        """删除第一个值为 data 的节点"""        prev = -1        curr = self.head        while curr != -1:            if self.nodes[curr]['data'] == data:                if prev == -1:                    self.head = self.nodes[curr]['next']                else:                    self.nodes[prev]['next'] = self.nodes[curr]['next']                self._free_node(curr)                return True            prev = curr            curr = self.nodes[curr]['next']        return False    def display(self):        """遍历并打印链表"""        result = []        curr = self.head        while curr != -1:            result.append(str(self.nodes[curr]['data']))            curr = self.nodes[curr]['next']        print(" -> ".join(result) if result else "Empty list")

使用示例

现在我们来测试一下这个静态链表：

# 创建一个容量为10的静态链表sll = StaticLinkedList(size=10)# 插入数据sll.insert_at_head(30)sll.insert_at_head(20)sll.insert_at_head(10)# 打印链表sll.display()  # 输出: 10 -> 20 -> 30# 删除节点sll.delete_by_value(20)sll.display()  # 输出: 10 -> 30

总结

通过本教程，你已经掌握了如何用Python实现静态链表。虽然Python本身支持动态内存分配，但理解静态链表实现能帮助你更好地应对算法题、面试题，以及在资源受限环境下的编程挑战。希望这篇链表教程对你有所帮助！

关键词回顾：Python静态链表、静态链表实现、Python数据结构、链表教程