线性表的实现分析

?顺序存储和链式存储的对比：

? 顺序表 链表 空间性能 顺序表的存储空间是静态分布的，需要一个固定长度的数组，因此总有部分数组元素被浪费。 链表的存储空间是动态分布的，因此不会产生空间的浪费。但是需要额外的空间来为每个节点保存引用。 时间性能 顺序表中元素的逻辑顺序和物理存储顺序是保持一致的，因此支持随机读取，在查找、读取方面性能较好。 链表采用链式结构存储数据，因此在插入、删除元素时性能较好。

?

如下图：

class="irc_mut" style="margin-top: 0px; display: block; margin-left: auto; margin-right: auto;">

?

线性表是增强版数组：

?从某种程度上来讲，线性表是数组的加强：

• 线性表的长度可以动态改变，但Java数组的长度是固定的；
• 线性表可以插入元素，数组无法插入元素；
• 线性表可以删除元素，数组无法删除元素，只能将指定元素置为null或者0；
• 线性表可以搜索指定元素的位置，数组一般没有此方法；
• 线性表提供方法来清空所有元素，数组一般没有类似方法

?JDK提供的线性表：

?

?

其中，ArrayList就是顺序线性表，LinkedList就是链式线性表。对于初学者，只要会使用JDK提供的线性表即可，可以查看下相关的源码，对其实现原理有所了解，待小有所成后，可以自己动手编写线性表的实现。

?