数组(Array)\是一种**线性表**数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
数组下标由0开始
为什么?
数组查找数据时的寻址公式为:start_address + n*data_block_size
。
一方面是按照上述公式,如果下标由1开始,则公式为:start_address + (n-1)*data_block_size
每次寻址时会做一次 n-1
的运算。
另一方面是历史原因,都是从0开始的。
快速查找
根据下标随机查找,时间复杂度为O(1)。
插入、删除慢
插入、删除会导致数组后续元素的后移,时间复杂度为O(n)。