对ArrayList和LinkedList底层实现原理详解

ArrayList和LinkedList底层实现原理详解 ArrayList 底层实现方式的知识点： 1. ArrayList 底层实现方式：ArrayList 通过数组实现，一旦我们实例化 ArrayList 无参数构造函数默认为数组初始化长度为 10。 2. add 方法底层实现：如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5 倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时，重复该过程。 3. 扩容数组的方法：扩容数组调用的方法是 Arrays.copyOf(objArr, objArr.length + 1)。 4. ArrayList 的扩容机制：是一旦数组超出长度，就开始扩容数组。 LinkedList 底层实现方式的知识点： 1. LinkedList 底层实现方式：LinkedList 底层的数据结构是基于双向循环链表的，且头结点中不存放数据。 2. 节点实例：节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息。 3. 双向链表的结构：双向链表的结构包括头结点、尾结点和中间结点，每个结点都包含前一个节点的位置信息和后一个节点位置信息。 ArrayList 和 LinkedList 的比较： 1. 内存占用：ArrayList 占用内存少于 LinkedList，因为 ArrayList 是基于数组实现的，而 LinkedList 是基于链表实现的。 2. 查询效率：ArrayList 的查询效率高于 LinkedList，因为 ArrayList 可以通过索引直接访问元素，而 LinkedList 需要遍历链表来访问元素。 3. 插入和删除效率：LinkedList 的插入和删除效率高于 ArrayList，因为 LinkedList 只需要改变链表中相应的指针，而 ArrayList 需要移动数组中的元素。 总结：ArrayList 和 LinkedList 是 Java 中两个常用的集合类，它们的底层实现方式不同，ArrayList 是基于数组实现的，而 LinkedList 是基于链表实现的。理解它们的底层实现方式可以帮助我们更好地使用它们。