线性表是一种线性结构，它是具有相同数据类型的n(n>=0)个数据元素组成的有序序列。线性表包括数组和链表

1.数组特点

①.存储空间：连续的内存空间，存储在栈中。

②.可以通过数组下标快速找到值，因为是一段连续的存储空间，所以根据第一个值和数组下标根据公式即可计算出当前需要寻找的值。

③.数组插入和删除效率低，因为数组插入或者删除都需要将当前元素的后面的数据结构进行移动。

2.链表特点

①.存储空间：间断的内存空间，存储在堆中。通过存储的下标来确定下一个元素。

②.通过下标查询效率低，因为是间断的内存空间，只能通过指针得到下一个元素的位置，所以可能需要从第一个开始慢慢往后找。

③.链表插入和删除效率高，因为链表插入和删除只需要修改此元素前一个元素的指针指向此元素，此元素指针在指向后一个元素即可。

区别及优缺点：

• 存储位置：数组将元素在内存中连续存放，而链表中的元素在内存中不是顺序存储的。
• 存储空间：一般情况下，存储相同多的数据，数组占用的内存较少，而链表还需要存储前驱和后继，需要更多的内存。
• 长度的可变性：数组的长度在定义的时候给定，如果存储的数据个数超过数组的初始长度，会发生溢出，而链表的长度可以按实际情况伸缩。
• 按序号查找：按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均时间复杂度为O(n)。
• 按值查找：如果数组是无序的，数组和链表的时间复杂度均为O(n)，如果数组是有序的，使用二分查找可以使时间复杂度降低到O(logn)。
• 插入和删除：数组平均需要移动n/2个元素，而链表只需要修改指针。
• 空间分配：数组在静态存储分配情形下，存储的元素数量有限，在动态存储分配情形下，虽然存储空间可以扩充，但是需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块的连续存储空间，将导致分配失败；而链表中的元素空间只在需要时分配，只要内存有空间就可以分配，操作比较灵活高效。   

上述说的链表是单向链表，还有双向链表和循环链表。

双向链表就是除头和尾的两个元素其他元素都是有上一个指针和下一个指针的

循环链表则是在尾部元素的指针指向第一个元素

如若不清楚可以参考下面几个文档：

数组和链表 - 程序员自由之路 - 博客园

双向链表与单向链表

数组和链表 - 简书

你真的知道数组和链表吗？

你真的知道链表和数组的区别吗？ - 云+社区 - 腾讯云

转载于:https://my.oschina.net/java1314/blog/3038518

在java中，数组定义为一种基本类型，其可以通过下标获取到对应位置的数据。那么这种结构的数据，在内存中是怎么存放的呢？
数组的结构示意图正如上图所示，数组在内存中是一段连续的存储单元，每个数据依次放在每个单元中。分析这种结构，我们可以得出以下几个结论：创建一个数组，必须声明其长度，以在内存中寻找合适的一段连续存储单元。这也意味着数组的大小是固定的，我们无法动态调整其大小。想要获取数组中第i个元素，其时间复杂度是 O(1)，因为可以根据其地址直接找到它。同理修改也是。数组对查询表现一般，要想查找一个元素，需要遍历，时间复杂度为O(n)。因为地址连续，想要在数组中插入一个元素是复杂的，因为从插入位置起，后边的所有元素都需要向后移动一位。同理删除也是，只是移动方向为向前。并且，当数组存满时，就无法继续插入了。因为数组要占据一整块内存，有可能产生许多的碎片，也可能因为找不到合适的内存块，而导致存储失败。总结起来就是：数组大小固定，查找迅速，增删复杂，需要完整的内存块，容易产生碎片。链表链表是一种离散存储结构，其在内存中存储不是连续的，每个数据元素都通过一个指针指向其下一个元素的地址。根据指针域的不同，链表又分为单链表、双向链表、循环链表等，这里我们只分析单链表。示意图如下所示：链表的结构示意图分析这种结构，我们可以得出以下几个结论：声明一个链表时，不需要知道其长度，也不需要连续的内存块，所以其大小可以动态调整。链表的每个元素都分为数据域和指针域，前者是实际存储的数据，后者则指向下一个元素的地址。和数组相比，每个元素需要占用的内存更大了。要获取链表的第 i 个元素变得复杂，因为其地址存放在它上一个元素的指针域里，所以只能从第一个元素起，进行 i 次操作。同理修改也是。链表对查询表现也一般，需要遍历，时间复杂度为O(n)。增加与删除一个元素更方便了，因为没有对内存地址的限制，我们只需要在对应节点合理处理下指针域的值，就可以把一个元素插入链表或者从链表删除。链表对内存的要求很小，只要能够存储下一个数据元素的内存块都可以使用，因此不会造成碎片化。总结起来就是：大小可以动态调整，增删迅速，查找较慢，数据元素所占内存略多，不需要整块内存块，不会造成碎片化。数组与链表的选择通过以上分析，数组和链表对我们影响最大的几点区别在于：数组按位置查找迅速，链表增删方便数组是固定大小，链表可以随时扩充与缩减链表每个元素占据内存略多于数组数组和链表在查询方面表现都比较一般，耗时较长在数据量很小，内容基本固定时，我们选择何种数据结构的影响并不大。但当数据量较大时，如果我们需要对数据进行频繁的插入删除，我们应该选择链表，如果我们需要频繁的获取某个位置的元素，我们应该选择数组。数组与链表并没有明确的优劣之分，根据不同的使用场景进行不同的选择，才是这两种结构使用的最佳方式。