java集合框架的底层实现原理及List集合的底层实现原理

前言：

此篇文章讲解ArrayList和LinkedList底层实现原理、for和foreach遍历集合哪个效率会更高一些！

讲讲什么是集合框架？集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

没学集合框架之前我们存储多个数据是采用数组实现的，但是我们要创建数组的话先要初始化数组容量

这个时候我们可以使用到集合框架了 List 集合框架接口：

集合框架结构图

List接口

public interfaceListextendsCollection{}

List接口中存储元素的特点：

List中存储的元素实现类排序，而且可以重复的存储相关元素。

(1)ArrayList：

优点：操作读取操作效率高，基于数组实现的，可以为null值，可以允许重复元素，有序，异步。

缺点：由于它是由动态数组实现的，不适合频繁的对元素的插入和删除操作，因为每次插入和删除都需 要移动数组中的元素。

(2)LinkedList:

优点：LinkedList由双链表实现，增删由于不需要移动底层数组数据，其底层是链表实现的，只需要修改链表节点指针，对元素的插入和删除效率较高。

缺点： 遍历效率较低。HashMap和双链表也有关系。

ArrayList成员变量

LinkeList成员变量

图截的不好，望包涵，手有点抖

聊聊ArrayList和LinkeList的底层数据结构

先谈谈LinkedList底层数据结构

话不多说先上图

-- 具有头节点和尾节点的双链表

-- 附上一张别人的画图(若有侵权请及时联系作者删除)

作者是个手残党画得扭扭曲曲的

双链表是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。所以删除和插入元素只需要修改链表节点指针就可以了，不像ArrayList一样，ArrayList底层使用数组实现的，每一次删除或修改数组都会移动元素。

谈谈ArrayList底层数据结构

ArrayList底层由数组实现，在实例化一个ArrayList时没给予构造函数数组个数参数，集合中的数组默认是10的容量，在调用add方法时如果容量已满，会将数组的容量扩大1.5倍的容量 如图1

如果有兴趣的同学，可以试下实现一个MyArratList，多看看内部实现原理，便更能随心所欲的使用它。

给大家扯扯ArrayList和LinkeList的add添加元素的内部实现

List接口中有有很多的接口方法，如size()、isEmpty()、clear()等等.....，我就不一 一写这么多了。

ArrayList的添加元素方法

1，先从add方法说起，执行add方法里面会先执行 ensureCapacity() 方法，先讲讲它是干嘛的吧！主要是确保数组的容量是否能继续添加元素，未声明集合容量的话，默认是 为10的，所以一当可用容量满后将会把数组容量扩大1.5倍。

2，讲讲ensureCapacity()方法，当(元素数量+1)大于 数组长度时，会将容量扩大1.5倍，先创建一个新数组来存放数据，再扩大数组容量，最后拷贝到 elementData 数组中。

LinkedList的添加元素方法

1，LinkedList底层使用链表实现，实现添加删除元素操作会比ArrayList效率高很多，LinkedList添加只需改变最后节点的指向即可，不会改变或挪动其他的元素。

-- 往链表中添加元素图

使用for循环遍历效率高还是foreach(增强式循环)？

1，for语法

for (int i = 0; i < integers.length; i++) {

System.out.println(intergers[i]);

}

2,foreach 语法

for(Integer in : integers){

System.out.println(in);

}

1，使用for适合循环ArrayLIst以及数组，当大批量的循环LinkedList时程序将会卡死，for适合循环数组结构，通过下标去遍历。

2，使用foreach适合循环LinkedList，使用双链表结构实现的应当使用foreach循环。