面试官问你LinkedList?把这篇文章甩给他
本文内容基于 jdk1.8 环境
本文最先发布于我的个人博客,CSDN为同步发布,如有需要,请访问 腿短快跑的个人博客 获取更多内容
源码获取
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 节点的前驱节点设置为新的节点
- 链表长度增加
- 修改次数增加
addLast(E e)
在链表尾部添加元素
/** * 在尾部插入元素 * * 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 中
/** * 判断元素是否包含在链表中 * (o==null ? e==null : o.equals(e)). * * @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) 方法
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 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 c) 方法来添加元素,其中 index 的位置为 size,即:从队尾位置开始添加
addAll(int index, Collection 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
- 修改次数增加
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 适合写多读少的场景(读需要每次从头开始遍历,不支持随机访问)
关注我获取更多知识
关注发送关键词 全栈资料
获取 34G 学习资源,无任何套路
关注发送关键词 面试
获取 面试手册,无任何套路