顺序表和链表的区别

参考：线性表和链表的区别

注：参考文中的‘线性表’准确的说应该是’顺序表‘，链表与顺序表都是线性表。

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

链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

顺序表在内存中是一块连续的存储空间；如：一个表中的内容是：【1，2，3】则它在内存中可能是如下存储的：
1
2
3
通过这个结构可以看出，只要知道了第一个元素在内存中所在的位置。就可以很容易的知道其他元素的位置。因为每一个元素占的空间是一样的。所以，如果我们知道第一个元素：1在内存号：1000；而每一个元素占8个内存空间；则第二个元素：2所在的内存空间为：1000 + 8；依此类推。所以，在顺序表中访问数据元素是很快的。它的缺点也正因为它是连续的一块内存空间。所以，如果往中间添加或在中间删除一个元素。都要移动其他的元素。如：我在最前面加入一个元素：0.则1，2，3都要往后移一位；或，我将1删除，则2，3都要往前移一位；估算一下运算时间：在第一个元素处添加，要移动所有的元素。花费的时间是添加元素的时间 X 加上移动其他元素的时间：N，在最后面加元素不需要移动任何元素。时间仅为添加元素的时间： X .所以添加元素要的平均时间是 (N + 2X)/2；删除操作和添加操作是一样的；所以，当改变顺序表长度的时间，它会在移动元素上花费大量的时间。
在JAVA中。顺序表的最直接应用就是数组：Array;但Array在初始化的时间必须规定其元素长度。如：
int[] arr = new int[5];必须规定其长度，但内容可以不填。它要知道长度，然后去开辟一块内存空间。一旦数组初始化，它就不能往里面添加，删除元素了。但可以将元素值设为空；
如果需要扩充数组长度，JAVA 提供了另一个类：ArrayList.
JAVA中所有的虚拟出来的数据容器都继承自接口：Collection;ArrayList继承自：List.而List又继承了Collection;Collection提供了几种基本方法：add();clear();remove();size();toArray();iterator()等；
ArrayList提供了较灵活的用法：
List<Long> lists = new ArrayList<Long>();
ArrayList<Long> lists = new ArrayList<Long>();
上面的用法使用了泛型。而且lists并未规定长度。它可以在程序中自由扩充。但这一特点就意味着它可能在运行时因为将内存耗尽而出现问题；数组是规定长度的，所以如果内存不足，你根本初始化不了，一旦初始化了就可以随便用。
ArrayList,和Array都是数据结构中顺序表的实现。
链表；
链表的存储是链式的，它不强迫数据是在一片连续的内存空间；它可以是分散存储的。所以，它的每个元素除了包括元素的值外，还要包括一些额外的信息；如：它的下一个元素在什么地方。
最基本的链式存储中的元素包括两部分：元素值和下个元素的位置；
可以如下理解：
内存空间： 值 下一元素空间
50 46 空
.
100 10 200
.
.
200 15 50
当存在这个链的时候，我们肯定知道链头在哪，我们假设上面链头在内存空间100处。则上述的链表表示的数据形式是：[10,16,46]；知道了链头在哪里，如果要查找其他元素。必须从链头开始，依次查找下一内存空间里的值；所以查找用的时间为N/2；显然就比顺序表慢了。如果是删除或添加元素。例，现在要将：[10,16,46]改成：[10,16,30,46];我们要做的是，将30放在内存中，假设它的内存地址是500；然后再将16这个值的下一元素空间的值改成500;并将30这一数值对应的下一元素空间值改成50(46这个值对应的内存空间);看起来要比顺序表简单。但细看会发现：要添加或删除一个元素，必须知道它的上一个元素是谁；但现在数据中存储的只有某一无线的下一个元素。如果要找上一个元素，则又要从链头开始遍历。这会浪费大量时间，还不如顺序表好用。所以这时候出现了另一链表:双链表.它和基本链表不同的是，每个元素里不但存储了下一个元素的空间，还存储了上一个元素的空间。
JAVA 中对链表的实现是通过类：LinkedList 来实现的。LinkedList 最终也是上溯到了Collection接口；
所以它也有上面说的诸如：add().clear()等方法。