数据结构（顺序表）

谈起顺序表，那我们就不得不先来了解一下它的上级概念---线性表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

*线性表的有逻辑结构与物理结构：

逻辑结构：一定是线性的

物理结构：不一定是线性的。

顺序表

概念与结构

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

那么顺序表和数组有什么区别？

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。

我们可以通过日常生活中的具体例子来了解这二者的区别：

数组包含与线性表中，是线性表的底层逻辑。顺序表是数组ProMax.

分类

根据定义方式的不同，顺序表可以分类为静态顺序表与动态顺序表。

静态顺序表

概念：使⽤定⻓数组存储元素

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费。

动态顺序表

按需申请空间，能有效避免空间的浪费（但无法绝对避免浪费）

顺序表的常见问题

• 中间/头部的插⼊删除，时间复杂度为O(N)

• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。

• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200， 我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。