本文内容基于 jdk1.8 环境
本文最先发布于我的个人博客，简书为同步发布，如有需要，请访问 腿短快跑的个人博客 获取更多内容
源码获取
jdk 源码在我们 jdk 的安装目录下即可找到：
jdk1.8
在 jdk1.8 及之前的版本中，jdk的源码均可在安装目录的根目录下找到src.zip，此包即为 jdk 源码jdk11
从 jdk11 开始，jdk的源码包放在 jdk 安装目录下的 lib 目录下，在 lib 目录下找到src.zip即为源码
实现接口
LinkedList 实现了以下接口：
List
实现了 List 接口，Java集合框架中常用接口Deque
双端队列接口，用于实现队列功能Cloneable
克隆接口，用于实现两个 List 之间的克隆Serializable
序列化接口
节点结构
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;
}
}
- item：当前节点的实际元素值
- next：当前节点的后继节点
- prev：当前节点的前驱节点
核心属性
// LinkedList实际长度
transient int size = 0;
// 开始节点
transient Node<E> first;
// 结束节点
transient Node<E> last;
从上述代码中我们可以得出以下结论：
- LinkedList 使用链表方式存储
- LinkedList 支持头节点和尾节点，因此 LinkedList 是一个双向链表
- LinkedList 支持读少写多的场景
核心方法
构造方法
用于初始化 LinkedList，还有一个无参构造函数，里面没有做任何逻辑，此处不做分析
/**
* 集合的构造器
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
// 调用默认无参构造器，创建一个空LinkedList
this();
// 将集合的元素全部添加进去
addAll(c);
}
/**
* 批量将一个集合的元素值添加到链表中(尾部)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// 从size位置添加一个集合的元素
return addAll(size, c);
}
/**
* 在指定位置添加一个集合的元素
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查位置是否出现越界，越界则抛出异常
checkPositionIndex(index);
// 集合转换为数组
Object[] a = c.toArray();
// 获取要添加的长度
int numNew = a.length;
if (numNew == 0)
// 没有需要添加长度
return false;
Node<E> pred, succ;
if (index == size) {
// 索引位置是最后，当前索引位置的元素设置为null
succ = null;
// 前驱节点设置为last节点
pred = last;
} else {
// 找到指定索引的元素
succ = node(index);
// 前驱节点设置为指定索引的节点的前驱节点
pred = succ.prev;
}
// 遍历要添加的元素的数组
for (Object o : a) {
// 创建一个新的元素
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// 前驱节点为null，新节点为第一个节点
first = newNode;
else
// 前驱节点不为null，新节点设置为前驱节点的next节点
pred.next = newNode;
// 前驱节点向后移动一位
pred = newNode;
}
if (succ == null) {
// 指定索引位置的节点为null，说明在尾部插入的，last节点设置为最后一个前驱节点
last = pred;
} else {
// 指定索引位置的节点不为null，说明在中间位置插入的，将前驱节点的next节点设置为指定索引的节点，指定索引的节点的前驱节点设置为前驱节点
pred.next = succ;
succ.prev = pred;
}
// 链表长度增加
size += numNew;
// 修改数量增加
modCount++;
return true;
}
- 调用无参构造函数，创建一个空的 LinkedList
- 批量添加元素
- 调用从指定指定索引位置批量添加元素的方法，指定索引位置为当前 size 大小
- 进行索引位置检查，如果出现索引位置越界的情况，直接抛出异常
- 将集合转换为 Object 数组方便后续操作
- 如果数组的长度为 0，没有节点需要添加，则直接返回
- 标识指定索引位置的节点(succ)和该节点的前驱节点(pred)
- 如果指定的索引位置是 size，即在 LinkedList 结尾添加元素
- 将 succ 节点设置为null
- 将 pred 节点设置为 last 节点
- 如果指定的索引位置不是 size，则在 LinkedList前面或中间添加元素
- 将 succ 节点设置为指定索引的节点
- 将 pred 节点设置为 succ 的前驱节点
- 遍历要添加的数组
- 创建一个新的节点，前驱节点为 pred，后继节点为 null
- 如果 pred 节点为 null，则说明在开头位置插入，将 first 节点设置为新的节点
- 如果 pred 节点不为 null，则说明在中间位置插入，将 pred 设置为新的节点
- 如果 succ 节点为 null，则说明在尾部插入的，将 last 节点设置为 pred 节点
- 如果 succ 节点不为 null。则说明在中间位置插入的，将 pred 节点的后继节点设置为 succ 节点，将 succ 节点的前驱节点设置为 pred 节点
- 将链表长度增加集合的长度
- 将修改次数增加
- 返回修改结果
- 调用从指定指定索引位置批量添加元素的方法，指定索引位置为当前 size 大小
getFirst()
用于获取 LinkedList 头节点数据
/**
* 获取第一个节点
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
// 获取first节点
final Node<E> f = first;
if (f == null)
// first节点为null，链表没有初始化，抛出异常
throw new NoSuchElementException();
// 返回first节点的元素值
return f.item;
}
- 获取 first 节点
- 如果 first 节点为 null，则说明链表没有初始化，直接抛出异常
- 返回 first 节点的数据
getLast()
获取 LinkedList 尾节点数据
/**
* 获取最后一个节点
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
// 获取last节点
final Node<E> l = last;
if (l == null)
// last节点为null，链表没有初始化，抛出异常
throw new NoSuchElementException();
// 返回last节点的元素值
return l.item;
}
- 获取 last 节点
- 如果 last 节点为 null，则说明链表没有初始化，直接抛出异常
- 返回 last 节点的数据
removeFirst()
移除链表表头元素
/**
* 移除第一个元素
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
// 获取first节点
final Node<E> f = first;
if (f == null)
// first节点为null，链表没有初始化，抛出异常
throw new NoSuchElementException();
// 调用移除第一个节点
return unlinkFirst(f);
}
/**
* 移除头节点
*/
private E unlinkFirst(Node<E> f) {
// 获取first节点的元素内容
final E element = f.item;
// 获取first节点的下一个节点
final Node<E> next = f.next;
// 将first节点的内容设置为null，帮助jvm gc
f.item = null;
// 将first节点的下一个节点也设置为null，帮助jvm gc
f.next = null; // help GC
// 将下一个节点设置为first节点
first = next;
if (next == null)
// 如果下一个节点为空，则说明链表为空，将last节点也设置为null
last = null;
else
// 如果下一个节点不为空，则说明链表不为空，将下一个节点的前驱节点设置为null，下一个节点就彻底成为了头节点
next.prev = null;
// 链表长度-1
size--;
// 修改次数增加
modCount++;
// 返回旧的链表的头部内容
return element;
}
- 获取 first 节点
- 如果 first 节点为 null，则说明链表没有初始化，直接抛出异常
- 调用 unlinkFirst() 来移除队首元素
- 获取 first 节点的值为 element
- 获取 first 节点的后继节点为 next 节点
- 将 first 节点内容设置为 null，帮助 gc
- 将 first 节点的后继节点设置为 null，帮助 gc
- 将 next 节点赋值给 first 节点
- 如果 next 节点为 null，则说明链表已经为空了，将 last 节点也设置为 null
- 如果 next 节点不为 null，则说明链表还有数据，将 next 几点的前驱节点设置为 null，这样 next 节点就彻底成为了头节点
- 将链表长度-1
- 修改次数增加
- 返回 element 数据
removeLast()
移除链表表尾元素
/**
* 移除最后一个元素
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
// 获取last节点
final Node<E> l = last;
if (l == null)
// last节点为null，链表没有初始化，抛出异常
throw new NoSuchElementException();
// 调用移除最后一个元素
return unlinkLast(l);
}
/**
* 移除尾节点
*/
private E unlinkLast(Node<E> l) {
// 获取节点的元素
final E element = l.item;
// 获取节点的前一个节点
final Node<E> prev = l.prev;
// 将节点的元素设置为null，帮助jvm gc
l.item = null;
// 将节点的前驱节点设置为null，帮助jvm gc
l.prev = null; // help GC
// 将节点的前一个节点设置为last节点
last = prev;
if (prev == null)
// 如果前一个节点为null，则说明链表为空，将first节点设置为null
first = null;
else
// 如果前一个节点不为null，则说明链表不为空，将前一个节点的后继节点设置为null，前一个节点就彻底成为了尾节点
prev.next = null;
// 链表长度-1
size--;
// 修改次数增加
modCount++;
// 返回节点的元素
return element;
}
- 获取 last 节点
- 如果 last 节点为 null，则说明链表没有初始化，直接抛出异常
- 调用 unlinkLast() 来移除队尾元素
- 获取 last 节点的值为 element
- 获取 last 节点的前驱节点为 prev 节点
- 将 last 节点的值设置为 null，帮助 gc
- 将 last 节点的前驱节点设置为 null，帮助 gc
- 将 last 节点设置为 prev 节点
- 如果 prev 节点为 null，则说明链表为空，将 first 节点设置为 null
- 如果 prev 节点不为 null，则说明链表不为空，将 prev 节点的后继节点设置为 null，prev 节点就彻底成了尾节点
- 链表长度-1
- 修改次数增加
- 返回 element 值
addFirst(E e)
在链表头部添加数据
/**
* 在头部插入元素
*
* @param e the element to add
*/
public void addFirst(E e) {
// 调用在头部插入元素
linkFirst(e);
}
/**
* 将元素插入表头
*/
private void linkFirst(E e) {
// 当前first节点赋值给f
final Node<E> f = first;
// 创建一个新的节点，节点的前置节点为null，数据为e，后置节点为f
final Node<E> newNode = new Node<>(null, e, f);
// first节点指向
first = newNode;
if (f == null)
// 原first节点为null，说明链表为空链表，此为第一个节点，将last节点指向新节点
last = newNode;
else
// 原来first节点不为null，说明链表已经不为空，将f的前驱节点设置为新的节点
f.prev = newNode;
// 链表长度增加
size++;
// 修改次数增加
modCount++;
}
- 调用 linkFirst 在头部插入元素
- 创建一个新的节点，前置节点为 null，后置节点为 first 节点
- 将 first 节点指向新的节点
- 如果 原first 节点为 null，则说明原链表为空，新节点为唯一的节点，将 last 节点指向新的节点
- 如果 原first 节点不为 null，则说明原链表不为空，将 原first 节点的前驱节点设置为新的节点
- 链表长度增加
- 修改次数增加
<span id="addLast"></span>
addLast(E e)
在链表尾部添加元素
/**
* 在尾部插入元素
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
// 调用在尾部插入元素
linkLast(e);
}
/**
* 将元素插入表尾
*/
void linkLast(E e) {
// 将之前的last节点赋值给l
final Node<E> l = last;
// 创建一个新的节点，前驱节点是l，内容是e，后继节点是null
final Node<E> newNode = new Node<>(l, e, null);
// 将新的节点赋值给last节点
last = newNode;
if (l == null)
// 如果旧的last节点为null，则说明新的节点是第一个节点，新节点设置为first节点
first = newNode;
else
// 如果旧的last节点不为null，则说明新的节点不是第一个节点，新节点挂在旧的last节点的后继节点上
l.next = newNode;
// 链表长度增加
size++;
// 修改次数增加
modCount++;
}
- 调用 linkLast 在尾部插入节点
- 创建一个新的节点，前驱节点为 last 节点，后继节点为 null
- 将 last 节点指向新的节点
- 如果 原last 节点为 null，则说明原链表为空，新节点为唯一的节点，将 first 节点指向新的节点
- 如果 原last 节点不为 null，则说明原链表不为空，将 原last 节点的后继节点设置为新的节点
- 链表长度增加
- 修改次数增加
contains(Object o)
用于判读元素是否在 LinkedList 中
/**
* 判断元素是否包含在链表中
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
// 判断元素的索引位置是否!=-1
return indexOf(o) != -1;
}
- 调用 indexOf 方法获取元素出现的索引位置
- 判断出现的索引位置是否为 -1，-1表示不包含，其他表示包含
add(E e)
在链表末尾添加元素
/**
* 添加元素(元素末尾)
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 在元素末尾添加元素
linkLast(e);
// 返回结果
return true;
}
实现方式等同于 addLast(E e) 方法
<span id="remove_o"></span>
remove(Object o)
用于删除链表中的指定元素
/**
* 删除元素
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
// 如果o为null，遍历链表
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
// 找到第一个节点值为null的节点，移除此节点
unlink(x);
return true;
}
}
} else {
// 如果o不为null，遍历链表
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
// 找到第一个元素值和o equals的节点，移除此节点
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节点
first = next;
} else {
// 前驱节点存在，将前驱节点的next设置为后继结点
prev.next = next;
// 将当前节点的前驱节点设置为null
x.prev = null;
}
if (next == null) {
// 后继节点为空，则说明没有后继节点了，将前驱节点赋值给 last 节点
last = prev;
} else {
// 后继节点不为空，则说明存在后继节点，将后继结点的前驱节点设置为前驱节点
next.prev = prev;
// 将当前节点的后继节点设置为 null
x.next = null;
}
// 将当前节点的元素值设置为null
x.item = null;
// 链表长度 -1
size--;
// 修改次数增加
modCount++;
// 返回当前节点的元素值
return element;
}
- 如果值为 null，遍历链表，找到第一个值为 null 的节点，调用 unlink 删除节点
- 如果值不为 null，遍历链表，找到第一个值和 o equals 的节点，调用 unlink 删除节点
unlink步骤
- 获取当前节点的值为 element
- 获取当前节点的前驱节点（prev）和后继节点（next）
- 如果 prev 节点为 null，则说明当前节点是第一个节点，将 first 节点直接指向 next 节点（因为要移除本节点，所以 first 节点不需要指向当前节点）
- 如果 prev 节点不为 null，则说明当前节点不是第一个节点，将 prev 节点的后继节点指向 next 节点，将当前节点的前驱节点设置为 null，帮助 gc
- 如果 next 节点为 null，则说明当前节点是最后一个节点，将 last 节点指向 prev 节点
- 如果 next 节点不为 null，则说明当前节点不是最后一个节点，将 next 节点的前驱节点指向 prev 节点，将当前节点的后继节点设置为 null，帮助 gc
- 将当前节点的数据设置为 null，帮助 gc
- 链表长度-1
- 修改次数增加
- 返回当前节点的值 element
addAll(Collection<? extends E> c)
将一个集合的节点新增到 LinkedList 中
/**
* 批量将一个集合的元素值添加到链表中(尾部)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// 从size位置添加一个集合的元素
return addAll(size, c);
}
调用 addAll(int index, Collection<? extends E> c) 方法来添加元素，其中 index 的位置为 size，即：从队尾位置开始添加
addAll(int index, Collection<? extends E> c)
将一个集合添加到指定位置
/**
* 在指定位置添加一个集合的元素
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查位置是否出现越界，越界则抛出异常
checkPositionIndex(index);
// 集合转换为数组
Object[] a = c.toArray();
// 获取要添加的长度
int numNew = a.length;
if (numNew == 0)
// 没有需要添加长度
return false;
Node<E> pred, succ;
if (index == size) {
// 索引位置是最后，当前索引位置的元素设置为null
succ = null;
// 前驱节点设置为last节点
pred = last;
} else {
// 找到指定索引的元素
succ = node(index);
// 前驱节点设置为指定索引的节点的前驱节点
pred = succ.prev;
}
// 遍历要添加的元素的数组
for (Object o : a) {
// 创建一个新的元素
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// 前驱节点为null，新节点为第一个节点
first = newNode;
else
// 前驱节点不为null，新节点设置为前驱节点的next节点
pred.next = newNode;
// 前驱节点向后移动一位
pred = newNode;
}
if (succ == null) {
// 指定索引位置的节点为null，说明在尾部插入的，last节点设置为最后一个前驱节点
last = pred;
} else {
// 指定索引位置的节点不为null，说明在中间位置插入的，将前驱节点的next节点设置为指定索引的节点，指定索引的节点的前驱节点设置为前驱节点
pred.next = succ;
succ.prev = pred;
}
// 链表长度增加
size += numNew;
// 修改数量增加
modCount++;
return true;
}
- 检查是否出现越界，如果出现越界，直接抛出异常
- 将集合转换为 Object 数组
- 如果集合的长度为 0，则直接结束，不做操作
- 使用 succ 表示后继节点，pred 表示前驱节点
- 如果指定的索引大小为 size，则说明从队尾添加，succ 节点为 null，pred 节点为 last 节点
- 如果指定的索引大小不为 size，则说明从队列中间田间，succ 节点为指定索引位置的节点，pred 节点为 succ 节点的前驱节点
- 遍历数组
- 创建一个新的节点，前驱节点为 pred 节点，后继节点为 null
- 如果 pred 节点为 null，则表示没有前驱节点，新节点应该是第一个节点，将 first 节点指向新节点
- 去过 pred 节点不为 null，则表示有前驱节点，新节点设置为 pred 节点的后继节点
- pred 节点设置为新节点，表示向后移动一位，方便下次循环新增节点
- 如果 succ 节点为 null，说明在尾部插入的，将 last 节点指向 pred 节点（因为 pred 节点在循环中表示了最后一个新增的节点）
- 如果 succ 节点不为 null，说明在中间插入的，将 pred 节点的后继节点设置为 succ 节点，succ 节点的前驱节点设置为 pred 节点
clear()
清空 LinkedList
/**
* 清空链表
*/
public void clear() {
// 遍历链表
for (Node<E> x = first; x != null; ) {
// 获取下一个节点
Node<E> next = x.next;
// 当前节点数据置空
x.item = null;
// 当前节点的下一个节点置空
x.next = null;
// 当前节点的前一个节点置空
x.prev = null;
// 当前节点设置为下一个节点
x = next;
}
// 前后节点均置为空
first = last = null;
// 长度设置为0
size = 0;
// 修改次数增加
modCount++;
}
- 从 first 节点开始遍历
- 获取当前节点的后继节点为 next
- 将当前节点的数据设置为 null，帮助 gc
- 将当前节点的后继节点设置为 null，帮助 gc
- 将当前节点的前驱节点设置为 null，帮助 gc
- 将当前节点指向 next 节点继续遍历
- 将 first 节点和 last 节点都设置为 null
- 将长度设置为0
- 修改次数增加
<span id="get_index"></span>
get(int index)
获取指定索引位置的节点值
/**
* 获取指定索引位置的元素
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
// 范围检查，如果出现越界问题，抛出异常
checkElementIndex(index);
// 返回指定索引位置的节点的元素值
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;
}
}
- 进行范围检查，如果出现越界问题，直接抛出异常
- 调用 node(int index) 方法获取指定的节点
- 判断指定的索引是在链表的前半部分还是在后半部分（通过不同的情况，从不同的方向遍历，从而提升性能）
- 如果索引是在链表的前半部分，则从 first 节点开始遍历
- 如果索引是在链表的后半部分，则从 last 节点开始遍历
- 遍历 LinkedList，找到对应的索引节点，返回节点
- 返回节点的数据
set(int index, E element)
设置指定索引位置的节点的值
/**
* 设置指定索引位置的节点的值
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
// 范围检查，如果出现越界问题，抛出异常
checkElementIndex(index);
// 获取指定索引位置的节点
Node<E> x = node(index);
// 获取节点的值
E oldVal = x.item;
// 节点的值设置为新的值
x.item = element;
// 返回节点的旧值
return oldVal;
}
- 进行范围检查，如果出现越界问题，直接抛出异常
- 调用 node(int index) 方法获取指定索引位置的节点，参考 get(int index) 方法
- 获取节点的值
- 将节点的值设置为新的值
- 返回节点的旧值
add(int index, E element)
在指定索引位置添加节点
/**
* 在指定位置新增元素
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 范围检查，如果出现越界问题，抛出异常
checkPositionIndex(index);
if (index == size)
// 如果索引位置是最后，则在最后新增
linkLast(element);
else
// 如果索引位置不是最后，在指定节点的前面添加
linkBefore(element, node(index));
}
/**
* 将元素插入指定节点的前面
*/
void linkBefore(E e, Node<E> succ) {
// 获取指定节点的前驱节点pred
final Node<E> pred = succ.prev;
// 创建一个新的节点，前驱节点为pred，元素值为e，后继节点为指定节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将指定节点的前驱节点设置为新的节点
succ.prev = newNode;
if (pred == null)
// 如果前驱节点pred是空，则说明新的节点是头节点，将新的节点赋值给first节点
first = newNode;
else
// 如果前驱节点pred不为空，则说明链表不为空，将前驱节点pred的后继节点设置为新的节点
pred.next = newNode;
// 增加链表的长度
size++;
// 增加修改次数
modCount++;
}
- 进行范围检查，如果出现数组越界，直接抛出异常
- 如果指定的索引为 size，则说明从尾部添加，调用 linkLast 方法，具体步骤参考 addLast(E e) 方法
- 如果指定的索引不为 size，则说明不是从尾部添加，调用 linkBefore 方法添加
- 获取当前指定位置的节点的前驱节点 pred
- 创建一个新的节点，前驱节点为 pred，后继节点为指定位置的节点
- 将指定节点的前驱节点设置为新的节点
- 如果 pred 节点为 null，说明新加的节点为第一个节点，将 first 节点指向新加的节点
- 如果 pred 节点不为 null，说明新加的节点不是第一个节点，将 pred 节点的后继节点指向新节点
- 增加链表的长度
- 修改次数增加
remove(int index)
移除指定索引位置的节点
/**
* 删除指定位置的节点
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
// 范围检查，如果出现越界问题，抛出异常
checkElementIndex(index);
// 移除指定位置的节点
return unlink(node(index));
}
- 进行范围检查，如果出现越界问题，直接抛出异常
- 调用 node(int index) 方法获取指定索引位置节点，参考 get(int index) 方法
- 调用 unlink 方法移除指定节点，参考 remove(Object o) 方法
indexOf(Object o)
获取指定元素第一次出现的位置
/**
* 获取元素对应的第一次出现位置
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
// 如果元素值为null，从头开始遍历
for (Node<E> x = first; x != null; x = x.next) {
// 找到第一个元素值为null的节点，返回对应的位置
if (x.item == null)
return index;
index++;
}
} else {
// 如果元素值不为null。从头开始遍历
for (Node<E> x = first; x != null; x = x.next) {
// 找到第一个元素值和o equals的节点，返回对应的位置
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
- 如果值为 null，从 first 节点开始遍历，找到第一个节点值为 null 的节点，返回对应的位置
- 如果值不为 null，从 first 节点开始遍历，找到第一个节点值和 o equals 的节点，返回对应的位置
- 如果没有找到，返回 -1
lastIndexOf(Object o)
获取指定元素最后一次出现的位置
/**
* 获取元素对应的最后一次出现的位置
*
* @param o element to search for
* @return the index of the last occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
// 如果元素值为null，从尾部开始遍历
for (Node<E> x = last; x != null; x = x.prev) {
index--;
// 找到第一个元素值为null的节点，返回对应的位置
if (x.item == null)
return index;
}
} else {
// 如果元素值不为null，从尾部开始遍历
for (Node<E> x = last; x != null; x = x.prev) {
index--;
// 找到第一个元素值和o equals的节点，返回对应的位置
if (o.equals(x.item))
return index;
}
}
// 未找到，返回-1
return -1;
}
- 如果值为 null，从 last 节点开始遍历，找到第一个节点值为 null 的节点，返回对应的位置
- 如果值不为 null，从 last 节点开始遍历，找到第一个节点值和 o equals 的节点，返回对应的位置
- 如果没有找到，返回 -1
总结
- LinkedList 也是 List 的一个实现类
- LinkedList 底层使用链表实现
- LinkedList 适合写多读少的场景（读需要每次从头开始遍历，不支持随机访问）
关注我获取更多知识
[图片上传失败...(image-3d7f32-1653952195249)]
关注发送关键词 全栈资料 获取 34G 学习资源，无任何套路
关注发送关键词 面试 获取 面试手册，无任何套路
