3.2-数组与链表

Create by fall on 30 Jan 2022
Recently revised in 17 Apr 2025

数组

线性数据结构，将同类型的元素存储在连续的内存空间，元素在数组中的位置称为索引（index）

访问元素

数组被存储在连续的内存空间，因此，计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引，即可访问该元素

。数组。   1   6   3   2   5
元素索引   0   1   2   3   4
内存地址   00  04  08  12  16

元素长度： 4

在数组中访问元素非常高效，我们可以在 O(1) 时间内随机访问数组中的任意一个元素。

插入元素

数组中的元素是紧挨着的，因此如果想要在数组中间插入一个元素，需要将该元素之后的所有元素都向后移动一位

由于数组长度为固定的，因此插入一个元素必定导致尾部元素丢失。