数据结构第4讲数组、单链表及双链表

数组：
数组在内存中采用静态分配方式，其存储空间为连续区域。以下为存储数值0、10、20、30、40的数组在内存中的示意图：

数组的优势:

1. 操作便捷，查询速度较高，
2. 具备出色的随机访问能力（可通过下标实现快速定位）
   数组的劣势:
3. 插入与删除操作效率较低（此类操作需伴随数据的迁移）
4. 可能造成内存资源的浪费（由于其存储特性为连续空间，因此在分配数组前必须预先设定容量，若设定不合理，则可能导致内存浪费）
5. 对内存空间的需求较高，需要保证有足够连续的存储区域。
6. 数组容量固定，不具备动态扩展能力

链表是由多个存储数据元素的节点通过指针相互连接而构成的数据结构，因此
链表的优势:

1. 实现了数据元素按顺序进行存储，具有连续性
2. 容量不受限制，具备良好的扩展性
3. 无需预先定义存储规模，可灵活增删元素
   链表的劣势:
4. 不支持随机访问，需从起始节点逐个遍历查找，导致检索效率较低
5. 由于包含大量指针字段，所占用的存储空间相对较大

![image](https://cdl.itadn