线性表的插入与删除代码
时间: 2024-09-24 12:03:40 浏览: 31
线性表的插入和删除通常涉及到数组或链表这两种基本数据结构的操作。
1. **数组表示的线性表**:
- **插入**:如果要在数组中间位置插入元素,通常需要移动后面的元素到新的位置,这需要O(n)的时间复杂度(n为数组长度)。Python代码示例:
```python
def insert_array(lst, index, value):
lst.insert(index, value)
```
- **删除**:删除指定索引的元素同样可能涉及移动后面的元素,时间复杂度也是O(n)。例如,在Python中:
```python
def delete_array(lst, index):
if index < len(lst):
lst.pop(index)
```
2. **链接列表表示的线性表**:
- **插入**:对于链表,可以在O(1)时间内完成,因为只需修改节点的指针即可。如在单向链表中添加新节点:
```python
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def insert_linked_list(head, index, value):
new_node = Node(value)
if index == 0:
new_node.next = head
return new_node
current = head
for _ in range(index - 1):
current = current.next
new_node.next = current.next
current.next = new_node
```
- **删除**:在链表中删除某个节点也快得多,只需要修改前驱节点的`next`指针,仍然是O(1)。如删除第`index`个节点:
```python
def delete_linked_list(head, index):
if index > 0 and head is not None:
current = head
for _ in range(index - 1):
current = current.next
if current is not None:
current.next = current.next.next
```
阅读全文