2.1.2　线性表插入和删除运算

1. 顺序存储结构下的运算

插入元素之前先要移出空位置后再进行插入，删除元素后同样要将删除元素位置后面的所有元素顺序向前移动一个位置。因此，在等概率前提下插入一个元素的平均移动次数为(在n个元素中可插入的位置有n+1个)：

而删除一个元素的平均移动次数为：

2. 链式存储结构下的运算

(1)单链表下的插入运算如图2-2所示，单链表下的删除运算如图2-3所示。

图2-2　单链表插入结点示意图

图2-3　单链表删除结点示意图

(2)双向链表的插入运算如图2-4所示，双向链表的删除运算如图2-5所示。

图2-4　双向链表的插入结点示意图

图2-5　双向链表的删除结点示意图

在线性链表中，在第一个结点前插入一个新结点和删除第一个结点会引起头指针head值的变化。通常在线性链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域无须存储任何信息，头结点的指针指向第一个数据结点。这样做有如下优点：

(1) 由于第一个数据结点的数据被存放入头结点的指针域下，所以在链表的第一个位置上的操作就和在表的其他位置上的操作一致，无须进行特殊处理；

(2) 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理就完全统一了。