一，前言
先来一张Collection集合图。
今天分享一些关于Collection集合中的List，讲真的集合这东西在网上真是老生常谈了。说实话连本人都觉得腻了(哈哈)，但是话又说回来，整个集合体系对于我们实际开发来说是非常重要的，所以还是有必要系统总结下。
不过在此之前先说说两种数据结构，链表和红黑树。
1.1，链表
链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表，那么这里给大家介绍的是单向链表。
简单的说，采用该结构的集合，对元素的存取有如下的特点：
多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。
查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。
增删元素快：
删除元素：只需要修改连接下个元素的地址即可。
1.2，红黑树
红黑树是一种自平衡二叉查找树，是计算机科学领域中的一种数据结构，典型的用途是实现关联数组，存储有序的数据。
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。
红黑树的约束:
红黑树的特点:
速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍。
二，List接口
2.1，简介
java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。
那么List接口有什么特点。
2.2，常用方法
List接口继承Collection接口，因此在父类接口中的方法，List子接口全部都有，并且还增加通过索引的方式操作数据。
public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。public E get(int index) :返回集合中指定位置的元素。public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
public class ListDemo {
public static void main(String[] args) {
// 创建List集合对象
List<String> list = new ArrayList<>();
// 往尾部添加 指定元素
list.add("ABC");
list.add("张三");
list.add("李四");
System.out.println(list);
// add(int index,String s) 往指定位置添加
list.add(1,"DEF");
System.out.println(list);
// String remove(int index) 删除指定位置元素 返回被删除元素
// 删除索引位置为2的元素
System.out.println("删除索引位置为2的元素");
System.out.println(list.remove(2));
System.out.println(list);
// String set(int index,String s)
// 在指定位置进行元素替代（改）
// 修改指定位置元素
list.set(0, "三毛");
System.out.println(list);
// String get(int index) 获取指定位置元素
// 跟size() 方法一起用来遍历的
for(int i = 0;i<list.size();i++){
System.out.println(list.get(i));
}
//还可以使用增强for
for (String string : list) {
System.out.println(string);
}
}
}
三，Array List（JDK8）
Array List底层是基于动态数组实现的，何以动态。在于它是一个可变的数组，根据实际情况它的容量可自动扩充，类似于在C语言中动态申请内存的原理。（题外话：记得有一次面试，面试官问我arraylist是怎么实现的，我说是一个动态数组。然后把他吓一跳，说一句让我想清楚再说。我还以为说错了，接着沉淀5秒钟，就是一个可自动扩容的动态数组）。
其特点是增删慢，查询快。因为是基于数组实现那么就会存在索引，增删就是对数据的更新，导致索引也会发生相应变化。但是存在索引值，所以对于查询数据来说就很快了。如图：
3.1，数组实现
为什么说底层是一个数组，请看源码：
ArrayList在初始化时默认的数组容量为10，源码如下：
3.2，构造方法
1，定义无参构造方法，初始化默认为10的空列表。
2，有参构造，并且自定义初始化容量的大小。
3，将数据类型转换为数组类型。
分析：
1，elementData = c.toArray();将元素转化成数组。
2，判断数组大小是否为0，否则将默认EMPTY_ELEMENTDATA赋值给数组。
3，接着里面的if判断，判断elementData是否成功转换为数组，如果成功则调用Arrays.copyOf方法将元素值，数组大小，及数组类复制值到elementData数组中。
完成以上初始化步骤之后，接着我们可以调用add方法完成数据添加。
3.3，add方法
先介绍没有指定索引的数据添加，请看add源码：
分析：
1，ensureCapacityInternal(size + 1);这个方法是判断在添加数据之前，数组的容量是否够用。这里就看下源码的实现吧。
判断是否要扩容。
说明：
首先size默认为0，然后size+1将参数传过来。判断if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)是不是第一次添加元素，如果是，则选取默认的容量大小10，正式将数组容量初始化为10.接着调用ensureExplicitCapacity(minCapacity);这里是判断是否需要进行扩容。这里我们假设不需要扩容，接着说完add方法最后一步。
2，elementData[size++] = e;最后执行这一步，将元素e添加到elementData数组中，并且大小加1，并完成元素添加。
3.4，扩容机制
上面我们说到在数组不扩容情况下元素是如何进行添加的，再来说说如何进行扩容。接着上面ensureExplicitCapacity(int minCapacity)这个方法，判断如果超出默认容量大小时，便调用grow(minCapacity);方法开始进行扩容。
在这里先指出扩容的机制其实就是数组的复制，创建一个新的数组，将小容量数组的元素复制到容量较大的数组中，以此完成数组的扩容。
接着我们看源码的实现：
分析：
1，获取旧数组的大小。
2，将大小扩大1.5倍。
3，新容量小于参数指定容量，修改新容量。
4，新容量大于最大容量，并指定新容量。
5，调用copyOf进行复制。
完成扩容。
四，线程不安全
Array List是线程不安全的，这点很重要，也是面试最常问的问题。那为什么是不安全的呢，下面简单总结以下。
情况一：
假设现在有A，B两个线程同时执行add方法，而现在size = 9，于是：
1，A经过以上步骤发现初始化容量为10，不需要进行数组扩容。
2，同时B也在执行add方法，它判断数组初始化容量也是10（size的值还是9），于是不进行数组扩容。接着A便执行add方法，元素添加成功后，size = 10；此时B开始执行add方法，但这个时候数组元素已经添加满了，B再添加就会造成数组下标越界异常。
情况二：
elementData[size++] = e;这一步也有可能出现问题。
列表大小为0，即size=0。
线程A开始添加一个元素，值为A。此时它执行第一条操作，将A放在了elementData下标为0的位置上。
接着线程B刚好也要开始添加一个值为B的元素，且走到了第一步操作。此时线程B获取到size的值依然为0，于是它将B也放在了elementData下标为0的位置上。
而最终size大小为：
线程A开始将size的值增加为1线程B开始将size的值增加为2
针对这种情况，可以使用以下方式解决：
List<String> list1 = Collections.synchronizedList(new ArrayList<String>());
五，Linked List
linked list数据存储的结构是双向链表结构。方便元素添加、删除的集合，但是查询较慢。
LinkedList中常用方法：
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
//添加元素
link.addFirst("abc1");
link.addFirst("abc2");
link.addFirst("abc3");
System.out.println(link);
// 获取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
// 删除元素
System.out.println(link.removeFirst());
System.out.println(link.removeLast());
while (!link.isEmpty()) { //判断集合是否为空
System.out.println(link.pop()); //弹出集合中的栈顶元素
}
System.out.println(link);
}
}
六，总结
1，arraylist增删慢，查询快，基于动态数组。
2，linkedlist增删快，查询慢，基于双向链表。
3，线程都不安全。
关于list接口中常用的两个集合就分享到此，对于两个集合要根据实际开发业务进行合理的选择，并且要注意线程安全的问题。本来想把set接口也一起写上，但是我觉得太长了，所以就留到下一篇博客。
好了，以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对亿速云的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
