一文学懂List附带超详细ArrayList，Vector，LinkedList底层源码解析

1.为什么要用集合

之前我们保存多个数据使用的都是数组，这有很多的局限性

1. 长度必须直接指定，而且一旦指定，不能更改。
2. 保存的必须为同一类型的元素
3. 使用数组进行增加/删除元素十分麻烦，浪费内存空间。

因此Java为我们提供了更方便的数组，集合。

2.认识集合

1. 可以动态保存多个对象，使用方便。
2. 提供了一系列方便的操作对象的方法，如add，remove等。
3. 使用集合添加，删除新元素十分便捷。

3. 集合体系

集合分为两组，单列集合与双列集合，分别对应Collection和Map，前者以元素形式存储数据，后者以键值对方式存储（key-value）。

4.Collection接口

4.1 Collection接口特点

1. collection实现子类可以存放多个元素，每个元素可以是Object。
2. Collection的实现类有些可以存放重复元素，有些不可以。
3. Collection的实现类，有些存放元素是有序的（LIst），有些不是有序（Set）。
4. Collection接口并没有直接的实现子类，是通过它的子接口Set和List来实现的。

4.2 Collection接口常用方法

这里用List集合演示

List list = new ArrayList();//创建集合对象
// add:添加单个元素
list.add("jack");
list.add(10);//list.add(new Integer(10))
list.add(true);
System.out.println("list=" + list);
// remove:删除指定元素
list.remove(0);//删除第一个元素
list.remove(true);//指定删除某个元素
//contains:查找元素是否存在
System.out.println(list.contains("jack"));
// size:获取元素个数
System.out.println(list.size());//2
//isEmpty:判断是否为空
System.out.println(list.isEmpty());//F
// clear:清空
list.clear();
//addAll:添加多个元素，也就是类似两个集合合并
ArrayList list2 = new ArrayList();
list2.add("红楼梦");
list2.add("三国演义");
list.addAll(list2);
// containsAll:查找多个元素是否都存在
System.out.println(list.containsAll(list2));
// removeAll：删除多个元素
list.removeAll(list2);

5.List接口

5.1 List接口基本介绍

1. List接口是Collection接口子接口
2. List集合类中的元素是有序的（添加顺序和取出顺序一致），且可以重复。
3. List集合类中的每个元素都有其对应的顺序索引，即支持索引。
4. List容器中的元素都对应一个整数类型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

//1. List 集合类中元素有序(即添加顺序和取出顺序一致)、且可重复 
List list = new ArrayList();
list.add("jack");
list.add("tom");
list.add("mary");
list.add("bobo");
list.add("tom");//可以重复
//2. List 集合中的每个元素都有其对应的顺序索引，即支持索引，索引是从 0 开始的
System.out.println(list.get(3));//bobo

5.2 List的三种遍历方式

List数组如下

List list = new LinkedList();
list.add("jack");
list.add("tom");
list.add("mary");
list.add("lucy");

1.迭代器遍历

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println(obj);

2.增强for

for (Object o : list) {
	System.out.println("o=" + o);
}

3.普通for

for (int i = 0; i < list.size(); i++) {
	System.out.println("对象=" + list.get(i));
}

6. ArrayList

6.1 ArrayList特点

1. ArrayList可以加入null，且可以加入多个。
2. ArrayList是由数组来实现数据存储的
3. ArrayList基本等同于Vector，除了 ArrayList是线程不安全的，但执行效率高，多线程情况下，不建议使用 ArrayList

6.2 ArrayList常用方法

List list = new ArrayList();
list.add("张三");
list.add("李四");
// void add(int index, Object ele):在 index 位置插入 ele 元素
//在 index = 1 的位置插入一个对象
list.add(1, "可爱的波波");
// boolean addAll(int index, Collection eles):从 index 位置开始将 eles 中的所有元素添加进来
List list2 = new ArrayList();
list2.add("jack");
list2.add("tom");
list.addAll(1, list2);
System.out.println("list=" + list);
// Object get(int index):获取指定 index 位置的元素
//说过
// int indexOf(Object obj):返回 obj 在集合中首次出现的位置
System.out.println(list.indexOf("tom"));//2
// int lastIndexOf(Object obj):返回 obj 在当前集合中末次出现的位置
list.add("可爱的波波");
System.out.println(list.lastIndexOf("可爱的波波"));
// Object remove(int index):移除指定 index 位置的元素，并返回此元素
list.remove(0);
// Object set(int index, Object ele):设置指定 index 位置的元素为 ele , 相当于是替换. list.set(1, "玛丽");
System.out.println("list=" + list);
// List subList(int fromIndex, int toIndex):返回从 fromIndex 到 toIndex 位置的子集合
// 注意返回的子集合 fromIndex <= subList < toIndex
List returnlist = list.subList(0, 2);
System.out.println("returnlist=" + returnlist);

6.3 ArrayList底层机制

1. ArrayList中维护了一个Object类型的数组elementData。
2. 当创建 ArrayList对象时，如果使用的是无参构造器，则初始elementData的容量为0，第一次添加，将其扩容为10，如果 还需要添加，则按elementData的1.5倍扩容。
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容1.5倍。

6.4 ArrayList源码分析

当 ArrayList使用无参构造器时，首先创建的是空的elementData数组

加入元素时

进行扩容

判断是否需要扩容

进一步判断其大小，如果是数组则返回10

如果数组大小将大于当前容量，则进行1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1);

7. Vector

7.1 Vector特点

1. Vector底层是一个对象数组，Object[] elementData;
2. Vector是线程同步的，即线程安全，Vector的操作方法带有锁
3. 在开发中，需要考虑线程安全，则使用Vector，其速度不如ArrayList

7.2 Vector使用注意

1. 其中方法与ArrayList一致
2. 在扩容时按2倍进行扩容

7.3 Vector源码解析

与ArrayList类似，Vector使用无参构造时就会拥有10个空间大小

先判断是否需要扩容，如果需要扩容则会以2倍大小扩容

8. LinkedList

8.1 LinkedList特点

1. LinkedList底层实现了双向链表和双端队列特点。
2. 可以添加任意元素（元素可以重复），包括null。
3. 线程不安全，没有实现同步。

增加元素的原理

8.2 LinkedList底层机制

1. LinkedList底层维护的是一个双向链表。
2. LinkedList中维护了两个属性first和last分别指向 首节点和尾节点。
3. 每个结点（Node对象），里面又维护了prev，next，item 三个属性。其中通过prev指向前一个，通过next指向后一个节点 。最终实现双向链表。
4. LinkedList中元素的添加和删除不是通过数组完成的，效率较高。

8.3 LinkedList源码解读

首先通过构造器产生一个大小为0的链表，，并且头尾都指向null

执行add（）方法

关键的节点连接

8.3 LinkedList常用方法

LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println("linkedList=" + linkedList);
//演示一个删除结点的
linkedList.remove(); // 这里默认删除的是第一个结点
linkedList.remove(2);//删除第三个结点，从0开始
//修改某个结点对象
linkedList.set(1, 999);
//得到某个结点对象
//get(1) 是得到双向链表的第二个对象
Object o = linkedList.get(1);
System.out.println(o);//999

8.4 遍历 LinkedList

8.4.1遍历迭代器

//因为 LinkedList 是 实现了 List 接口, 遍历方式
System.out.println("===LinkeList 遍历迭代器====");
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("next=" + next);
}

8.4.2 增强for

System.out.println("===LinkeList 遍历增强 for====");
for (Object o1 : linkedList) {
System.out.println("o1=" + o1);
}

8.4.3 普通for

System.out.println("===LinkeList 遍历普通 for====");
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}

9. 结语

Java集合的应用极其广泛，面试也常问，想完全了解集合的实现，建议还是自己亲手去debug源码追一下，这样的印象最为深刻，map的讲解将会放在下一篇，谢谢观看。