python静态链表

静态链表是一种使用数组实现的链表结构，它通过数组中的元素来模拟链表中的节点，并使用一个特殊的指针（游标）来表示节点之间的逻辑关系。静态链表的优点是实现简单，不需要频繁地申请和释放内存空间，但缺点是插入和删除操作比较麻烦，需要手动维护游标指针。

以下是一个简单的Python静态链表的实现示例[^1]：

class StaticLinkedList:
    def __init__(self, size):
        self.data = [None] * size  # 存储数据的数组
        self.next = [i + 1 for i in range(size)]  # 游标数组，用于维护节点之间的逻辑关系
        self.next[-1] = -1  # 最后一个元素的游标为-1，表示链表的末尾
        self.head = -1  # 头指针，指向链表的第一个节点

    def is_empty(self):
        return self.head == -1

    def is_full(self):
        return self.next == -1

    def insert(self, value):
        if self.is_full():
            print("StaticLinkedList is full")
            return

        new_node = self.next  # 获取一个空闲节点
        self.next = self.next[new_node]  # 更新空闲节点的游标
        self.data[new_node] = value  # 在空闲节点中存储数据

        if self.is_empty():
            self.head = new_node
            self.next[new_node] = -1
        else:
            current = self.head
            while self.next[current] != -1:
                current = self.next[current]
            self.next[current] = new_node
            self.next[new_node] = -1

    def delete(self, value):
        if self.is_empty():
            print("StaticLinkedList is empty")
            return

        prev = -1
        current = self.head
        while current != -1:
            if self.data[current] == value:
                break
            prev = current
            current = self.next[current]

        if current == -1:
            print("Value not found")
            return

        if prev == -1:
            self.head = self.next[current]
        else:
            self.next[prev] = self.next[current]

        self.next[current] = self.next  # 将删除的节点加入空闲节点链表
        self.next = current

    def display(self):
        if self.is_empty():
            print("StaticLinkedList is empty")
            return

        current = self.head
        while current != -1:
            print(self.data[current], end=" ")
            current = self.next[current]
        print()

# 创建一个容量为5的静态链表
static_list = StaticLinkedList(5)

# 插入数据
static_list.insert(1)
static_list.insert(2)
static_list.insert(3)

# 删除数据
static_list.delete(2)

# 显示链表中的数据
static_list.display()

输出结果为：

1 3