一、概述
LinkedList，绝对于 ArrayList，大家可能平时应用 LinkedList 要少一些，其实有时候应用 LinkedList 比 ArrayList 效率高很多，当然，这得视状况而定。
本文将带大家深刻 LinkedList 源码，剖析其背地的实现原理，以便当前在适合的状况下进行应用。
之前我所晓得的 LinkedList 的常识：
- LinkedList 底层是链表构造
- 插入和删除比拟快（O(1)），查问则绝对慢一些（O(n)）
- 因为是链表构造，所以调配的空间不要求是间断的
二、链表
因为 LinkedList 源码中很多中央是进行链表操作, 所以先带大家温习一下链表的基础知识. 以前用 C 语言实现的链表, 大家能够去看一下, 地址:https://github.com/xfhy/dataS…
1. 单链表
一个节点中蕴含数据和下一个节点的指针(留神, 是下一个节点的指针, 而不是下一个节点数据的指针), 尾节点没有下一个节点, 所以指向 null. 拜访某个节点只能从头节点开始查找, 而后顺次往后遍历.
2. 单向循环链表
单向循环链表比单链表多了一个尾节点的指针指向的是头结点.
3. 双向链表
双向链表的每个节点蕴含以下数据: 上一个节点的指针, 本人的数据, 下一个节点的指针. 尾节点没有下一个节点, 所以指向 null. 这样的构造, 比方我拿到链表两头的一个节点, 即能够往前遍历, 也能够往后遍历.
4. 双向循环链表
双向循环链表的尾节点的下一个节点是头结点, 头节点的上一个节点是尾节点.
三、LinkedList 的继承关系
源码中的定义:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable- AbstractSequentialList 这个类提供了 List 的一个骨架实现接口，以尽量减少实现此接口所需的工作量由“程序拜访”数据存储（如链接列表）反对。对于随机拜访数据（如数组），应应用 AbstractList 优先于此类。
- 实现了 List 接口, 意味着 LinkedList 元素是有序的, 能够反复的, 能够有 null 元素的汇合.
- Deque 是 Queue 的子接口,Queue 是一种队列模式, 而 Deque 是双向队列, 它反对从两个端点方向检索和插入元素.
- 实现了 Cloneable 接口, 标识着能够它能够被复制. 留神,ArrayList 外面的 clone()复制其实是浅复制(不晓得此概念的赶快去查资料, 这知识点十分重要).
- 实现了 Serializable 标识着汇合可被序列化。
四、看 LinkedList 源码前的筹备
1. 节点定义
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;
}
}Node 是 LinkedList 的动态外部类.
为什么是动态外部类? 我感觉可能起因如下: 一般外部类会有外部类的强援用, 而动态外部类就没有. 有外部类的强援用的话, 很容易造成内存透露, 写成动态外部类能够防止这种状况的产生.
2. 成员变量
看构造方法之前先看看几个属性:
// 链表长度
transient int size = 0;
/**
* 头结点
*/
transient Node<E> first;
/**
* 尾节点
*/
transient Node<E> last;这里为什么要存在一个成员变量尾节点? 我感觉是为了不便, 比方查找相应索引处元素 + 插入元素到最初. 查找相应索引处元素时, 先判断索引是在前半段还是在后半段, 如果是在后半段, 那么间接从尾节点登程, 从后往前进行查找, 这样速度更快. 在插入元素到最初时, 能够间接通过尾节点不便的进行插入.
3. 构造方法
上面是构造方法源码:
/**
* 结构一个空列表
*/
public LinkedList() {}
/**
* 结构列表通过指定的汇合
*/
public LinkedList(Collection<? extends E> c) {this();
addAll(c);
}两个构造方法都比较简单, 就是结构一个列表, 其中的 addAll()办法待会儿放到前面剖析.
思考: 为什么 LinkedList 没有提供 public LinkedList(int initialCapacity)这种构建指定大小列表的结构形式?
因为 ArrayList 有这种构造方法public ArrayList(int initialCapacity),ArrayList 提供这种构造方法的益处在于在晓得须要多大的空间的状况下, 能够按需结构列表, 无需节约多余的空间和不必要的生成新数组的操作. 而 LinkedList 能够很轻松动静的减少元素(O(1)), 所以没必要一开始就结构一个有很多元素的列表, 到时须要的时候再按需加上去就行了.
五、增加元素
1. add(E e)
办法作用: 将 e 增加到链表开端, 返回是否增加胜利
/**
* 增加指定元素到链表尾部
*/
public boolean add(E e) {linkLast(e);
return true;
}
/**
* Links e as last element. 将 e 增加到尾部
*/
void linkLast(E e) {
//1. 暂记尾节点
final Node<E> l = last;
//2. 构建节点 前一个节点是之前的尾节点
final Node<E> newNode = new Node<>(l, e, null);
//3. 新建的节点是尾节点了
last = newNode;
//4. 判断之前链表是否为空
// 为空则将新节点赋给头结点(相当于空链表插入第一个元素, 头结点等于尾节点)
// 非空则将之前的尾节点指向新节点
if (l == null)
first = newNode;
else
l.next = newNode;
//5. 链表长度减少
size++;
modCount++;
}大体思路:
- 构建一个新的节点
- 将该新节点作为新的尾节点. 如果是空链表插入第一个元素, 那么头结点 = 尾节点 = 新节点; 如果不是, 那么将之前的尾节点指向新节点.
- 减少链表长度
小细节 boolean add(E e) 增加胜利返回 true, 增加失败返回 false. 咱们在代码中没有看到有返回 false 的状况啊, 间接在代码中写了个返回 true, 什么判断条件都没有, 啊??
认真想想, 分配内存空间不是必须是间断的, 所以只有是还能给它调配空间, 就不会增加失败. 当空间不够调配时(内存溢出), 会抛出 OutOfMemory.
2. addLast(E e)
办法作用: 增加元素到开端. 外部实现和 add(E e) 一样.
public void addLast(E e) {linkLast(e);
}3. addFirst(E e)
办法作用: 增加元素到链表头部
public void addFirst(E e) {linkFirst(e);
}
/**
* 增加元素到链表头部
*/
private void linkFirst(E e) {
//1. 记录头结点
final Node<E> f = first;
//2. 创立新节点 next 指针指向之前的头结点
final Node<E> newNode = new Node<>(null, e, f);
//3. 新建的节点就是头节点了
first = newNode;
//4. 判断之前链表是否为空
// 为空则将新节点赋给尾节点(相当于空链表插入第一个元素, 头结点等于尾节点)
// 非空则将之前的头结点的 prev 指针指向新节点
if (f == null)
last = newNode;
else
f.prev = newNode;
//5. 链表长度减少
size++;
modCount++;
}大体思路:
- 构建一个新的节点
- 将该新节点作为新的头节点. 如果是空链表插入第一个元素, 那么头结点 = 尾节点 = 新节点; 如果不是, 那么将之前的头节点的 prev 指针指向新节点.
- 减少链表长度
4. push(E e)
办法作用: 增加元素到链表头部 这里的意思比较压栈. 和 pop(出栈: 移除链表第一个元素)相同.
外部实现是和 addFirst() 一样的.
public void push(E e) {addFirst(e);
}5. offer(),offerFirst(E e),offerLast(E e)
办法作用: 增加元素到链表头部. 外部实现其实就是add(e)
public boolean offer(E e) {return add(e);
}
public boolean offerFirst(E e) {addFirst(e);
return true;
}
/**
* 增加元素到开端
*/
public boolean offerLast(E e) {addLast(e);
return true;
}6. add(int index, E element)
办法作用: 增加元素到指定地位, 可能会抛出IndexOutOfBoundsException
// 增加元素到指定地位
public void add(int index, E element) {
//1. 越界查看
checkPositionIndex(index);
//2. 判断一下 index 大小
// 如果是和 list 大小一样, 那么就插入到最初
// 否则插入到 index 处
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// 查看是否越界
private void checkPositionIndex(int index) {if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Returns the (non-null) Node at the specified element index.
返回指定元素索引处的（非空）节点。*/
Node<E> node(int index) {// assert isElementIndex(index);
/**
* 这里的思维十分奇妙, 如果 index 在链表的前半部分, 那么从 first 开始往后查找
否则, 从 last 往前面查找
*/
//1. 如果 index<size/2 , 即 index 在链表的前半部分
if (index < (size >> 1)) {
//2. 记录下第一个节点
Node<E> x = first;
//3. 循环从第一个节点开始往后查, 直到达到 index 处, 返回 index 处的元素
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//index 在链表的后半局部
//4. 记录下最初一个节点
Node<E> x = last;
//5. 循环从最初一个节点开始往前查, 直到达到 index 处, 返回 index 处的元素
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* Links e as last element.
将 e 链接到 list 最初一个元素
*/
void linkLast(E e) {
//1. 记录最初一个元素 l
final Node<E> l = last;
//2. 构建一个新节点, 数据为 e, 前一个是 l, 后一个是 null
final Node<E> newNode = new Node<>(l, e, null);
//3. 当初新节点是最初一个元素了, 所以须要记录下来
last = newNode;
//4. 如果之前 list 为空, 那么 first=last=newNode, 只有一个元素
if (l == null)
first = newNode;
else
//5. 非空的话, 那么将之前的最初一个指向新的节点
l.next = newNode;
//6. 链表长度 +1
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
在非 null 节点 succ 之前插入元素 e。*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//1. 记录 succ 的前一个节点
final Node<E> pred = succ.prev;
//2. 构建一个新节点, 数据是 e, 前一个节点是 pred, 下一个节点是 succ
final Node<E> newNode = new Node<>(pred, e, succ);
//3. 将新节点作为 succ 的前一个节点
succ.prev = newNode;
//4. 判断 pred 是否为空
// 如果为空, 那么阐明 succ 是之前的头节点, 当初新节点在 succ 的后面, 所以新节点是头节点
if (pred == null)
first = newNode;
else
//5. succ 的前一个节点不是空的话, 那么间接将 succ 的前一个节点指向新节点就能够了
pred.next = newNode;
//6. 链表长度 +1
size++;
modCount++;
}大体思路:
- 首先判断一下插入的地位是在链表的最初还是在链表两头.
- 如果是插入到链表开端, 那么将之前的尾节点指向新节点
-
如果是插入到链表两头
- 须要先找到链表中 index 索引处的节点.
- 将新节点赋值为 index 处节点的前一个节点
- 将 index 处节点的前一个节点的 next 指针赋值为新节点
哇, 这里形容起来有点艰难,,,, 不晓得我形容分明没有. 如果没看懂我的形容, 看一下代码 + 再联合代码正文 + 画一下草图应该更清晰一些.
6. addAll(int index, Collection<? extends E> c)
办法作用: 将指定汇合的所有元素插入到 index 地位
// 将指定汇合的所有元素插入到开端地位
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}
// 将指定汇合的所有元素插入到 index 地位
public boolean addAll(int index, Collection<? extends E> c) {
//1. 入参合法性检查
checkPositionIndex(index);
//2. 将汇合转成数组
Object[] a = c.toArray();
//3. 记录须要插入的汇合元素个数
int numNew = a.length;
//4. 如果个数为 0, 那么插入失败, 不继续执行了
if (numNew == 0)
return false;
//5. 判断一下 index 与 size 是否相等
// 相等则插入到链表开端
// 不相等则插入到链表两头 index 处
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
// 找到 index 索引处节点 这样就能够不便的拿到该节点的前后节点信息
succ = node(index);
// 记录 index 索引处节点前一个节点
pred = succ.prev;
}
//6. 循环将汇合中所有元素连贯到 pred 前面
for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
// 如果前一个是空, 那么将新节点作为头结点
if (pred == null)
first = newNode;
else
// 指向新节点
pred.next = newNode;
pred = newNode;
}
//7. 判断 succ 是否为空
// 为空的话, 那么汇合的最初一个元素就是尾节点
// 非空的话, 那么将 succ 连贯到汇合的最初一个元素前面
if (succ == null) {last = pred;} else {
pred.next = succ;
succ.prev = pred;
}
//8. 链表长度 +numNew
size += numNew;
modCount++;
return true;
}大体思路:
- 将须要增加的汇合转成数组 a
- 判断须要插入的地位 index 是否等于链表长度 size, 如果相等则插入到链表最初; 如果不相等, 则插入到链表两头, 还须要找到 index 处节点 succ, 不便拿到该节点的前后节点信息.
- 记录 index 索引处节点的前一个节点 pred, 循环将汇合中所有元素连贯到 pred 的前面
- 将汇合最初一个元素的 next 指针指向 succ, 将 succ 的 prev 指针指向汇合的最初一个元素
六、删除元素
1. remove(),removeFirst()
办法作用: 移除链表第一个元素
/**
* 移除链表第一个节点
*/
public E remove() {return removeFirst();
}
/**
* 移除链表第一个节点
*/
public E removeFirst() {
final Node<E> f = first;
// 留神: 如果之前是空链表, 移除是要报错的哟
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
* 将第一个节点删掉
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//1. 记录第一个节点的数据值
final E element = f.item;
//2. 记录下一个节点
final Node<E> next = f.next;
//3. 将第一个节点置空 帮忙 GC 回收
f.item = null;
f.next = null; // help GC
//4. 记录头节点
first = next;
//5. 如果下一个节点为空, 那么链表无节点了 如果不为空, 将头节点的 prev 指针置为空
if (next == null)
last = null;
else
next.prev = null;
//6. 链表长度 -1
size--;
modCount++;
//7. 返回删除的节点的数据值
return element;
}大体思路: 其实就是将第一个节点移除并置空, 而后将第二个节点作为头节点. 思路还是十分清晰的, 次要是对细节的解决.
2. remove(int index)
办法作用: 移除指定地位元素
// 移除指定地位元素
public E remove(int index) {
// 查看入参是否非法
checkElementIndex(index);
//node(index)找到 index 处的节点
return unlink(node(index));
}
// 移除节点 x
E unlink(Node<E> x) {
// assert x != null;
//1. 记录该节点数据值, 前一个节点 prev, 后一个节点 next
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//2. 判断前一个节点是否为空
if (prev == null) {
// 为空的话, 那么阐明之前 x 节点是头节点 这时 x 的下一个节点成为头节点
first = next;
} else {
// 非空的话, 将前一个节点的 next 指针指向 x 的下一个节点
prev.next = next;
// x 的 prev 置为 null
x.prev = null;
}
//3. 判断 x 后一个节点是否为空
if (next == null) {
// 为空的话, 那么阐明之前 x 节点是尾节点, 这时 x 的前一个节点成为尾节点
last = prev;
} else {// 为空的话, 将 x 的下一个节点的 prev 指针指向 prev(x 的前一个节点)
next.prev = prev;
// x 的 next 指针置空
x.next = null;
}
//4. x 节点数据值置空
x.item = null;
//5. 链表长度 -1
size--;
modCount++;
//6. 将 x 节点的数据值返回
return element;
}大体思路:
- 首先找到 index 索引处的节点(这样就能够不便的获取该节点的前后节点), 记为 x
- 记录 x 的前 (prev) 后(next)节点
- 将 x 的前一个节点 prev 节点的 next 指针指向 next, 将 x 节点的后一个节点的 prev 指针指向 prev 节点.
- 将 x 节点置空, 链表长度 -1
3. remove(Object o)
办法作用: 从此链表中删除第一次呈现的指定元素 o
public boolean remove(Object o) {
//1. 判断 o 是否为空
if (o == null) {
// 为 null 循环, 找第一个数据值为 null 的节点
for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {
// 删除该节点
unlink(x);
return true;
}
}
} else {
// 非空 循环, 找第一个与 o 的数据值相等的节点
for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {
// 删除该节点
unlink(x);
return true;
}
}
}
return false;
}大体思路:
- 首先判断入参是否为 null
- 如果为 null, 那么循环遍历链表, 从头节点开始往后查找, 找到第一个节点的数据值为 null 的, 间接删除该节点.
- 如果非 null, 那么循环遍历链表, 从头节点开始往后查找, 找到第一个节点的数据值为 o 的, 间接删除该节点.
这里的循环遍历链表的代码, 我感觉还是比拟通用的, 从头节点开始, 通过一直的将 x 赋值为下一个元素, 直到遍历到为 null 的中央完结, 这样就完满的遍历完了链表所有节点.
4. removeFirstOccurrence(Object o)
办法作用: 从此链表中删除第一次呈现的指定元素 o. 外部其实就是下面的 remove(o);
public boolean removeFirstOccurrence(Object o) {return remove(o);
}5. removeLast()
办法作用: 移除最初一个元素并返回
public E removeLast() {
final Node<E> l = last;
// 如果链表是空的, 那么就要抛出一个谬误
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
移除链表最初一个元素
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//1. 记录尾节点数据值
final E element = l.item;
//2. 找到尾节点的前一个节点 prev
final Node<E> prev = l.prev;
//3. 将尾节点置空 不便 GC
l.item = null;
l.prev = null; // help GC
//4. 将 last 赋值为 prev
last = prev;
//5. 判断 prev 是否为 null
// 为空的话, 阐明之前链表就只有 1 个节点, 当初删了之后, 头节点和尾节点都为 null 了
// 非空, 间接将新任尾节点的 next 指针指向 null
if (prev == null)
first = null;
else
prev.next = null;
//6. 链表长度 -1
size--;
modCount++;
//7. 返回之前尾节点数据值
return element;
}大体思路:
- 判断链表是否有节点, 没有节点间接抛谬误 ….
- 首先找到倒数第二个节点(可能没有哈, 没有的话, 阐明链表只有一个节点)prev
- 而后将尾节点置空,prev 的 next 指针指向 null
6. removeLastOccurrence(Object o)
办法作用: 从此链表中删除最初一次呈现的指定元素 o.
实现: 其实和下面的 remove(o)是一样的, 只不过这里遍历时是从尾节点开始往前查找的.
public boolean removeLastOccurrence(Object o) {if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {if (x.item == null) {unlink(x);
return true;
}
}
} else {for (Node<E> x = last; x != null; x = x.prev) {if (o.equals(x.item)) {unlink(x);
return true;
}
}
}
return false;
}7. poll()
办法作用: 获取第一个元素的同时删除第一个元素, 当链表无节点时, 不会报错. 这里的 unlinkFirst()下面已剖析过.
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}8. pop()
办法作用: 获取第一个元素的同时删除第一个元素, 当链表无节点时, 会报错.
public E pop() {return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
七、批改元素
1. set(int index, E element)
办法作用: 设置 index 处节点数据值为 element
public E set(int index, E element) {
//1. 入参检测
checkElementIndex(index);
//2. 找到 index 处节点, 下面已剖析该办法
Node<E> x = node(index);
//3. 保留该节点旧值
E oldVal = x.item;
//4. 替换为新值
x.item = element;
//5. 将旧值返回
return oldVal;
}大体思路: 非常简单, 就是首先找到 index 处节点, 替换该节点数据值
八、查问元素
1. element()
办法作用: 获取链表第一个元素. 办法比较简单, 就是将链表头节点数据值进行返回
public E element() {return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}2. get(int index)
办法作用: 获取指定索引处元素. 办法比较简单, 就是通过 node(index)找到 index 索引处节点, 而后返回其数据值
public E get(int index) {
//1. 入参检测
checkElementIndex(index);
//2. 获取指定索引处节点数据值
return node(index).item;
}3. getFirst()
办法作用: 获取链表第一个元素. 非常简单, 就是将 first 的数据值返回
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}4. getLast()
办法作用: 获取链表最初一个元素. 非常简单, 就是将 last 的数据值返回
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}5. 通过 listIterator()遍历
这也是查问的一种, 哈哈
咱们先来看看 listIterator(int index) 办法, 就是 new 了一个 ListItr 进行返回.ListItr 是 LinkedList 的外部类.
public ListIterator<E> listIterator(int index) {checkPositionIndex(index);
return new ListItr(index);
}接下来, 咱们看看这个外部类:
private class ListItr implements ListIterator<E> {
// 上一次返回的节点
private Node<E> lastReturned;
// 下一个节点
private Node<E> next;
// 下一个节点索引
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {// assert isPositionIndex(index);
// 如果是最初一个节点, 那么返回 next 是 null
// 如果不是最初一个节点, 那么找到该 index 索引处节点
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
// 判断是否还有下一个元素
return nextIndex < size;
}
// 获取下一个元素
public E next() {checkForComodification();
//1. 如果没有下一个元素 抛异样
if (!hasNext())
throw new NoSuchElementException();
//2. 记录上一次遍历到的节点
lastReturned = next;
//3. 往后移
next = next.next;
//4. 索引 +1
nextIndex++;
//5. 将遍历到的节点数据值返回
return lastReturned.item;
}
public boolean hasPrevious() {
// 判断是否还有前一个元素
return nextIndex > 0;
}
// 获取前一个元素
public E previous() {checkForComodification();
//1. 如果没有前一个元素, 则抛异样
if (!hasPrevious())
throw new NoSuchElementException();
//2. 当 next 是 null 的时候, 赋值为 last
// 不是 null 的时候, 往前挪动
lastReturned = next = (next == null) ? last : next.prev;
//3. index-1 因为是往前
nextIndex--;
//4. 将遍历到的节点数据值返回
return lastReturned.item;
}
public int nextIndex() {return nextIndex;}
public int previousIndex() {return nextIndex - 1;}
// 移除以后遍历到的元素
public void remove() {checkForComodification();
//1. 移除以后遍历到的元素为 null, 间接抛谬误
if (lastReturned == null)
throw new IllegalStateException();
//2. 记录以后节点的下一个节点
Node<E> lastNext = lastReturned.next;
//3. 删除以后节点
unlink(lastReturned);
//4. 如果 next == lastReturned, 阐明以后是从返回后遍历的, 那么将 next 赋值为下一个节点
// 如果不相等, 那么阐明是从后往前遍历的, 这时只须要将 index- 1 就行了
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
//5. 将移除的节点置空
lastReturned = null;
expectedModCount++;
}
// 设置以后正在遍历的节点的值 啥? 用 ListIterator 竟然能够在遍历的时候批改值,,666
public void set(E e) {if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
// 设置以后遍历的节点的值
lastReturned.item = e;
}
// 增加一个值
public void add(E e) {checkForComodification();
lastReturned = null;
// 如果 next 为 null, 那么增加到最初
// 否则, 将 e 元素增加到 next 的后面
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);
// 循环 往后遍历 没遍历一个节点就回调以后节点的数据值
while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();}
// 判断一下该列表是否被其余线程改过(在迭代过程中) 批改过则抛异样
final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}
}这里的 ListIterator 有点强
- ListIterator 只能用于 List 及其子类型。
- 有 add()办法, 能够往链表中增加对象
- 能够通过 hasNext()和 next()往后程序遍历, 也能够通过 hasPrevious()和 previous()实现往前遍历
- 能够通过 nextIndex()和 previousIndex()返回以后索引处的地位
- 能够通过 set()实现以后遍历对象的批改
九、总结
好了, 又到了总结的时候, 置信各位认真看完的应该对链表的基本操作十分相熟了.
上面咱们来总结一下 LinkedList 的关键点
LinkedList 关键点
- 底层是双向链表存储数据, 并且记录了头节点和尾节点
- 增加元素十分快, 如果是增加到头部和尾部的话更快, 因为曾经记录了头节点和尾节点, 只须要链接一下就行了. 如果是增加到链表的两头局部的话, 那么多一步操作, 须要先找到增加索引处的元素(因为须要链接到这里), 能力进行增加.
- 遍历的时候, 倡议采纳 forEach()进行遍历, 这样能够在每次获取下一个元素时都十分轻松 (
next = next.next;). 而后如果是通过fori和get(i)的形式进行遍历的话, 效率是极低的, 每次get(i)都须要从最后面 (或者最初面) 开始往后查找 i 索引处的元素, 效率很低. - 删除也是十分快, 只须要改变一下指针就行了, 代价很小.
本文有写的不对中央, 还请多多包涵, 欢送批评指正.
这是我的笔记的其中一篇，须要看其余笔记的请移步 https://github.com/xfhy/Andro…，欢送 star、fork.