首页 > > 程序设计 > Java技术 >

深入理解List集合框架底层原理的实现

2018-06-18 01:49:22来源：未知阅读 ()

深入理解List集合框架

前言：

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

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

int[] arr =new int[10];

现在设置数组默认容量为10，当我们要向数组存储11个数据的话将会抛出

错误提示：提示出错：Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 意思是数组下标越界

这个时候我们就要使用集合框架了 List 集合框架接口：

集合框架结构图

一，List接口

public interface List<E> extends Collection <E>{}

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

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

（1）ArrayList：

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

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

（2）LinkedList:

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

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

ArrayList成员变量

// 版本号，不用管 

    private static final long serialVersionUID = 8683452581122892189L;

    // 数组默认的初始容量 

    private static final int DEFAULT_CAPACITY = 10;

    // 用于创建一个空的实例 

    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 用于保存List数据的数组 

    private transient Object[] elementData;

    // 数组大小

     private int size;

LinkedLIst成员变量：

    // 用于记录集合的数量

    transient int size = 0; 

    // 集合的第一项

    transient Node<E> first;

    // 集合的最后一项

    transient Node<E> last;

二，你肯定会想到为什么LinkedList为什么删除和插入效率高和ArrayList遍历效率高

先看看LinkedList底层使用双链表实现：

双链表图

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

ArrayList的底层实现：

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