死磕Java之聊聊LinkedList源码(基于JDK1.8)

工作快一年了,近期打算研究一下JDK的源码,也就因此有了死磕java系列

  • LinkedList 是一个继承于AbstractSequentialList的双向链表,链表不需要capacity的设定,它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList 实现 List 接口,能对它进行队列操作,提供了相关的添加、删除、修改、遍历等功能。
  • LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  • LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  • LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输,包括网络传输与本地文件序列化。
  • LinkedList 是非同步的,如若要在并发情况下使用建议选取java.util.concurrent包下的集合类型。

LinkedList的UML图

LinkedList的成员变量及其含义

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * 指向头指针的节点.
     * transient关键字扫盲,在实现Serilizable接口后,
     * 将不需要序列化的属性前添加关键字transient,
     * 序列化对象的时候,这个属性就不会序列化到指定的目的地中
     */
    transient Node<E> first;

    /**
     * 指向尾节点。
     */
    transient Node<E> last;

    /**
     * 构造方法的空实现。
     */
    public LinkedList() {
    }

    /**
     * 按照集合迭代器返回的顺序构造包含指定集合元素的列表。
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * 链表的节点,私有实现。
     */
    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;
        }
    }
}

聊聊LinkedList的主要方法实现

我们主要看研究一下下面的几个方法,LinkedList其他方法都是通过调用这几个方法来实现功能,包括LinkedList的双端队列的方法也是。

 /**
  * 在链表头部插入元素.
  */
 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++;
 }

 /**
  * 在指定节点前面插入元素.
  */
 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++;
 }

 /**
  * 移除链表的头部元素.
  */
 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 将元素置为空,让jvm在gc时回收资源
     first = next;
     if (next == null)
         last = null;
     else
         next.prev = null;
     size--;
     modCount++;
     return element;
 }

 /**
  * 移除链表的尾部元素.
  */
 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;
     l.prev = null; // help GC
     last = prev;
     if (prev == null)
         first = null;
     else
         prev.next = null;
     size--;
     modCount++;
     return element;
 }

 /**
  * 移除某一个节点元素.
  */
 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) {
         first = next;
     } else {
         prev.next = next;
         x.prev = null;
     }

     if (next == null) {
         last = prev;
     } else {
         next.prev = prev;
         x.next = null;
     }

     x.item = null;
     size--;
     modCount++;
     return element;
 }

 /**
  * 通过indexOf方法来定位给定的元素,若LinkedList中存在元素则返回该元素对应的index,
  * 反之返回-1.
  */
 public boolean contains(Object o) {
     return indexOf(o) != -1;
 }

 /**
  * 在链表尾部追加元素.
  */
 public boolean add(E e) {
     linkLast(e);
     return true;
 }

 /**
  * 移除链表中的指定元素,分两种情况进行处理,当元素为空时与元素不为空时,时间复杂度为O(n).
  */
 public boolean remove(Object o) {
     if (o == null) {
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 unlink(x);
                 return true;
             }
         }
     } else {
         for (Node<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item)) {
                 unlink(x);
                 return true;
             }
         }
     }
     return false;
 }

 /**
  * 将一个集合的所有元素追加到链表的尾部.
  */
 public boolean addAll(Collection<? extends E> c) {
     return addAll(size, c);
 }

 /**
  * 将指定集合中的所有元素插入到该列表中,从指定位置开始。将当前在该位置的元素(如果有的话)
  * 和任何后续元素向右移动(增加它们的索引)。新元素将以指定集合的迭代器返回的顺序出现在列表中。
  */
 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) {
         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;
 }

 /**
  * 清空链表.
  */
 public void clear() {
     // Clearing all of the links between nodes is "unnecessary", but:
     // - helps a generational GC if the discarded nodes inhabit
     //   more than one generation
     // - is sure to free memory even if there is a reachable Iterator
     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;
     size = 0;
     modCount++;
 }


 // Positional Access Operations 以下是位置访问操作

 /**
  * 获取链表中对应索引的节点,时间复杂度为O(n)
  */
 public E get(int index) {
     // 检查index是否越界
     checkElementIndex(index);
     return node(index).item;
 }

 /**
  * 更新对应index的元素,并返回旧值,时间复杂度为O(n).
  */
 public E set(int index, E element) {
     checkElementIndex(index);
     Node<E> x = node(index);
     E oldVal = x.item;
     x.item = element;
     return oldVal;
 }

 /**
  * 在指定索引添加元素,时间复杂度为O(1).
  */
 public void add(int index, E element) {
     checkPositionIndex(index);

     if (index == size)
         linkLast(element);
     else
         linkBefore(element, node(index));
 }

 /**
  * 移除指定索引的元素,时间复杂度为O(1).
  */
 public E remove(int index) {
     checkElementIndex(index);
     return unlink(node(index));
 }
 
  /**
  * 查找指定index位置的元素.
  */
 Node<E> node(int index) {
     // assert isElementIndex(index);

     // 在查找对应index位置的元素的时候,java开发人员做了一层优化
     // 当index大于size的一半时从前向后查
     // 当index小于size的一半时从后向前查
     // 这样的话时间复杂度就变成了index/2
     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;
     }
 }

 // Search Operations

 /**
  * 查找指定元素的index,从前向后查
  */
 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;
 }

