1. 数组

1.在内存中，数组是一块连续的区域 
2.数组需要预留空间

在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低 
ps：数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小（在运行阶段是不允许改变的）

3.在数组起始位置处，插入数据和删除数据效率低。

插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移 
删除数据时，待删除位置后面的所有元素都需要向前搬移

4.随机访问效率很高，时间复杂度可以达到O(1)

因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了

5.数组开辟的空间，在不够使用的时候需要扩容，扩容的话，就会涉及到需要把旧数组中的所有元素向新数组中搬移 
6.数组的空间是从栈分配的

2. 链表

1.在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续 
2.链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址

每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据

3.查找数据时效率低,时间复杂度为O(N)

因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)

4.空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高 
5.任意位置插入元素和删除元素效率较高，时间复杂度为O(1) 
6.链表的空间是从堆中分配的

3. 对比

数组 : 
优点 : 
      1. 随机访问性强，查找速度快，时间复杂度为O(1)
缺点 : 
      1.头插和头删的效率低，时间复杂度为O(N) 
      2.空间利用率不高 
      3.内存空间要求高，必须有足够的连续的内存空间 
      4.数组空间的大小固定，不能动态拓展
链表: 
优点:
      1.任意位置插入元素和删除元素的速度快，时间复杂度为O(1) 
      2.内存利用率高，不会浪费内存 
      3.链表的空间大小不固定，可以动态拓展
缺点: 
      随机访问效率低，时间复杂度为O(N)

4. 总结

简单的对比过后基本上就可以了解数组已经链表的应用场景了. 不再赘述, 那么为什么会产生这样的结果呢?
上面的说明已经简明的阐述了原因, 总结一下

数组 : 
    想要创建必须开辟出一段内存, 这段内从要求在初始化时就需要指定. 
这样就很容易的可以开辟出一段连续的空间, 当我们访问的时候, 由于空间是连续的, 
当我们找到这个数组的内存位置时, 就可以通过简单的计算, 找到我们需要查找的角标的数据. 
就好比我们大学时候住的宿舍, 一个班的同学挨着住, 只要记住一个班级第一个房间号, 就可以找到所有人. 想要找谁很容易, 往后直接数房间敲门就可以了.

那么链表呢 : 
    链表分成单边链表,双端链表,循环链表. 其实原理差不多. 就是通过记住链表中别的元素的内存地址, 从而让链表的元素之间产生关联性, 所以, 链表的内存是非连续的. 就好比我们毕业了, 大家住在天南海北, 想要把人找全就只能通过手机号了, 遍历起来自然效率很低


插入数据效率对比.
数组 : 由于数组的内存地址是连续的, 最坏的情况, 就是在头部插入数据, 这时, 必须将数组的每个元素向后移动一个位置, 确保空间连续,再向头部插入数据.时间复杂度 O(n)
链表 :  由于链表中的每个元素都记着其他元素的内存地址, 查入数据就很好理解了, 只要改变插入位置前后的两个指针的指向即可, 操作相比于数组简单很多, 时间复杂度下降到 O(1)

所以插入效率上 链表才明显大于数组!!

5. 如何自己实现一个链表

由于网上的例子很多, 代码就不贴了. 总结一下实现原理

1. 实现一个链表类
2. 该链表类中需要有一个内部类(或者外部类无关紧要)
  该类中至少要有三个成员变量
  2.1 上一个元素的地址
  2.2 下一个元素的地址
  2.3 存储的数据
3. 实现插入 删除 遍历等方法
  3.1 插入 : 插入元素是, 如果是第一个元素无需操作, 从第二个元素开始, 遍历到需要的位置, 每当一个元素被加进来, 
        将此元素的指针传递给上一个元素下一个地址, 将上一个元素的指针给此元素的上一个地址, 以此类推
  3.2 删除: 
        删除一个元素, 同样需要遍历到相应的位置, 然后将需要删除的元素的的两个指针断开,
        将前一个元素的后一直指针指向当前元素的后一个元素, 
        将当前元素的后一个元素的前指针指向当前元素的前一个元素, 那么当前元素就被剔除出了这个链表.
  3.3 遍历 :
        遍历链表需要找到链表的第一个元素, 然后通过后指针拿到下一个元素以此类推

其实原理很简单, 到这基本上也就看明白了. 其中有一个地方有点不好理解, 我们一般在创建数组的时候都会指定一个数组的大小得到一个对象.
并且我们添加元素的时候将某个元素添加到了数组对象中. 那链表呢?  我们好像并没有通过一个类似容器的东西存储我们添加进来的元素.
这其实也就是链表的核心, 我们每添加一个元素的时候, 都要 new 一个带有前后指针的对象, 
这个对象被创建后会被系统分配到内存中的某一位置. 也就实现了内存的散列排布. 👌