首先,我们都知道数组和数组列表的随机访问和迭代操作是很快的,但是他们两个都有一个重大的缺陷：增加一个元素或者删除一个元素的开销很大。原因是为什么呢

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)—即每个对象都还存放这前驱的引用

 
 
 

数组与链表的优缺点；

数组: 

优点：使用方便 ，查询效率 比链表高，内存为一连续的区域 

缺点：大小固定，不适合动态存储，不方便动态添加 

链表： 

优点：可动态添加删除 大小可变 ，内存可能是不连续内存，链式存储。 

缺点：只能通过顺次指针访问，查询效率低

链表和数组的本质差异

1 在访问方式上 

数组可以随机访问其中的元素 

链表则必须是顺序访问，不能随机访问 

2 空间的使用上 

链表可以随意扩大 

数组则不能

从CPU的角度
CPU 寄存器 – immediate access (0-1个CPU时钟周期) 

CPU L1 缓存 – fast access (3个CPU时钟周期) 

CPU L2 缓存 – slightly slower access (10个CPU时钟周期) 

内存 (RAM) – slow access (100个CPU时钟周期) 

硬盘 (file system) – very slow (10,000,000个CPU时钟周期)
各级别的存储器速度差异非常大，CPU寄存器速度是内存速度的100倍！ 这就是为什么CPU产商发明了CPU缓存。 而这个CPU缓存，就是数组和链表的区别的关键所在。
CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取 每个元素的时间只要3个CPU时钟时间。而链表的节点分散在堆空间里面，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。 这样算下来，数组访问的速度比链表快33倍！ （这里只是介绍概念，具体的数字因CPU而异）
总结一下， 各种存储器的速度差异很大，在编程中绝对有必要考虑这个因素。 比如，内存速度比硬盘快1万倍，所以程序中应该尽量避免频繁的硬盘读写；CPU缓存比内存快几十倍，在程序中尽量多加利用。
CPU性能衡量参数-主频，MIPS，CPI，时钟周期，机器周期，指令周期 

1，主频
主频 = 时钟频率，它是指CPU内部晶振的频率，常用单位为MHz，它反映了CPU的基本工作节拍;
时钟频率又称主频，它是指CPU内部晶振的频率，常用单位为MHz，它反映了CPU的基本工作节拍;
2，时钟周期
时钟周期 t =1/ f; 主频的倒数
3，机器周期
机器周期 = m*t ;一个机器周期包含若干个时钟周期
4，指令周期
指令周期 = m*t*n; 执行一条指令所需要的时间，一般包含若干个机器周期
5，CPI
CPI = m*n; 平均每条指令的平均时钟周期个数
指令周期 = CPI×机器周期 = n（CPI=n）×m×时钟周期=nm/主频f, 注意指令周期单位是s或者ns，CPI无量纲
参考：https://en.wikipedia.org/wiki/Cycles_per_instruction
6，MIPS(MillionInstructions Per Second）
MIPS = 每秒执行百万条指令数 = 1/（CPI×时钟周期）= 主频/CPI
MFLOPS 每秒百万浮点运算次数。
表示秒钟所能执行的指令条数，对于微型计算机可用CPU的主频和每条指令的执行所需的时钟周期来衡量。
 

首先这句话成立的前提下是在ArrayList和其他底层使用数组的集合中才成立，因为就数组本身而言不存在增加和删除，数组一旦创建，长度不能再变，然而增加元素会使数组长度+1，删除元素会使数组长度-1，那么ArrayList是如何使数组的长度“发生变化”的呢，其实当要增删元素时，ArrayList会把数组进行扩容和缩容，从而达到使数组长度变化的效果，但是其实扩容缩容前的数组和扩容缩容后的数组不是同一个数组，扩容缩容后会重新创建了一个数组，然后再把这个新的数组重新赋值给ArrayList底层维护的旧数组，这其实是调用了一个常用的数组工具类Arrays里面的copyOf方法实现的。



那么，如果我们每次添加元素时，底层都只把数组的长度+1，然后把新的数据添加进去，调用Arrays工具类复制一个新数组，这样如果频繁增加的话，岂不是会在创建数组上消耗一部分时间？所以，数组每次扩容时，都会根据一定的算法计算出所需要的长度，多预留几个容量来减少数组在扩容上的时间。

至于为什么增删慢，你可以这样想，数组是一片连续的内存空间，如果你想在特定的位置添加一个元素，那后面的元素都要往后挪；想删除一个元素，后面的元素都要往前挪，这个过程就很耗时。

 



比如我们想删除下标为2的元素，下标从3开始（包含）的元素都得往前挪动。

在下标2和下标3中间添加一个元素，那下标3开始（包含）的元素都要往后挪动，挪动后原来的下标3就变成下标4了，后面以此类推