JDK源码阅读（五）：LinkedList源码解析

乱敲代码

发布于 2019-07-09 10:58:37

2350

发布于 2019-07-09 10:58:37

文章被收录于专栏：Java系列文章Java系列文章

上次分析了LinkedList的结构和添加方法这次开始分析下面的。

上文阅读直达车: 【震精】LinkedList源码竟然可以这样玩！！注意源码版本为JDK1.8

1.删除

1.2remove()

在LinkedList中remove()和removeFirst()是相同的在LinkedList中的删除其实就是通过修改上一个节点和指向下一个节点的引用完成的,可以看下面的图片：

我们可以看到把node6的prev指向清空然后把node3的next设置成空就完成了删除的操作。看一下JDK的源码实现：

调用removeFirst,在调用removeFirst中先获取头部节点，如果头节点为空就抛异常。

调用unlinkFirst

private E unlinkFirst(Node<E> f) {         final E element = f.item;         //next 为头结点的下一个节点         final Node<E> next = f.next;         f.item = null;         // 将节点的元素以及引用都设为 null，便于垃圾回收         f.next = null;          //修改头结点为第二个节点         first = next;          //如果第二个节点为空（当前链表只存在第一个元素）         if (next == null)            //那么尾节点也置为 null             last = null;         else         //如果第二个节点不为空，那么将第二个节点的上一个引用置为 null             next.prev = null;         size--;         modCount++;         return element;     }

1.3 removeLast()

我们看一下removeLast，从列表中删除最后一个元素

首先看到先获取了last最后一个元素，如果为空然后就抛异常然后调用了unlinkLast

看到unlinkLast方法中有一个 help gc ,它的主要作用就是帮助GC来做垃圾回收。

private E unlinkLast(Node<E> l) {       // assert l == last && l != null;         final E element = l.item;         final Node<E> prev = l.prev;         l.item = null;          //帮助GC垃圾回收         l.prev = null;         //尾节点为倒数第二个节点         last = prev;         //如果倒数第二个节点为null         if (prev == null)            //那么将节点也置为 null             first = null;         else             prev.next = null;        //如果倒数第二个节点不为空，那么将倒数第二个节点的下一个引用置为 null         size--;         modCount++;         return element;     }

同样执行了modCount++

1.3 remove(int index)

根据索引来删除元素

  //删除此列表中指定位置的元素      public E remove(int index) {          //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常          checkElementIndex(index);          return unlink(node(index));      }      E unlink(Node<E> x) {          // assert x != null;          final E element = x.item;         final Node<E> next = x.next;         final Node<E> prev = x.prev;
         if (prev == null) {//如果删除节点位置的上一个节点引用为null（表示删除第一个元素）             first = next;//将头结点置为第一个元素的下一个节点         } else {//如果删除节点位置的上一个节点引用不为null             prev.next = next;//将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点（去掉删除节点）             x.prev = null;//删除节点的上一个节点引用置为null         }
         if (next == null) {//如果删除节点的下一个节点引用为null（表示删除最后一个节点）             last = prev;//将尾节点置为删除节点的上一个节点         } else {//不是删除尾节点             next.prev = prev;//将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点             x.next = null;//将删除节点的下一个节点引用置为null         }        //删除节点内容置为null，便于垃圾回收         x.item = null;         size--;         modCount++;         return element;     }

3.修改 set(int index, E element)

简单粗暴直接贴代码

public E set(int index, E element) {        //检查索引是否合法否则IndexOutOfBoundsException异常        checkElementIndex(index);        //获取指定索引的元素        Node<E> x = node(index);        E oldVal = x.item;        //将指定索引的元素替换成新的元素        x.item = element;        /返回指定索引位置原来的元素        return oldVal;/    }

4.查找元素

很简单

4.1 getFirst()

返回第一个元素

  public E getFirst() {            获取头         final Node<E> f = first;            判断是否为空         if (f == null)             throw new NoSuchElementException();        元素返回         return f.item;     }

4.2 getLast()

返回最后一个元素

public E getLast() {         final Node<E> l = last;         if (l == null)             throw new NoSuchElementException();         return l.item;     }

4.3 get

返回指定索引元素

public E get(int index) {         checkElementIndex(index);         return node(index).item;     }

暂时就这么多

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-07-01，如有侵权请联系 cloudcommunity@tencent.com 删除

jdk

node.js

http

本文分享自乱敲代码微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

jdk

node.js

http

登录后参与评论

0 条评论

热度