Java源码阅读之LinkedList - JDK1.8
阅读优秀的源码是提升编程技巧的重要手段之一。 如有不对的地方，欢迎指正~ 转载请注明出处https://blog.lzoro.com。 前言 前文基于缓冲数组的ArrayList已经分析过，那么同样作为List实现的LinkedList又有什么不一样呢？ image 在阅读LinkedList源码之前，开头处先简单总结一下两者的区别 ArrayList 基于缓冲数组进行数据存储 查询/修改方便，因为基于下标容易定位数据 插入/删除不方便，需要移动数据 LinkedList 基于双向链表进行数据存储 查询/修改不方便，因为要移动指针 插入/删除方便，因为基于指针，不需要移动数据 带着这些概念，再次打开你的IDE，挽起袖子，开撸代码，加上注释，总计1262行代码，比ArrayList还少呢。 基本介绍 静态常量 嗯，没有，你没看错，LinkedList内部没有含业务属性的静态常量。 image 成员变量 工欲善其事，必先利其器。 虽然没什么太大关系，但为了提供逼格还是来了个引用。 要透彻理解整个LinkedList，那首先得先了解下它的内部提供了哪些成员变量，分别是做什么用的，这样有助于我们在看功能方法时提高效率。 其实，LinkedList内部定义的成员变量也少，但是没办法，谁让我为了提升篇幅，多说两句了。 image /** * 大小 */ transient int size = 0; /** * 首节点 * 恒定的: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * 尾节点 * 恒定的: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; 可以看出来首节点/尾节点都是Node<E>的实例，那么Node<E>是何方神圣呢 它是一个私有的静态内部类，内部定义了当前元素和前置/后继指针，和一个构造函数，是整个双向链表的基础。 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; } } 构造函数 /** * 构造一个空的List */ public LinkedList() { } /** * 根据给定的集合构造一个List * * @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) { //调用上面的构造函数 this(); //添加集合到List中 addAll(c); } 简洁明了。你应该也注意到了第二个构造函数中的addAll方法，看名字也知道是将集合c中的所有元素添加到LinkedList中。所以不能错过，往下看 image 可以看到，addAll(Collection<? extends E> c)是调用addAll(int index, Collection<? extends E> c)的，而这两个方法都是public的，第一个方法是在链表尾部添加指定的集合，而第二个方法比第一个方法多了一个参数，用来指定在某个位置添加指定集合。 /** * 将指定集合的所有元素添加都list尾部 * * 如果操作过程中指定的集合被修改，则此操作的行为未定义。 * (注意，如果指定的集合是该列表，并且它不是空的，则会发生这种情况。) * 其实就是线程不安全。 * * @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) { 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; //如果是空集合，则返回false if (numNew == 0) return false; //定义前置/继任节点 Node<E> pred, succ; //如果指定的位置是尾部(index==size) //无论当前链表是不是空的，只要index==size，就是往尾部插入元素 if (index == size) { //继任节点为null succ = null; //前置节点就是最后一个节点 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) first = newNode; else pred.next = newNode; pred = newNode; } //如果没有继任节点 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } //修改大小 size += numNew; //修改操作计数 modCount++; return true; } 这里的addAll添加一个集合的元素操作，整体逻辑还是比较清晰的，包含了指定集合c的非空判断，插入位置判断，断开链表，修改引用，后续判断和修改计数。 功能方法 了解了一些基础之后，那就该上大菜了。 接下来阅读，平时我们用的比较频繁的一些功能方法的源码。 还是老生常谈，对于这种集合框架来说，常用方法无外乎增/删/改/查。 另外，由于LinkedList不仅实现了List接口，还实现了Deque双端队列接口，所以也提供了队列相关方法。 add 跟ArrayList一样，LinkedList的添加也分为几类 尾部添加单个元素 指定位置添加单个元素 尾部添加集合元素 指定位置添加集合元素 首位添加 由于集合元素的添加，在上面构造函数章节已经提过，这里就不再赘述。 着重看一下单个元素的添加。 /** * 尾部添加元素，返回true * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { //调用linkLast，后续分析 linkLast(e); return true; } /** * 指定位置添加元素 * * @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，后续分析 linkBefore(element, node(index)); } /** * 头部插入 * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); } /** * 尾部插入 * * @param e the element to add */ public void addLast(E e) { linkLast(e); } 方法都很简单，没有什么操作逻辑，可以看出来，是linkLast/linkFirst/linkBefore在提供实际实现。 /** * 作为首节点 */ private void linkFirst(E e) { //取出当前首节点 final Node<E> f = first; //创建新节点 final Node<E> newNode = new Node<>(null, e, f); //用新节点替换首节点 first = newNode; //如果原来的首节点不存在的话 if (f == null) //当前只有一个节点，则首位节点都是同一个 last = newNode; else //原来的首节点后移 f.prev = newNode; //修改计数 size++; modCount++; } /** * 作为尾节点 */ void linkLast(E e) { //取出当前尾节点 final Node<E> l = last; //根据给定元素创建新节点 final Node<E> newNode = new Node<>(l, e, null); last = newNode; //判断原来的尾节点是否存在 if (l == null) //与上面同理 first = newNode; else //原来的尾节点前移 l.next = newNode; //修改计数 size++; modCount++; } /** * 在非null继任节点前插入 */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); //其实就是从指定节点断开连接，修改指针引用 succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } 看完上面内容，大概也就能了解为什么LinkedList适合插入/删除节点了，因为插入操作对于LinkedList来说，不需要移动数据，只需要在指定位置修改指针引用即可，即，断开->插入->修改引用。 移除其实也是同样的道理，即，断开->移除->修改引用。 remove 移除分为以下几种 根据下标移除 根据对象移除 移除头部(实现Deque接口的方法) 移除尾部((实现Deque接口的方法) 移除首个匹配的对象(实现Deque接口的方法) 移除最后一个匹配的对象(实现Deque接口的方法) /** * 根据下标移除元素，并移动相关指针 * * @param index 要移除元素的下标 * @return 返回删除元素的前一个元素 * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { //下标合法性判断 checkElementIndex(index); //调用node进行节点查找之后调用unlink进行移除 //后续分析这两个方法 return unlink(node(index)); } /** * 如果存在的话从list中移除第一个匹配的元素 * 如果不存在，则list不改变 * * 更正式点说，是移除在低位匹配到的元素 * 如下所示 * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> * (假如元素存在). * Returns {@code true} 如果列表存在元素 (等价理解，该链表被改变). * * @param o 要移除的元素 * @return {@code true} 如果存在要移除的元素 */ public boolean remove(Object o) { //先判断要移除的元素是不是null if (o == null) { //从首节点遍历查找 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { //匹配到null，在调用unlink移除(之后分析这个方法) unlink(x); return true; } } //要移除的元素不是 null } else { //仍然是遍历，不过比较方法换成equals for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 移除并返回首个元素 * * @return 返回list首元素 * @throws NoSuchElementException list为空时，抛异常 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); //调用unlinkFirst，后面和unlink一起分析 return unlinkFirst(f); } /** * 移除并返回尾部元素 * * @return 返回list尾元素 * @throws NoSuchElementException list为空时，抛异常 */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); ////调用unlinkLast，后面和unlink一起分析 return unlinkLast(l); } /** * 从list头部->尾部进行遍历，如果存在指定元素的话，则移除第一个匹配的元素，如果不存在，则list不改变 * * @param o 要移除的元素 * @return {@code true} 如果存在的话，返回true * @since 1.6 */ public boolean removeFirstOccurrence(Object o) { //直接调用remove(o)，因为remove(o)就是从头部遍历并移除第一个匹配的元素 return remove(o); } /** * 从list尾部->头部进行遍历，如果存在指定元素的话，则移除第一个匹配的元素，如果不存在，则list不改变 * * @param o 要移除的元素 * @return {@code true} 如果存在的话，返回true * @since 1.6 */ public boolean removeLastOccurrence(Object o) { //判断o是不是null，如果是null，则用==比较 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; } //上面这个方法，通过条件分支，循环在两个分支里都有，看似可以抽离循环，然后再循环内部判断o==null来精简代码。 //但是实际上，把o==null抽离出来循环之外，虽然多写了些代码，但是不用在每次循环中做两次判断，可以提供效率。 //如果有类似的场景，我们也可以参考这种写法。 好了，看完上面的remove类方法，遗留了几个实际实现node、unlink、unlinkFirst、unlinkLast未阅读，下面继续 /** * 返回非指定位置的非null节点 */ Node<E> node(int index) { // assert isElementIndex(index); //判断下标在list的上游/下游 //如果是上游的话，从头部进行查找 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; } } /** * 移除非null节点x */ E unlink(Node<E> x) { // assert x != null; //取出元素待返回 final E element = x.item; //取出x的前/后节点 final Node<E> next = x.next; final Node<E> prev = x.prev; //如果前置节点不存在，则证明x是首节点 if (prev == null) { //首节点指向x的后置节点 first = next; } else { //如果x不是首节点 //则将x的前置节点与后置节点相连 prev.next = next; //x与前置节点断开 x.prev = null; } //如果x的后置节点不存在，则证明x是尾节点 if (next == null) { //尾节点指向x的前置节点 last = prev; } else { //如果不是尾节点 //则将x的尾首节点相连 //修改引用 next.prev = prev; //x与后置节点断开 x.next = null; } //x的元素置null x.item = null; //size - 1 size--; //操作计数 + 1 modCount++; return element; } /** * 移除非null的f首节点. */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; //老规矩，取出f节点元素，待返回 final E element = f.item; //取出f的后置节点 final Node<E> next = f.next; //下面两个置null帮助垃圾收集器进行GC f.item = null; f.next = null; // help GC //首节点指向f的后置节点 first = next; //如果后置节点不存在，证明list只有一个节点 if (next == null) //置null last = null; else //list不只一个节点 //后置节点变成首节点了，所以首节点的prev置null next.prev = null; //常规操作 size--; modCount++; return element; } /** * 移除非null的l尾节点 */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; //取出元素待返回 final E element = l.item; //取出l的前置节点 final Node<E> prev = l.prev; //两个置null帮助垃圾收集器GC l.item = null; l.prev = null; // help GC //尾节点指向l的前置节点 last = prev; //如果前置节点尾null，证明list只有一个节点 if (prev == null) //首节点置null，此时list为空 first = null; else //list不只一个节点 //前置节点变成尾节点了，所以尾节点的后置为null prev.next = null; //常规操作 size--; modCount++; return element; } set 设置/修改元素操作，需要提供下标和对应的元素，逻辑比较简单。 /** * 提供下标和元素来替换指定位置的元素 * * @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); //获取指定节点（在remove章节已经分析过该方法） Node<E> x = node(index); //进行替换 E oldVal = x.item; x.item = element; return oldVal; } get LinkedList的查找元素方式跟ArrayList有点不同，由于它是双端链表形式存储数据，所以额外提供了getFirst和getLast，方法实现都很简单，下面看一下这三个方法的实现 /** * 返回指定位置的元素 * * @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) { //这里其实也是调用node(index)方法进行定位 checkElementIndex(index); return node(index).item; } /** * 返回list的首元素 * * @return the first element in this list * @throws NoSuchElementException if this list is empty */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * 返回list的尾元素 * * @return the last element in this list * @throws NoSuchElementException if this list is empty */ public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } contains 判断list是否包含指定元素，跟ArrayList一样，通过查找元素的下标后判断下标是否存在，来判断元素是否存在，不一样的是元素的查找方法。 LinkedList是双端链表实现，所以查找方法时从首节点进行遍历。 public boolean contains(Object o) { return indexOf(o) != -1; } public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } 其他方法 其他还有一些方法，如clear以及Deque接口中定义的方法实现如offer等，避免篇幅过长，这里不一一分析，有兴趣的可自行阅读源码，实现逻辑都相对比较简单。 clear offer peek ... 只要了解了双端链表的基本原理，和常规操作，基本上内部的方法实现都能掌握得差不多，所以。 我犯懒了，就差不多分析到这里。 image 最后 惯例求点赞~~ 3Q~
