学习笔记之数据结构篇——线性表

     线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列；可以采用顺序存储结构和链式存储结构表示。

线性表的顺序存储结构（顺序表）

顺序表使用一维数组存储数据元素，如下：

顺序表存储结构的优点：

       线性表的顺序存储结构中任意数据元素的存储地址可由公式（LOC(ai) = LOC(ai-1) + C）直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。 也就是说定位操作可以直接实现。  

      高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。

顺序表存储结构的缺点：

数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间

插入与删除运算的效率很低（要移动元素）。

顺序存储结构的线性表的存储空间不便于扩充。

总结：

顺序表的静态特性很好，动态特性很差：

 ① 顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。get()、set()方法时间复杂度是 O(1)。

② 插入和删除操作效率很低。如果在各位置插入元素的概率相同，则有

 

线性表的链式存储结构（链表：单链表，双链表）

 链表是用若干个地址分散的存储单元存储数据元素（存储一个数据元素的存储单元为结点）

    单链表操作的效率分析:isEmpty()的时间复杂度是O(1)，toString()，size()，get(i)，insert(i,x)，remove(i)，search（key），remove（key）等成员方法都要遍历单链表，时间复杂度为O(n）。