ArrayList数组和LinkedList数组的总结

ArrayList数组的总结

数据结构

数据结构是数据存放的一种方式，用来组织数据，使得磁盘或者内存空间更有效率的存放数据。通俗来说就是提供空间的利用率和数据的查找速度。

• 理论：计算机中人们总是在衡量时间和空间的关系，两者只能选其一
• 算法：通俗来讲就是节约时间节约成本去完成一件事

数据结构之线性表

特点：数据连续放置，从逻辑上来说也就是有序的

分为顺序表和链表

LinkedList：地址不连续但是值连续

ArrayList的继承体系

整个框架执行的顺序

1、定义一个空数组

2、调用add方法确保list内部有多余的空间存储arrays.copy()方法

3、初始化数组去最大值默认数组的长度为10

4、避免数组的负增长

ArrayList数组最开始定义长度的好处？

创建数组时最好先定义一个初始化数组避免在add操作是消耗cpu

add方法是调用Arrays.copy方法进行复制时消耗比较大。

总结

List类的 add 方法，包括在末尾添加元素和在指定位置添加元素。通过分析我们知道List集合就相当于一个elemenData数组，该数组可以实现自动扩容。当我们调用add方法的时候实际上的函数调用顺序为：ensureExplicitCapacity(int minCapacity)方法来进行初始化数组，当添加进的元素数量大于elemenData默认容量时会调用grow方法进行扩容（1.5倍扩容），而当扩容过大时会调用hugeCapacity方法进行最大容量（Integer.max_value-8）限制。

LinkedList数组的总结

LinkedList继承体系

Deque:双端队列

可以在队列的两端进行插入和删除，队满的标志：head指针+1=tail指针 eg:1+127= -128溢出

设计模式之适配器模式（通俗理解为插座）

适配器在不影响自身逻辑的情况下还能实现其他对象的方法。

linkedList就是双向链表 它有一个pre前驱和next后继中间存放data

ArrayList和LinkedList的区别：

• ArrayList的底层是顺序表，没有赋值时数组的初始化大小为10 增长因子为0.5，顺序表的存储地址是连续的所以查找比较快，实现增删改的时候需要挪动位置，如果删除的是最后以为元素就不需要挪动位置。ArrayList的空间浪费主要体现在list列表的结尾要预留一定的容量空间，

• LinkedList的底层是链表，链表的存储地址是不连续的每个存储地址通过指针指向，在查找时需要通过指针遍历元素。链表在插入的时候不需要移动其他元素，所以在插入和删除时比较快。而LinkedList的空间花费体现在它的每一个元素都需要消耗相当的空间。

需要移动其他元素，所以在插入和删除时比较快。而LinkedList的空间花费体现在它的每一个元素都需要消耗相当的空间。