## List接口
继承Collection接口的一个接口，就是传统的线性表的结构，实现该接口的结构存储的数据不唯一（值不唯一，类型是唯一的），同时数据按照添加的顺序进行排列。
其主要扩展Collection的方法有：
~~~
public interface List<E> extends Collection<E> {
// 元素进行排序
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
// 获取某个下标的元素
E get(int index);
// 修改某个下标的元素
E set(int index, E element);
// 判断元素是否存在
// 从头开始，并返回第一相同元素的索引
int indexOf(Object o);
// 从后面开始，并返回第一个相同元素的索引
int lastIndexOf(Object o);
// 快速创建List对象的静态方法
static <E> List<E> of() {
return (List<E>) ImmutableCollections.ListN.EMPTY_LIST;
}
static <E> List<E> of(E e1) {
return new ImmutableCollections.List12<>(e1);
}
// 还有好几个重载的方法
}
~~~
*****
下面是List的常见实现类：
### Vector
底层用数组存储，里面的方法都是线程安全的，现版本基本别抛弃了，不建议使用。
~~~
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 1. 重要的属性
// 用数组结构来保存数据
protected Object[] elementData;
// 数组中元素的个数
protected int elementCount;
// 扩容时数组增长的大小，如果该值小于等于0时会默认增长一倍
protected int capacityIncrement;
//-----------------------------------------------------
// 2.构造函数
public Vector() {
// 无参构造默认数组初始化大小为10
this(10);
}
public Vector(int initialCapacity) {
// 默认扩容因子为0，因此在扩容的时候会增长数组长度的一倍
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
// 最终都会调用这个
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
// -------------------------------------------
// 3. 常见操作
// 添加元素，修改到底层数组结构内容的有如下两个方法：
// 私有的，供其他add方法调用，往s的位置添加
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
// 超出底层数组大小需要扩容
elementData = grow();
elementData[s] = e;
elementCount = s + 1;
}
// 插入操作，往index位置插入
public synchronized void insertElementAt(E obj, int index) {
if (index > elementCount) {
// 插入范围在0~elementCount
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
// AbstractList中声明的用来记录结构被修改的次数，可以用于增强for循环中删除数组元素报错的情况。
modCount++;
final int s = elementCount;
Object[] elementData = this.elementData;
if (s == elementData.length)
elementData = grow();
// 将index开始的元素移动到index+1后，使用native方法，性能更高
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = obj;
elementCount = s + 1;
}
// 获取元素
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
// 移除元素
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
// 要移动元素的数量，如果是index为最后一个元素则不用移除操作
int numMoved = elementCount - index - 1;
if (numMoved > 0)
// 将index+1的位置往前移动即可删除
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
// 移除所有元素
public void clear() {
removeAllElements();
}
public synchronized void removeAllElements() {
final Object[] es = elementData;
for (int to = elementCount, i = elementCount = 0; i < to; i++)
es[i] = null;
modCount++;
}
// --------------------------------------
// 扩容操作
private Object[] grow() {
// 至少扩容大于1个元素
return grow(elementCount + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
// 获取新的数组长度，当扩容因子为0的时候扩展为原来的1倍大小
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, capacityIncrement > 0 ? capacityIncrement : oldCapacity);
return elementData = Arrays.copyOf(elementData, newCapacity);
}
}
~~~
*****
### ArrayList
底层用数组存储，与Vector相比，ArrayList的操作不是线程安全的，其他基本与Vector相同。
~~~
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 默认初始化数组元素的大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 创建没有元素的ArrayList的话所有ArrayList共享这个对象，节约空间
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 没有指定初始化容量时使用，可以用于标识在添加第一个元素的时候需要扩容的大小
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 底层数组结构，通过上面两个全局静态的常量可以发现，当初始化容量为0或者不指定的时候这是一个延迟创建的对象，知道真正添加元素的时候才创建
*/
transient Object[] elementData;
/**
* 元素个数
*/
private int size;
// 构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 容量为0的时候不创建对象
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 不指定初始化容量的时候在第一次添加元素时会初始化10个元素大小的数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/** 其他操作和vector相比差不多，主要是扩容机制不太一样，ArrayList没有扩容因子，因此在一般情况都是扩容当前长度的1/2大小的；
有个特殊的情况就是如果当初始化容量为0的时候第一次添加元素的时候只会扩容一个元素
*/
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, oldCapacity >> 1);// 右移
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
}
~~~
ArrayList的扩容机制有点特殊的点在于当没有指定初始容量或者初始容量为0的时候在第一次添加数据的时候就会进入扩容逻辑，是延迟创建对象的：
1. 初始容量为0时第一次添加元素创建1个长度的底层数组。
2. 没有指定初始容量时第一次添加元素创建默认长度为10的底层数组。
3. 初始化容量指定为0时，第一次添加元素的数组长度会扩容为1。
Vector和ArrayList的异同：
1. 正常情况下底层数组初始大小都为10。
2. Vector可以指定初始的扩容因子，并且在没有指定的情况下默认扩容一倍大小；而ArrayList不能指定扩容因子的大小，正常情况下每次扩容原来的1/2。
3. Vector的操作都是同步的，使用synchronized关键字进行修饰，而ArrayList的操作并不是同步的。
4. ArrayList在初始化容量为0或者没有指定初始化容量的时候做了一些优化，可以实现延迟创建对象的效果。
*****
### LinkedList
底层用双向链表存储数据
~~~
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 元素数量
transient int size = 0;
// 指向头节点
transient Node<E> first;
// 指向尾节点
transient Node<E> last;
// 空构造
public LinkedList() {
}
// Node结构如下
private static class Node<E> {
E item;
// 指向下一个元素
Node<E> next;
// 指向上一个元素
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// ------------------------------------------
// 常见操作
// 1. 添加节点
public void addFirst(E e) {
// 头插
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
// 创建节点并连接
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addLast(E e) {
// 尾插
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
// 创建节点并连接
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
public boolean add(E e) {
// add默认使用尾插
linkLast(e);
return true;
}
// 查询操作
Node<E> node(int index) {
// 前一半位置从头开始查，
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 后一半位置从尾开始查
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 算了...其他就需要再看吧，下面这些都是队列的相关操作，注意其实现了Dequeu
public E peek() {} // 获取第一个元素
public E poll() {} // 删除第一个元素并返回
public E remove() {} // 移除第一个元素
public void push(E e) {} // 插入第一个元素的位置
public E pop() {} // 弹出第一个元素
}
~~~
从源代码可以看出LinkedList是一个双端链表，不仅可以作为链表使用，还可以作为队列使用。
参考：
JDK1.8源码
- 第一章 Java基础
- ThreadLocal
- Java异常体系
- Java集合框架
- List接口及其实现类
- Queue接口及其实现类
- Set接口及其实现类
- Map接口及其实现类
- JDK1.8新特性
- Lambda表达式
- 常用函数式接口
- stream流
- 面试
- 第二章 Java虚拟机
- 第一节、运行时数据区
- 第二节、垃圾回收
- 第三节、类加载机制
- 第四节、类文件与字节码指令
- 第五节、语法糖
- 第六节、运行期优化
- 面试常见问题
- 第三章 并发编程
- 第一节、Java中的线程
- 第二节、Java中的锁
- 第三节、线程池
- 第四节、并发工具类
- AQS
- 第四章 网络编程
- WebSocket协议
- Netty
- Netty入门
- Netty-自定义协议
- 面试题
- IO
- 网络IO模型
- 第五章 操作系统
- IO
- 文件系统的相关概念
- Java几种文件读写方式性能对比
- Socket
- 内存管理
- 进程、线程、协程
- IO模型的演化过程
- 第六章 计算机网络
- 第七章 消息队列
- RabbitMQ
- 第八章 开发框架
- Spring
- Spring事务
- Spring MVC
- Spring Boot
- Mybatis
- Mybatis-Plus
- Shiro
- 第九章 数据库
- Mysql
- Mysql中的索引
- Mysql中的锁
- 面试常见问题
- Mysql中的日志
- InnoDB存储引擎
- 事务
- Redis
- redis的数据类型
- redis数据结构
- Redis主从复制
- 哨兵模式
- 面试题
- Spring Boot整合Lettuce+Redisson实现布隆过滤器
- 集群
- Redis网络IO模型
- 第十章 设计模式
- 设计模式-七大原则
- 设计模式-单例模式
- 设计模式-备忘录模式
- 设计模式-原型模式
- 设计模式-责任链模式
- 设计模式-过滤模式
- 设计模式-观察者模式
- 设计模式-工厂方法模式
- 设计模式-抽象工厂模式
- 设计模式-代理模式
- 第十一章 后端开发常用工具、库
- Docker
- Docker安装Mysql
- 第十二章 中间件
- ZooKeeper