文章目录
(一)List子父层级：
List接口继承于Collection，Collection继承Iterable;
LIst接口实现类分为：Vector、ArrayList、LinkedList;
(二)List实现类
1、LinkedList实现类
《1）LinkedList底层是内部Node类的存储，prev、next、item值，同时最外层还有first、last节点；
（2）LinkedList是线程不安全的，多线程环境会报并发修改异常java.util.ConcurrentModificationException。
（3）LinkedList无扩容机制，底层是双向链表结构，内部是Node结构，外部是first、last首尾节点。
2、常见源码
（1）构造方法：
//无参构造，有参构造是将一个LinkedList对象传入进行追加（数据复制）
public LinkedList() { }
（2）add方法：
public boolean add(E e) {
linkLast(e);//将e以尾插法入链表
return true;
}
//新数据入链表
void linkLast(E e) {
final Node<E> l = last;//获取尾节点
final Node<E> newNode = new Node<>(l, e, null);//调用Node构造方法进行入链表
last = newNode;//修改最新尾节点
if (l == null)//判定是否为第一个链表节点
first = newNode;//设置为第一个节点
else
l.next = newNode;//将新节点与旧节点相连
size++;//数量自增
modCount++;//操作链表自增
}
//内部类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;//设置当前新节点的上一节点值
}
}
（3）remove方法：
//列举根据值删除,不列举按索引删除remove，逻辑大体差不多
public boolean remove(Object o) {
if (o == null) {//空值删除
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//调用删除方法
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);//调用删除方法
return true;
}
}
}
return false;
}
//删除节点方法，将节点的前后节点进行连接，然后将自身置空，其中判定首节点和尾节点为空处理
E unlink(Node<E> x) {
final E element = x.item;//删除节点值
final Node<E> next = x.next;//删除节点的下一节点
final Node<E> prev = x.prev;//删除节点的上一节点
if (prev == null) {//上一节点那为空
first = next;//设置新的首节点
} else {
prev.next = next;//将删节点的前后链接（前节点）
x.prev = null;//置空当前节点的prev值
}
if (next == null) {//删除节点下一节点为空
last = prev;//设置新的尾节点
} else {
next.prev = prev;//删除节点的前后链接（针对后节点）
x.next = null;//置空当前节点的next值
}
x.item = null;//置空当前节点值
size--;//数量减一
modCount++;//操作次数自增
return element;//返回删除节点值
}
（4）get方法：
public E get(int index) {
checkElementIndex(index);//是否在正常范围内，index>=0&&index<size
return node(index).item;//返回指定索引节点值
}
//根据索引值返回节点,根据二分法(折半)查找
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;//返回节点
}
}
（5）set方法：
//指定索引位置进行设值
public E set(int index, E element) {
checkElementIndex(index);//检查索引是否合法
Node<E> x = node(index);//获取索引节点
E oldVal = x.item;//原索引节点值
x.item = element;//设值
return oldVal;//返回旧值
}
3、总结
（1）LinkedList是线程不安全，多线程环境会造成并发修改异常java.util.ConcurrentModificationException；
（2）LinkedList是一个双向链表结构（无扩容机制），内部是Node，外部是首尾节点first、last。