ArrayList和LinkedList原理

蔚落 2023-10-17 22:02 37阅读 0赞

总的来说：

当操作是在一列 数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；

当你的操作是在一列数据的前面或中 间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

ArrayList：

ArrayList 使用默认无参数构造函数，底层的Object数组长度默认为10，当长度不够用自动增长0.5倍

源代码：

默认长度10

\[java\] [view plain][] [copy][view plain]

1.  /\*\*
2.   \* Default initial capacity.
3.   \*/
4.  **private****static****final****int** DEFAULT\_CAPACITY = 10;

如果数组长度不够增长0.5倍grow方法

\[java\] [view plain][] [copy][view plain]

1.  **int** newCapacity = oldCapacity + (oldCapacity >> 1);

ArrayList为什么查询快，增删慢？

查询快：

![SouthEast][]

因为数组的内存地址排列是连续的，可以很快找到比如 list.get(100); 第一个元素内存地址是0x98，那么内存地址加100就找到了。

增删慢：

增：

![SouthEast 1][]

我们假设这个数组长度容量为7，现在要再添加一个元素它会怎么做呢？

增加元素时，先检测数组长度是否够用，如果底层Object数组长度不够，增加0.5倍的长度，形成一个新的Object数组，并将之前的数组元素copy到新的数组里面。

删：

![SouthEast 2][]

删除慢：当删除里面的其中一个数据时，后面的数据要全部移动一个位置。

LinkedList：

![Center][]

使用链表数据结构实现，特点，增删快，查询慢。

查询慢：元素之前内存地址不连续，只能挨个挨个遍历查找

增加：

![SouthEast 3][]

插入数据时，只需要改变内存地址的指向；

![SouthEast 4][]

将和它有关系的内存地址指向删除掉，没人指向它，它就成为了垃圾对象。

[view plain]: https://blog.csdn.net/baidu_19473529/article/details/55253582#
[SouthEast]: https://img-blog.csdn.net/20170216113601116?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20170216113746169?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20170216114237349?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[Center]: https://img-blog.csdn.net/20170216114442492?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[SouthEast 3]: https://img-blog.csdn.net/20170216114536119?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20170216114746746?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYmFpZHVfMTk0NzM1Mjk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast