JavaList定义
List是位于java.util下的一个接口，是Java集合中的有序集合，也称为序列。
JavaList实现种类
因为List是一个接口，为了使用它，你必须实例化一个具体的实现。
JavaList的常用实现类有：
- ArrayList
- LinkedList
- Vector
- Stack
ArrayList 和 LinkedList 最常用，Vector和Stack不太常用。
Vector可以理解成线程安全的ArrayList ，不过不建议使用，需要线程安全建议使用CopyOnWriteArrayList。
Stack继承自Vector，实现了一个后进先出的堆栈，不过它里面的方法与Vector内部的类似，都使用了Synchronized进行同步修饰，也不太常用。
所以，学习JavaList重点掌握好ArrayList 和LinkedList 即可。
ArrayList
1.ArrayList简介
ArrayList属于Java集合框架最常用的集合，实现了 List 接口。
2.ArrayList数据结构
ArrayList底层是用数组实现的，可以认为ArrayList是一个可改变大小的数组，随着越来越多的元素被添加到ArrayList中，其规模是动态增加的。
3.ArrayList特点
- 插入的元素是有序的；
- 基于动态数组的数据结构；
- 非线程安全；
- 擅长随机访问；
- 插入和删除可能引起扩容，效率较低；
4.ArrayList常用方法
1)add增加
List<String> list = new ArrayList<String>();
System.out.println("ArrayList集合初始化容量："+list.size());
//添加功能：
list.add("mikechen");
list.add("的互联网架构");
添加元素时，会指定默认为10的容量，当添加元素导致集合容量大于10，触发扩容机制，扩容为原来的1.5倍。
2)remove移除
List<String> list = new ArrayList<String>();
System.out.println("ArrayList集合初始化容量："+list.size());
//添加功能：
list.add("mikechen");
list.add("的互联网架构");
//删除功能：
list.remove(0);
3)get获取
List<String> list = new ArrayList<String>();
System.out.println("ArrayList集合初始化容量："+list.size());
//添加功能：
list.add("mikechen");
list.add("的互联网架构");
//get获取
list.get(0);
源码如下：
public E get(int index) { //获取指定索引的值
rangeCheck(index);//是否越界
return elementData(index);//返回指定下标的值
}
private void rangeCheck(int index) {
if (index >= size) //索引大于 集合长度，抛异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
由于ArrayList底层是基于数组实现的,所以获取元素就相当简单了,直接调用数组随机访问即可。
4)set修改
List<String> list = new ArrayList<String>();
System.out.println("ArrayList集合初始化容量："+list.size());
//添加元素
list.add("mikechen");
list.add("的互联网架构");
//修改元素
list.set(0,"ada");
源码如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}}
修改指定位置的元素为新元素，首先需要校验给定index的值，index必须大于等于0，小于size，然后将新元素保存到index位置，并将旧元素返回。
5)扩容操作
public void ensureCapacity(int minCapacity) {
//修改计时器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若当前需要的长度大于当前数组的长度时，进行扩容操作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//计算新的容量大小，为当前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//数组拷贝，生成新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
ensureCapacity()，该方法就是ArrayList的扩容方法，每次扩容处理会是1.5倍。
LinkedList
1.LinkedList简介
LinkedList是Java集合中比较常用的数据结构，与 ArrayList 一样，实现了 List 接口，只不过 ArrayList 是基于数组实现的，而 LinkedList是基于链表实现的。
2.LinkedList数据结构
LinkedList的数据结构是一个双向链表，它有两个成员变量：first 和 last，分别指向双向队列的头和尾。
Node<E> first; Node<E> last;
这里“双向”的含义是相对单链表而言的，双向链表的节点不仅有后继，还有前驱。
3.LinkedList特点
- 增删效率高；
- 查询效率低；
- 线程不安全；
4.LinkedList常用方法
1)添加元素
boolean add(E e)
将指定的元素追加到此列表的末尾。
List<String> linkedList = new LinkedList<String>();
System.out.println("LinkedList初始容量："+linkedList.size());
//添加元素
linkedList.add("mikechen");
linkedList.add("的互联网架构");
2)修改元素
E set(int index,E element)
用指定的元素替换此列表中指定位置的元素
List<String> linkedList = new LinkedList<String>();
System.out.println("LinkedList初始容量："+linkedList.size());
//添加元素
linkedList.add("mikechen");
linkedList.add("的互联网架构");
//修改元素
linkedList.set(0,"ada");
3)删除元素
boolean remove(Object o )
从列表中删除指定元素的第一个出现（如果存在）
List<String> linkedList = new LinkedList<String>();
System.out.println("LinkedList初始容量："+linkedList.size());
//添加元素
linkedList.add("mikechen");
linkedList.add("的互联网架构");
//删除元素
linkedList.remove("mikechen");
ArrayList和LinkedList的区别
1. ArrayList 的实现是基于数组,LinkedList的实现是基于双向链表;
2. 对于随机访问 ArrayList 要优于LinkedList,ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问,而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起,查找某个元素的时间复杂度是O(N);
3. 对于插入和删除操作,LinkedList要优于 ArrayList ,因为当元素被添加到LinkedList任意位置的时候,不需要像 ArrayList 那样重新计算大小或者是更新索引;
4. LinkedList比ArrayList 更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》