/**
  * 查找指定元素的index,从后向前查
  */
 public int lastIndexOf(Object o) {
     int index = size;
     if (o == null) {
         for (Node<E> x = last; x != null; x = x.prev) {
             index--;
             if (x.item == null)
                 return index;
         }
     } else {
         for (Node<E> x = last; x != null; x = x.prev) {
             index--;
             if (o.equals(x.item))
                 return index;
         }
     }
     return -1;
 }

动手实现LinkedList

由于代码过长,故不在此处一一贴出来,感兴趣的小伙伴可以到我的github查看[github]: https://github.com/haifeiWu/interview-collect/tree/master/src/main/java/com/haifeiwu/interview/structure/list

小结

  • 与ArrayList相比,LinkedList的长处在于当频繁的增加或者删除元素时效率会很高,但是LinkedList空间占用比较大,是一种典型的用空间换时间方案,在我们平时做代码优化时这也不失是种折中的方案。
  • LinkedList并发插入时节点覆盖的问题,就是当多个线程同时获取到相同的尾节点的时候,然后多个线程同时在此尾节点后面插入数据的时候会出现数据覆盖的问题,因此在并发量大的情况下应该使用java的加锁机制,或者采用java.util.concurrent包下的集合类型。

作 者:haifeiWu 原文链接:http://www.hchstudio.cn/article/2018/e5cd/ 版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一枝花算不算浪漫

一道笔试题来理顺Java中的值传递和引用传递

1081
来自专栏拭心的安卓进阶之路

Java 集合深入理解(11):LinkedList

今天心情鱼肚白,来学学 LinkedList 吧! 日常开发中,保存一组数据使用的最多的就是 ArrayList, 其次就是 LinkedList 了。 我们...

2897
来自专栏JavaEdge

"聊胜于无",浅析Java中的原子操作Java的指针Unsafe类i++不是线程安全的1 原子更新基本类型类2 原子更新数组3 AtomicReference(原子更新引用)4 原子更新字段Atomi

6486
来自专栏小灰灰

JDK容器学习之LinkedList:底层存储&读写逻辑

LinkedList的底层结构及读写逻辑 链表容器,通常适用于频繁的新增删除,遍历的方式访问数据元素的场景 LinkedList 底层数据结构为链表,非线程安...

2008
来自专栏猿人谷

顺序栈的实现和两栈共享空间

顺序栈的实现和两栈共享空间 一.顺序栈的实现        栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(t...

5338
来自专栏文武兼修ing——机器学习与IC设计

栈与栈的实现栈栈的基本操作栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作...

3225
来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

1162
来自专栏老马说编程

(39) 剖析LinkedList / 计算机程序的思维逻辑

上节我们介绍了ArrayList,ArrayList随机访问效率很高,但插入和删除性能比较低,我们提到了同样实现了List接口的LinkedList,它的特点与...

2108
来自专栏海说

14、Iterator跟ListIterator的区别

14、Iterator与ListIterator的区别       在使用List,Set的时候,为了实现对其数据的遍历,会经常使用到Iterator(跌代器)...

1900
来自专栏我的技术专栏

数据结构图文解析之:栈的简介及C++模板实现

1575

扫码关注云+社区

领取腾讯云代金券