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