写一个使用链式存储的线性表的增删
时间: 2024-10-12 14:16:31 浏览: 4
链式存储的线性表,也叫链表,是一种动态数据结构,它的每个元素称为节点,包含两个部分:数据域和指针域。在链表中插入和删除操作相对于数组来说更方便,因为不需要预先知道表的长度。
**插入操作**:
1. 创建新节点:首先创建一个新的节点,并将要插入的数据存入该节点的数据域。
2. 链接节点:如果链表为空,则新节点成为头结点;若链表非空,找到最后一个节点,将其指针域指向新的节点,完成插入。
3. 更新头指针:如果新节点就是插入的第一个,那么头指针就指向它。
**删除操作**:
1. 查找节点:需要知道要删除的节点的位置。可以遍历整个链表,直到找到目标节点。
2. 确定前驱节点:记录当前节点的前一个节点,以便后续修改链表结构。
3. 修改链接:删除目标节点,将前驱节点的指针域直接指向目标节点的下一个节点(如果有的话)。
4. 回收资源:如果删除的是头节点,记得更新头指针。
**Python 示例** (仅提供伪代码):
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 插入操作
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
# 删除操作
def delete_node(self, target_data):
current = self.head
if current and current.data == target_data:
self.head = current.next
return
prev = None
while current and current.data != target_data:
prev = current
current = current.next
if current is not None:
prev.next = current.next
```