写点什么

LinkedList 源码分析 - 删除

作者:zarmnosaj
  • 2022 年 5 月 20 日
  • 本文字数:965 字

    阅读完需:约 3 分钟

LinkedList 源码分析-删除

节点删除的方式和节点追加类似,可以从头部删除,或从尾部删除。

从头部删除

源码:


    private E unlinkFirst(Node<E> f) {        // assert f == first && f != null;        final E element = f.item;        final Node<E> next = f.next;        f.item = null;        f.next = null; // help GC        first = next;        if (next == null)            last = null;        else            next.prev = null;        size--;        modCount++;        return element;    }
复制代码


  1. final E element = f.item 取出节点的值,当做方法的返回值

  2. final Node<E> next = f.next; 取出节点的下一个节点

  3. f.item = null;f.next = null; 元素置空,帮助 GC 回收节点

  4. first = next; 头节点的下一个节点成为头节点

  5. if (next == null) 如果 next 为空,表明链表为空

  6. next.prev = null;链表不为空,头节点的前一个节点指向 null

  7. size--;modCount++; 修改链表大小和版本

从尾部删除

    private E unlinkLast(Node<E> l) {        // assert l == last && l != null;                final Node<E> prev = l.prev;        l.item = null;        l.prev = null; // help GC        last = prev;        if (prev == null)            first = null;        else            prev.next = null;        size--;        modCount++;        return element;    }
复制代码


  1. final E element = l.item; 取出尾节点的值,当做方法的返回值

  2. final Node<E> prev = l.prev; 取出尾节点的上一个节点

  3. l.item = null;l.prev = null 帮助 GC 回收头节点

  4. last = prev; 尾节点的上一个节点成为尾节点

  5. if (prev == null) 如果 prev 为空,表明链表为空

  6. prev.next = null; 链表不为空,尾节点的前一个节点指向 null

  7. size--; modCount++; 修改链表大小和版本


进行删除操作的时候,删除的节点,都会把其前后指向节点都置为 null,帮助 GC 进行回收。


链表结构的节点新增、删除都只是把前后节点的指向修改下就好了,所以 LinkedList 适宜在新增和删除频繁的场景下使用,相应的也就不适宜在查询场景频繁的情况下使用,但是查找效率低而 ArrayList 的遍历效率会比 LinkedList 的遍历效率高一些。LinkedList 还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用。

用户头像

zarmnosaj

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

评论

发布
暂无评论
LinkedList 源码分析-删除_5 月月更_zarmnosaj_InfoQ写作社区