|
|
| 插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的存储单元。在等概率下平均移动元素的次数分别是
|
|
|
|
|
|
|
| 在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。
|
|
|
| （1）在单向链表中插入节点时，指针的变化情况如下图所示。
|
|
|
|
|
|
|
| （2）在单向链表中删除节点时，指针的变化情况如下图所示。
|
|
|
|
|
|
|
| （3）在双向链表中插入节点时，指针的变化情况如下图所示。
|
|
|
|
|
|
|
| （4）在双向链表中删除节点时，指针的变化情况如下图所示。
|
|
|
|
|
|
|
 注意：以上3图中①为插入运算前的指针走向；②为插入运算后的指针走向；虚线为插入后的指针指向。
|
|
|
