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的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。