9.2.2　顺序表

9.2.2　顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。

其插入删除操作如图9-7所示

注意：

·插入操作：移动元素时，要从后往前操作，不能从前往后操作，不然元素会被覆盖。

·删除操作：移动元素时，要从前往后操作。

顺序表效率分析：

·顺序表插入和删除一个元素，最好情况下其时间复杂度（这个元素在最后一个位置）为O（1），最坏情况下其时间复杂度为O（n）。

·顺序表支持随机访问，读取一个元素的时间复杂度为O（1）。

顺序表的优缺点：

（1）优点：支持随机访问

（2）缺点：插入和删除操作需要移动大量的元素，造成存储空间的碎片。

顺序表适合元素个数变化不大，且更多是读取数据的场合。