首先,我们都知道数组和数组列表的随机访问和迭代操作是很快的,但是他们两个都有一个重大的缺陷：增加一个元素或者删除一个元素的开销很大。原因是为什么呢
 1.数组是一个有序列表 ，数组是在连续的位置上面储存对象的应用。当我们删除某一个元素的时候在他后面的元素的索引都会左移 举个例子:
 
Public class Test(){
   public static void main (Stirng[args]){
       List<String> list = new ArrayList<String>();
       list.add("a"); //0
       list.add("b"); //1
       list.add("c"); //2
       list.add("d"); //3
       list.add("e"); //4
       list.add("f"); //5
       //我们把索引为2的元素删掉
       list.remove(2);
       //然后我们在输出一下 就会发现原来索引为2的元素"c"在被删除后 原来的索引3的元素前移 
        System.out.println(list.get(2));
        System.out.println(list.get(3));
        System.out.println(list.get(4));
        //输出的结果为 d e f
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
如果感觉还不够清晰的话 我们来画个图：
 
 增加同理，但是索引是右移的
 
在java中还有一个数据结构—链表(LinkedList)解决了这个问题,链表存放对象是放入到一个单独的链接(link)中，链接中还存放这下一个链接的引用，在java语言设计中链表都是双向链接(Double linked)—即每个对象都还存放这前驱的引用
 ————————————————
 版权声明：本文为CSDN博主「小林带程序猿」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 原文链接：https://blog.csdn.net/weixin_46070645/article/details/106048143

首先,我们都知道数组和数组列表的随机访问和迭代操作是很快的,但是他们两个都有一个重大的缺陷：增加一个元素或者删除一个元素的开销很大。原因是为什么呢
 1.数组是一个有序列表 ，数组是在连续的位置上面储存对象的应用。当我们删除某一个元素的时候在他后面的元素的索引都会左移 举个例子:
 
 Public class Test(){
   public static void main (Stirng[args]){
       List<String> list = new ArrayList<String>();
       list.add("a"); //0
       list.add("b"); //1
       list.add("c"); //2
       list.add("d"); //3
       list.add("e"); //4
       list.add("f"); //5
       //我们把索引为2的元素删掉
       list.remove(2);
       //然后我们在输出一下 就会发现原来索引为2的元素"c"在被删除后 原来的索引3的元素前移 
        System.out.println(list.get(2));
        System.out.println(list.get(3));
        System.out.println(list.get(4));
        //输出的结果为 d e f
   }
 }
 
如果感觉还不够清晰的话 我们来画个图：
 增加同理，但是索引是右移的
 
在java中还有一个数据结构—链表(LinkedList)解决了这个问题,链表存放对象是放入到一个单独的链接(link)中，链接中还存放这下一个链接的引用，在java语言设计中链表都是双向链接(Double linked)—即每个对象都还存放这前驱的引用

首先这句话成立的前提下是在ArrayList和其他底层使用数组的集合中才成立，因为就数组本身而言不存在增加和删除，数组一旦创建，长度不能再变，然而增加元素会使数组长度+1，删除元素会使数组长度-1，那么ArrayList是如何使数组的长度“发生变化”的呢，其实当要增删元素时，ArrayList会把数组进行扩容和缩容，从而达到使数组长度变化的效果，但是其实扩容缩容前的数组和扩容缩容后的数组不是同一个数组，扩容缩容后会重新创建了一个数组，然后再把这个新的数组重新赋值给ArrayList底层维护的旧数组，这其实是调用了一个常用的数组工具类Arrays里面的copyOf方法实现的。
 
 
那么，如果我们每次添加元素时，底层都只把数组的长度+1，然后把新的数据添加进去，调用Arrays工具类复制一个新数组，这样如果频繁增加的话，岂不是会在创建数组上消耗一部分时间？所以，数组每次扩容时，都会根据一定的算法计算出所需要的长度，多预留几个容量来减少数组在扩容上的时间。
 
至于为什么增删慢，你可以这样想，数组是一片连续的内存空间，如果你想在特定的位置添加一个元素，那后面的元素都要往后挪；想删除一个元素，后面的元素都要往前挪，这个过程就很耗时。
 
 
 
 
比如我们想删除下标为2的元素，下标从3开始（包含）的元素都得往前挪动。
 
在下标2和下标3中间添加一个元素，那下标3开始（包含）的元素都要往后挪动，挪动后原来的下标3就变成下标4了，后面以此类推

查询
 1、数组是具有相同数据型的数据，并且有一定的顺序，数组在内存中的地址是连续相邻的。而链表在内存中是散列存放的。
 
2、CUP缓存会把一片连续的内存空间读入。因为数组结构是连续的内村地址，所以数组全部或者部分元素被连续被存在CPU缓存里面，而链表的节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，而缓存的速率要比内存快。
 
3、CPU --》寄存器–》缓存 --》内存
 
    cpu 取数据，处理数据，都要放到寄存器中处理（存放指令），缓存就是吧内存中提取的数据暂时保存在里面。

    如果寄存器要获取内存中同一位置的数据，就从缓存中获取，如果寄存器获取的不是同一个内存地址的数

    据（或者获取的内存地址缓存中不存在），就从内存中查找获取 
 
从上述比较中，我们可以看出数组的查询，要比链表的快
 
插入&删除
 1.数组的中间插入（或删除）一个元素，那么这个元素后的所有元素的内存地址都要往后（前）移动（数组的内存地址是连续的），对最后一个元素插入（或删除）时才比较快，而链表不需要改变内存的地址，只需要修改节点的信息即可（包括指针指向，节点值）。
 
2.链表的扩展性较好，定义数组时所占用的空间大小都是固定的，如果存储满了，无法扩展，只能新建一个更大空间的数组。
 
综上所述我们可以得出：
 
数组大小固定，不适合动态存储，动态添加，内存为一连续的地址，可随机访问，查询较快，
 
而链表大小可变，扩展性强，只能顺着指针的方向查询，速度较慢。
 
数组(Array)
 一、数组特点：
 所谓数组，就是相同数据类型的元素按一定顺序排列的集合；数组的存储区间是连续的，占用内存比较大，故空间复杂的很大。但数组的二分查找时间复杂度小，都是O(1)；数组的特点是：查询简单，增加和删除困难；
 
1.1 在内存中，数组是一块连续的区域
 
1.2 数组需要预留空间
 
  在使用前需要提前申请所占内存的大小，如果提前不知道需要的空间大小时，预先申请就可能会浪费内存空间，即数组的空间利用率较低。注：数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小(在运行阶段是不允许改变的)
 
1.3 在数组起始位置处，插入数据和删除数据效率低。
 
插入数据时，待插入位置的元素和他后面的所有元素都需要向后搬移
 
删除数据时，待删除位置后面的所有元素都需要向前搬移。
 
1.4 随机访问效率很高，时间复杂度可以达到O(1)
 
因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址向后偏移就可以访问到了。
 
1.5 数组开辟的空间，在不够使用的时候需要进行扩容；扩容的话，就涉及到需要把旧数组中的所有元素向新数组中搬移。
 
1.6 数组的空间是从栈分配的。（栈：先进后出）
 
二、数组的优点：
 
随机访问性强,查找速度快，时间复杂度是0（1）
 
三、数组的缺点：
 
3.1 从头部删除、从头部插入的效率低，时间复杂度是o(n),因为需要相应的向前搬移和向后搬移。
 
3.2 空间利用率不高
 
3.3 内存空间要求高，必须要有足够的连续的内存空间。
 
3.4 数组的空间大小是固定的，不能进行动态扩展。
 
链表(ListNode)
 一、链表的特点：
 所谓链表，链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
 
链表:链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：查询相对于数组困难，增加和删除容易。
 
1.1 在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续。
 
1.2 链表中的元素有两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址。
 
   每一个数据都会保存下一个数据的内存地址，通过该地址就可以找到下一个数据
 
1.3 查找数据时间效率低，时间复杂度是o(n)
 
 因为链表的空间是分散的，所以不具有随机访问性，如果需要访问某个位置的数据，需要从第一个数开始找起，依次往后遍历，知道找到待查询的位置，故可能在查找某个元素时，时间复杂度是o(n)
 
1.4 空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高
 
1.5 任意位置插入元素和删除元素时间效率较高，时间复杂度是o(1)
 
1.6 链表的空间是从堆中分配的。（堆：先进先出，后进后出）
 
二、链表的优点
 
2.1 任意位置插入元素和删除元素的速度快，时间复杂度是o(1)
 
2.2 内存利用率高，不会浪费内存
 
2.3 链表的空间大小不固定，可以动态拓展。
 ————————————————
 版权声明：本文为CSDN博主「か陌寒」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 原文链接：https://blog.csdn.net/weixin_43429144/article/details/104298780