python静态链表
时间: 2024-04-21 20:21:28 浏览: 131
静态链表是一种使用数组实现的链表结构,它通过数组中的元素来模拟链表中的节点,并使用一个特殊的指针(游标)来表示节点之间的逻辑关系。静态链表的优点是实现简单,不需要频繁地申请和释放内存空间,但缺点是插入和删除操作比较麻烦,需要手动维护游标指针。
以下是一个简单的Python静态链表的实现示例[^1]:
```python
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
```
阅读全文