线性表的插入与删除代码

线性表的插入和删除通常涉及到数组或链表这两种基本数据结构的操作。

1. **数组表示的线性表**：
- **插入**：如果要在数组中间位置插入元素，通常需要移动后面的元素到新的位置，这需要O(n)的时间复杂度（n为数组长度）。Python代码示例：

     def insert_array(lst, index, value):
         lst.insert(index, value)

- **删除**：删除指定索引的元素同样可能涉及移动后面的元素，时间复杂度也是O(n)。例如，在Python中：

     def delete_array(lst, index):
         if index < len(lst):
             lst.pop(index)

2. **链接列表表示的线性表**：
- **插入**：对于链表，可以在O(1)时间内完成，因为只需修改节点的指针即可。如在单向链表中添加新节点：

     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`个节点：

     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