- 简介
- 内部结构
- add
- remove
- set
- get
- ArrayList和linkedList
linkedList将做为双链表来实现，它本身实现了List接口和Deque接口(即满足队列的特性)，并且实现了所有可选的列表操作，并且允许包含所有元素（包括null）。面试中经常问到linkedList和ArrayList的区别 可以参考对比【JDK源码】ArrayList
下图是linkedList的UML图：
从图中我们可以看出：
- 继承了AbstractSequentialList抽象类：在遍历linkedList的时候，官方更推荐使用顺序访问，也就是使用我们的迭代器。（因为linkedList底层是通过一个链表来实现的）（虽然linkedList也提供了get（int index）方法，但是底层的实现是：每次调用get（int index）方法的时候，都需要从链表的头部或者尾部进行遍历，每一的遍历时间复杂度是O(index)，而相对比ArrayList的底层实现，每次遍历的时间复杂度都是O(1)。所以不推荐通过get（int index）遍历linkedList。至于上面的说从链表的头部或尾部进行遍历：官方源码对遍历进行了优化：通过判断索引index更靠近链表的头部还是尾部来选择遍历的方向）（所以这里遍历linkedList推荐使用迭代器）。
- 实现了List接口。（提供List接口中所有方法的实现）
- 实现了Cloneable接口，它支持克隆（浅克隆），底层实现：linkedList节点并没有被克隆，只是通过Object的clone（）方法得到的Object对象强制转化为了linkedList,然后把它内部的实例域都置空，然后把被拷贝的linkedList节点中的每一个值都拷贝到clone中。（后面有源码解析）
- 实现了Deque接口。实现了Deque所有的可选的操作。
- 实现了Serializable接口。表明它支持序列化。（和ArrayList一样，底层都提供了两个方法：readObject（ObjectInputStream o）、writeObject（ObjectOutputStream o），用于实现序列化，底层只序列化节点的个数和节点的值）。
1、首先我们先看看linkedList中真正用来存储元素的数据结构。
- Node 类是linkedList中的私有内部类，linkedList中就是通过Node来存储集合中的元素。
private static class Node{ E item;//节点的值 //双向链表 Node next;//当前节点的后一个节点的指针 Node prev;//当前节点的前一个节点的指针 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
2、linkedList集合中有哪些元素：
public class linkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable { transient int size = 0;//记录linkedList的大小 transient Node first;//用来表示linkedList的头节点。 transient Node last;//用来表示linkedList的尾节点。 }
3、接下来看看构造器，linkedList提供了两个构造器，ArrayList比它多提供了一个通过设置初始化容量来初始化类。linkedList不提供该方法的原因：因为linkedList底层是通过链表实现的，每当有新元素添加进来的时候，都是通过链接新的节点实现的，也就是说它的容量是随着元素的个数的变化而动态变化的。而ArrayList底层是通过数组来存储新添加的元素的，所以我们可以为ArrayList设置初始容量（实际设置的数组的大小）。
- 空构造器：
public linkedList() {
}
- 传入一个集合（Collection）作为参数初始化linkedList。
// 首先调用一下空的构造器。
//然后调用addAll(c)方法。
public linkedList(Collection c) {
this();
addAll(c);
}
这里有一个非常重要的方法linkedList(Collection c)
//通过调用addAll(int index, Collection c) 完成集合的添加。
public boolean addAll(Collection c) {
return addAll(size, c);
}
//几乎所有的涉及到在指定位置添加或者删除或修改操作都需要判断传进来的参数是否合法。
// checkPositionIndex(index)方法就起这个作用
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);==>
//先把集合转化为数组，然后为该数组添加一个新的引用（Objext[] a）。
Object[] a = c.toArray();
//新建一个变量存储数组的长度。
int numNew = a.length;
//如果待添加的集合为空，直接返回，无需进行后面的步骤。后面都是用来把集合中的元素添加到
//linkedList中。
if (numNew == 0)
return false;
//这里定义了两个节点
//Node succ：指代待添加节点的位置。
//Node pred：指代待添加节点的前一个节点。
Node pred, succ;
//如果index==size 在链表尾部追加数据
if (index == size) {
succ = null;
pred = last;
//否则的话succ指向插入待插入位置的节点。这里用到了node（int index）方法，这个方法
} else {
//node方法是返回index位置的结点==>
succ = node(index);
pred = succ.prev;
}
//链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//构建一个新的结点将 pred 和 元素e 给新结点
Node newNode = new Node<>(pred, e, null);
//为空说明是头结点
if (pred == null)
first = newNode;
//否则 前置节点的后置节点设置为新节点 其实就是在添加了
else
pred.next = newNode;
//往后走 继续添加
pred = newNode;
}
//当succ==null（也就是新添加的节点位于linkedList集合的最后一个元素的后面）
if (succ == null) {
//则设置尾节点
last = pred;
// 否则是在队中插入的节点
} else {
//更新前置节点 后置节点
pred.next = succ;
//更新后置节点的前置节点
succ.prev = pred;
}
//最后把集合的大小设置为新的大小
size += numNew;
//modCount（修改的次数）自增。
modCount++;
return true;
}
分析完后发现两个方法 checkPositionIndex(index) node(index)
- node(index)
//根据index 查询出Node， Nodenode(int index) { // assert isElementIndex(index); //通过下标获取某个node 的时候，（增、查 ），会根据index处于前半段还是后半段 进行一个折半，以提升查询效率 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
- checkPositionIndex(index)
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size; //插入时的检查，下标可以是size [0,size]
}
小结：
- 链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的
- 通过下标获取某个node 的时候，会根据index处于前半段还是后半段 进行一个折半，以提升查询效率
添加单个元素
- add(E e)
//在尾部插入一个节点： add
public boolean add(E e) {
linkLast(e);
return true;
}
- linkLast(e)
//生成新节点 并插入到 链表尾部， 更新 last/first 节点。
void linkLast(E e) {
final Node l = last; //记录原尾部节点
final Node newNode = new Node<>(l, e, null);//以原尾部节点为新节点的前置节点
last = newNode;//更新尾部节点
if (l == null)//若原链表为空链表，需要额外更新头结点
first = newNode;
else//否则更新原尾节点的后置节点为现在的尾节点（新节点）
l.next = newNode;
//size和modCount自增。
size++;
modCount++;
}
添加单个元素并且带上位置
- add(int index, E element)
//在指定下标，index处，插入一个节点
public void add(int index, E element) {
checkPositionIndex(index);//检查下标是否越界[0,size]
if (index == size)//在尾节点后插入
linkLast(element);
else//在中间插入
linkBefore(element, node(index));
}
- linkBefore(element, node(index))
//在succ节点前，插入一个新节点e void linkBefore(E e, Nodesucc) { // assert succ != null; //保存succ的前置节点 final Node pred = succ.prev; //以前置和后置节点和元素值e 构建一个新节点 final Node newNode = new Node<>(pred, e, succ); //新节点new是原节点succ的前置节点 succ.prev = newNode; if (pred == null)//如果之前的前置节点是空，说明succ是原头结点。所以新节点是现在的头结点 first = newNode; else//否则构建前置节点的后置节点为new pred.next = newNode; size++; modCount++; }
小结：
- 增一定会修改modCount
按照位置删除结点
- remove(int index)
//删：remove目标节点
public E remove(int index) {
checkElementIndex(index);//检查是否越界 下标[0,size)
return unlink(node(index));//从链表上删除某节点
}
- unlink(node(index))
//从链表上删除x节点 E unlink(Nodex) { // assert x != null; final E element = x.item; //当前节点的元素值 final Node next = x.next; //当前节点的后置节点 final Node prev = x.prev;//当前节点的前置节点 if (prev == null) { //如果前置节点为空(说明当前节点原本是头结点) first = next; //则头结点等于后置节点 } else { prev.next = next; x.prev = null; //将当前节点的 前置节点置空 将节点置空，方便GC } if (next == null) {//如果后置节点为空（说明当前节点原本是尾节点） last = prev; //则 尾节点为前置节点 } else { next.prev = prev; x.next = null;//将当前节点的 后置节点置空 将节点置空，方便GC } x.item = null; //将当前元素值置空 size--; //修改数量 modCount++; //修改modCount return element; //返回取出的元素值 }
- checkElementIndex(index)
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//下标[0,size)
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
直接删除某个结点
remove(Object o)
//因为要考虑 null元素，也是分情况遍历
public boolean remove(Object o) {
if (o == null) {//如果要删除的是null节点(从remove和add 里 可以看出，结点允许元素为null)
//遍历每个节点 对比
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
小结
-
删也一定会修改modCount
-
按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。
-
按元素删，会先去遍历链表寻找是否有该Node，考虑到允许null值，所以会遍历两遍，然后再去unlink它
-
扩展：遍历链表的方式
for (Nodesetx = first; x != null; x = x.next) { ... } Node x = first; while(x!=null){ x = x.next; }
public E set(int index, E element) {
checkElementIndex(index); //检查越界[0,size)
Node x = node(index);//取出对应的Node
E oldVal = x.item;//保存旧值 供返回
x.item = element;//用新值覆盖旧值
return oldVal;//返回旧值
}
改也是先根据index找到Node，然后替换值，改 不会修改modCount
get根据index查询节点
- get(int index)
public E get(int index) {
checkElementIndex(index);//判断是否越界 [0,size)
return node(index).item; //调用node()方法 取出 Node节点，
}
根据节点对象，查询下标
- indexOf(Object o)
public int indexOf(Object o) {
int index = 0;
if (o == null) {//如果目标对象是null
//遍历链表
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
从尾至头遍历链表，找到目标元素值为o的节点
- lastIndexOf(Object o)
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
查不修改modCount
为什么要修改这个modCount？
-
快速失败机制(集合容器下面大多都有这个机制来抛出异常…)
- 当一个list被多个线程成同时修改的时候会抛出异常。但是不能用来保证线程安全。
- 所以在多线程环境下，还是要自己加锁或者采用JUC包下面的方法来保证线程安全，
- 而不能依靠fail-fast机制抛出异常，这个方法只是用来检测bug。
-
此类的迭代器和迭代方法返回的迭代器是快速失败的：如果链表在迭代器被创建后的任何时间被结构化修改，除非是通过remove或者add方法操作的，否则将会抛出ConcurrentModificationException异常，因此，面对高并发的修改，迭代器以后快速而干净的失败以防承担冒着未确定的任意，非确定性行为的风险
我们也顺带看一下toArray()，毕竟这是个高频的API
public Object[] toArray() {
//new 一个新数组 然后遍历链表，将每个元素存在数组里，返回
Object[] result = new Object[size];
int i = 0;
//其实就是遍历链表然后赋值给数组
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
总结
linkedList 是双向列表。
-
链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的。增加一定会修改modCount。
-
通过下标获取某个node 的时候，会根据index处于前半段还是后半段 进行一个折半，以提升查询效率
-
删也一定会修改modCount。 按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。 按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node。
-
改也是先根据index找到Node，然后替换值。改不修改modCount。
-
查本身就是根据index找到Node。
-
所以它的CRUD操作里，都涉及到根据index去找到Node的操作。
- ArrayList的底层是数组；linkedList的底层是双向链表。
- 对于随机访问get和set，ArrayList优于linkedList,因为ArrayList可以通过下标位置定位数据而linkedList要遍历链表，移动指针
- 对于新增和删除操作add和remove，linkedList比较占优势，因为只需移动指针而不需要移动数据，但是ArrayList使用System…arraycopy进行数据拷贝以移动数据。
文章参考
添加链接描述
添加链接描述
添加链接描述
