ArrayList和LinkedList的底层代码实现思想
ArrayList是Java众多集合类中的一个,实现List接口,List的父接口是Collection。ArrayList底层的数据结构是线性表中的顺序表,底层是一个长度可以动态增长的数组。数组有很多缺点,ArrayList弥补了数组的缺点。
源码:
1)transient Object[] elementData;,是一个数组的引用,用来指向底层数组;private int size;用来表示ArrayList中真实元素的个数,每次增加和删除元素size的值都要变化。
2)public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,java.io.Serializable{} 这三个接口都没有方法。
3)数组默认长度:JDK 1.7中 new ArrayList()>>>this(10);JDK 1.8中 new ArrayList(),数组的长度是0。第一次添加元素时扩容。
4)当数组已经满时,默认每次扩容为原来的50%;使用了位运算。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
如果扩容50%的空间不足以存放元素,就扩容为所添加元素的最小容量。
5)iterator();ArrayList中提供了一个内部类:Itr implements Iterator,实现了其中的hasNext()、next()等方法。
基本思路:有一个索引/指针,初始执行第一个元素,next()时指向下一个元素,hasNext()判断是否等于size。
优缺点:
数组的优缺点决定了ArrayList的优缺点,数组按索引查询最快,添加删除元素都要大量移动元素,效率很低。ArrayList不仅按索引查询速度快,而且实现了长度的动态变化;但是缺点也很明显,即删除和添加效率低。按内容查找要逐个比较,效率低下。
综上所述,在添加删除操作多的时候不建议使用ArrayList;遍历时,按照索引随机获取某一元素操作多的时候建议使用ArrayList。
Vector是早期版的ArrayList,线程安全,效率低,每次扩容100%。
LinkedList底层是双向链表,优缺点和数组正好相反。
最新文章
- [深度优先搜索] POJ 3620 Avoid The Lakes
- 关于jQuery中环境配置中的问题
- jQuery小节
- Android开发--Layout元素
- cheat-linux命令行实用助记工具
- Spring Aspect 用法略讲
- 【2017-05-03】winform打印控件、事件对象和事件数据、MDI窗体容器
- React Native编译器的配置以及基础知识
- 基于Nginx服务器和iOS9的HTTPS安全通信
- C# Task.Run 和 Task.Factory.StartNew 区别
- Spring Bean的生命周期,《Spring 实战》书中的官方说法
- 环境配置 jupyter代码自动补全
- Spring3 (事务管理)
- 关于Eclipse新建Dynamic Web Projecj默认未创建web.xml的问题
- [转]FTP命令字和响应码解释
- 2018.11.08 UVA11021 Tribles(概率dp)
- 变动事件_DOM2级的变动事件(mutation)
- Java多线程1:进程和线程的区别
- Linux用户及用户组管理命令
- QT开发之旅三串口设备调试工具
热门文章
- Python语法之垃圾回收机制
- 【Layui】当Layui数据表格和Layui下拉框组合时发生的问题
- [Go] 使用读写锁对map资源进行安全处理
- 【leetcode】1247. Minimum Swaps to Make Strings Equal
- (转)CSS定义字体间距 字体行与行间距
- 在$scope中变量和方法的使用
- Understanding the Transform Function in Pandas
- C++入门经典-例6.3-字符串之未使用字符串结束符“\0”和使用字符串结束符“\0”的区别
- SpringMVC配置多个自定义拦截器
- Python学习笔记:类