数组和链表联系和区别
什么是数据结构？
简单理解就是研究数据的存储方式，合理的组织数据，高效的处理数据。
线性表
-
线性表是最常用数据结构的一种，是数据结构中的逻辑结构
-
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的
-
线性表可以通过数组(顺序存储结构)存储，也可以通过链式存储
-
线性表根据存储结构的不同可以分为顺序表和链表：
-
顺序表为顺序存储的线性表，即用数组描述的线性表就是顺序表
-
链表为链式存储的线性表
-
链表
- 物理存储单元上非连续、非顺序
- 由结点组成，通过指针联系
- 不需要一块连续的内存空间，通过指针将一组零散的内存块串联起来使用
-
由图可以看出每个结点都分配在了非连续的位置，结点通过指针连接到了一起----非连续性。
-
如果要找数据为3的结点(数据为3存储的位置不一定为3)，需要从头开始遍历寻找直到找到为止----地址是无序的–非顺序性。
-
每个元素的查找都要从头开始遍历，时间复杂度为O(n)–n为要查找的元素的节点的位置。
-
-
存储n个结点消耗的空间：n+m=2n。链表的每个节点除了存储数据(n)外还需要存储下一个节点地址-指针域所占存储量m
数组
-
对应链表的连续、顺序
-
需要一块连续的内存空间来存储
-
由图可以看出数组的每个元素都是连续紧邻分配的----连续性。
-
(Java中int型大小占4个字节)，由于元素在内存中是连续紧邻分配的，大小一样–方便查找，查询的速度比链表快。
-
通过下标找到相应的内存地址，从而进行访问。第一个元素的地址+元素下标×字节数。
-
假设初始地址为100，查找第三个元素的地址：100+2×4=108。每个数据的地址都是有序的–顺序性。
-
查找时间复杂度为O(1)：因为通过计算得出地址，通过地址进行访问，无论数据多大，都是计算完直接访问，所以为1。
-
-
存储n个结点消耗的内存：数组的容量n