List之LinkedList源码

LinkedList简介

LinkedList最大的特点是它的数据结构,它的底层是使用链表结构实现。链表是线性表的一种。而链表又分为单向链表和双向链表,
链表又有循环与非循环之分,在jdk1.6中就是使用了双向循环链表的结构,而在jdk1.7和jdk1.8中改成了双向链表,也就是取消循环了。

链表结构

既然LinkedList的底层是链表结构 那就来看看各种链表把

单向链表

单向链表中每个节点都有一个指向下一个节点的指针next,最后一个节点的指针next指向null

单向循环链表

单向循环链表是通过最后一个节点(tail)的指针指向第一个节点(head),形成一个闭环

双向链表(jdk1.6之后使用)

双向链表中每个节点都会有两个指针,pre指向前一个节点,next指向下一个节点,第一个节点的pre指向null,最后一个节点的next指向null,达到两个方向互通

双向循环链表(jdk1.6)

第一个节点中的pre指向最后一个节点,最后一个节点中的next指向第一个节点,形成一个闭环,且双向互通

LinkedList源码

先看看他的继承图

  • 继承AbstractSequentialList,该类对AbstractList进一步抽象,在迭代器的基础上实现增删改查,只能按次序访问,无法随机访问
  • 实现Deque,Deque是一个双向队列,既可以先进先出,又可先进后出
  • 实现Cloneable,实现Cloneable接口,就可以使用Object.clone()进行克隆了。
  • 实现Serializable,实现序列化接口,说明该类能够启用其序列化功能。序列化其实就是持久化,将class转变为字节流传输,然后保存,反序列化就是读取

    LinkedList的节点


  LinkedList 是node节点有三个属性;

  • item 存储该节点的元素element
  • next 存储该节点指向下个节点的指针next
  • prev 存储该节点指向上个节点的指针prev

LinkedList的构造方法

  LinkedList 有两种构造方法 一种是无参构造,另一种是LinkedList(Collection<? extends E>) 允许传入一个集合

LinkedList的add(六种)

1. 第一种add(E)方法默认往linkedList末尾添加新元素

过程就是:new一个新的节点 newNode,将 prev 指针指向 l ,e 作为新节点元素,next 指向 null,新添加的 newNode 变为该 LinkedList 的最后一个节点 last 若 l 节点不存在,则将新节点 newNode 作为第一个节点 first 若 l 节点存在,将 l 节点的 next 指针指向 新节点 newNode

2. 第二种add(int, E) 方法在指定位置添加新的元素

在调用linkBefore之前。node(index)会有一些处理

 public void add(int index, E element) {
        checkPositionIndex(index); //对指定元素位置进行合理性检查

        if (index == size)
            linkLast(element); //index == size 时,调用 linkLast 方法将元素添加到 linkedList 末尾
        else
            linkBefore(element, node(index)); //调用 linkBefore 方法
    }

    //元素位置越界检查异常处理
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //判断元素位置是否合理
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

再看看 linkBefore() 方法的实现:

   /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        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中没有下标的概念,但是它又能够在指定的位置插入元素,看完上面的代码,
很显然它是通过遍历找到指定位置的元素,这里作者巧妙的利用了二分法,让遍历的效率提高一倍

这个 linkBefore 方法实现原理与 linkLast 方法类似,将新节点 newNode 的 prev 指针指向指定位置的节点 succ 的前一个节点 pred ,而 succ 的 prev 指针变为指向新节点 newNode, 而新节点 newNode 的 next 指针则指向 succ ,pred 节点的 next 指针指向 newNode ; 这里文字有点绕, 简单点讲: 就是将新节点 newNode 插入 指定节点 succ 的位置,再将它们的指针重整。

3. 第三种addAll(Collection<? extends E> c)

方法内部调用的是addAll(int index, Collection<? extends E> c) 方法,这里只分析后一个addAll(int index, Collection<? extends E> c) 方法: 在指定位置插入一个集合,linkList有改动返回true,否则返回false

 public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //指定位置合理性检查

        Object[] a = c.toArray(); // 将指定集合转换成数组 a
        int numNew = a.length;    // 保存数组的长度
        if (numNew == 0)
            return false;         // 数组没有元素返回false

        Node<E> pred, succ;       // 定义 pred 和 succ 节点,将要在这两个节点中间插入新的节点  
        if (index == size) {
            succ = null; // 当指定位置 index 等于链表长度时,该插入位置为链表末端,不存在 succ 节点
            pred = last; // 则 pred 为最后一个节点 last  
        } else {
            succ = node(index); // 将指定位置index的节点赋值给 succ 
            pred = succ.prev;   // succ 的 prev 指针指向 pred 
        }

        for (Object o : a) { // for 循环遍历 a 数组
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null); // 将新节点 e 的 prev 指针指向 pred 节点,next 指针先指向 null ,得到新节点 newNode 
            if (pred == null) // 不存在前一个节点 pred 时
                first = newNode; // 则新节点 newNode 为链表头一个节点 first 
            else
                pred.next = newNode; //存在前一个节点 pred 时,pred 的 next 指针指向新节点 newNode
            pred = newNode; // 最后将新节点赋值为 pred 供下次循环使用,逐个将数组 a 中的元素插入到链表中
        }

        if (succ == null) { // 遍历完后,如果不存在 succ 节点
            last = pred;  // 则数组 a 中最后一个元素 pred 就是链表末端最后一个节点 last
        } else { // 如果存在 succ 节点
            pred.next = succ; // 则数组 a 中最后一个元素 pred 节点的 next 指针指向 succ 节点
            succ.prev = pred; // succ 的 prev 指针指向 数组 a 中最后一个元素 pred 节点
        }

        size += numNew; // 更新链表长度
        modCount++;
        return true; // 链表改动,返回 true
    }

小结: addAll 方法实现步骤:①传入指定的集合转换为数组;②遍历该数组逐个插入到链表中

4. 第四种addFirst(E) 和 addLast(E) 一个是头插,一个是尾插 分别调用了 linkFirst(E) 和 linkLast(E)

只要读懂前面的分析过程,这里就很容易了,当我们要往链表头部插入一个新的节点时,我们只要将新节点的 prev 指针指向 null ,next 指针指向原链表的第一个节点,如此,指定的新元素就成为链表的第一个节点 first ;在链表尾部插入新元素也是同理,只是指针的方向改为指向 last 节点就可以了

LinkedList的删除(七种)

1. 第一种  remove() remove() 方法删除链表的第一个元素
/**
     * Retrieves and removes the head (first element) of this list.
     * 检索并删除列表的头部第一个元素
     * @return the head of this list
     * @throws NoSuchElementException if this list is empty
     * @since 1.5
     */
    public E remove() {
        return removeFirst();
    }

    /**
     * Removes and returns the first element from this list.
     * 从列表中移除并返回第一个元素
     * @return the first element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException(); //first 节点为 null 时,说明该链表上没有元素,抛出异常
        return unlinkFirst(f); 
    }

    /**
     * first 节点不为空时,断开 first 节点指针
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item; // 将指定删除节点的元素 item 赋值给新定义的 element ,在方法结束时返回 element  
        final Node<E> next = f.next; // 将 f 节点的 next 指向的节点赋值给新定义的 next 节点
        f.item = null; // first 节点的 item 设置为 null
        f.next = null; // first 节点的 next 设置为 null
        first = next;  // first 节点的下一个节点 next 作为第一个节点 first
        if (next == null)
            last = null; // next 节点为 null 时,说明链表只有一个节点 first ,不存在节点 last ,所以 last 要设置为 null 
        else
            next.prev = null; // next 在这里作为删除 first 节点后的第一个节点,故 next 的 prev 指针应该指向 null 
        size--; // 链表长度减一
        modCount++;
        return element; // 最后返回指定删除的元素 element
    }
remove() 方法实现大致分为三步:

1. 将第一个节点保存起来,方法结束时返回
2. 断开第一个节点的所有指针
3. 将第一个节点的下一个节点 next 设置为第一个节点 first

2. 第二种 remove(int) remove(int) 方法删除指定位置的一个元素
 public E remove(int index) {
        checkElementIndex(index); //指定位置的合理性检查
        return unlink(node(index)); // node(index) 上面分析过,返回 index 位置的的节点,接着调用 unlink 方法 
    }

    /**
     * 删除指定不为空的元素
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item; // 将指定位置节点 x 的属性 item 保存为 element ,方法结束时返回 element 
        final Node<E> next = x.next; // 将 x 节点的 next 指针指向新定义的 next 节点
        final Node<E> prev = x.prev; // 将 x 节点的 prev 指针指向新定义的 prev 节点

        if (prev == null) {
            first = next; // 当 prev 指针指向 null 时,说明指定删除的节点位置为链表首节点 first ,将 next 节点设置为 first 节点
        } else {
            prev.next = next; // 否则将 next 节点设置为新定义的 prev 节点的 next 节点
            x.prev = null; // 断开指定删除节点的 prev 指针指向的节点
        }

        if (next == null) {
            last = prev; // 当 next 指针指向的节点为 null 时,prev 节点作为最后一个节点 last  
        } else {
            next.prev = prev; // 否则将 prev 节点设置为新定义的 next 节点的 prev 节点
            x.next = null; // 断开指定删除节点的 next 指针指向的节点
        }

        x.item = null; // 将指定删除的节点的 item 属性设置为 null,让 GC 清理
        size--; // 链表长度减一
        modCount++;
        return element; // 最后返回 element 元素
    }
remove(int index) 方法大致分为以下五步:

1. node(index) 获取到指定位置的节点
2. 调用 unlink 方法,将指定位置节点传入
3. 将指定位置节点的 item 属性保存为 element ,方法调用完毕返回该元素
4. 断开指定位置节点的所有指针
5. 将指定位置节点的左右节点连接

3. remove(Object o) LinkedList remove(o) 方法支持传入一个Object类型,如果链表中包含指定元素,则删除,返回 true;如果不包含则返回 false
 public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) { // 传入的参数为 null 时,从 first 节点开始 for 循环遍历整个链表
                if (x.item == null) { // 当节点的 item 属性为 null 时
                    unlink(x); // 删除该节点(unlink方法上面分析过)
                    return true; // 返回 true
                }
            }
        } else { // 要删除的元素不为 null 的情况
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) { // equals 方法判断元素是否同一元素
                    unlink(x); // 同一个元素,则删除该元素
                    return true; // 返回 true
                }
            }
        }
        return false; // 如果指定删除的元素在链表中不存在时,返回false
    }

这里需要注意的是,在LinkedList 中可以存在 null 值的,而这个 null 值是存储在节点的 item 属性中,节点还有 prev 和 next 指针分别指向前一个元素和后一个元素,prev 和 next 不是空的,所以这也是LinkedList 中可存放 null 值的合理性因素。

4. 其余几种removeFirst() 和 removeLast() 首尾删除与首尾插入对应

removeFirstOccurrence(Object o) 和 removeLastOccurrence(Object o)

这两个方法与 remove(Object o) 方法相似,只不过remove(Object o) 默认从链表头部开始遍历删除第一次出现的指定元素,removeFirstOccurrence(Object o) 就是调用了remove(Object o) 方法;而removeLastOccurrence(Object o) 实现了从链表尾部开始遍历删除指定元素,看到源码,我们可以知道它的实现方式与 remove(Object o) 相似,不同的是遍历的方向相反而已。


总的来说:
LinkedList 支持链表首末添加/删除元素操作
LinkedList 支持指定位置插入/删除元素
LinkedList 允许删除指定元素
LinkedList 支持存放 null 值

LinkedList的修改

set(int index, E element) 将链表中指定位置 index 的元素替换成指定元素 element
LinkedList 的数据都是存储在每个节点的 item 属性当中,我们修改数据时,只要修改对应位置节点的 item 属性就行了。

LinkedList的查

get(int) 方法允许获取链表中指定位置的元素。

get(int) 方法的实现调用了 node(index) 方法。方法内部主要是根据指针 for 循环遍历找到对应位置的节点,显然这种查找方式效率很慢,任何事情都不能做的完美,在这种数据结构下,已经决定了它自身的查找效率是个短板。作者希望能够尽可能的提高它的查询效率,在遍历之前使用了二分法,查找效率提高了一倍。

总结:

LinkedList 在头部或尾部添加元素,复杂度为 O(1)
LinkedList 随机添加元素,涉及到指针的指向操作(参考本文3.4.2 node(index) 方法分析),复杂度为 O(n)
LinkedList 删除元素,在头部尾部删除元素,复杂度为 O(1)
LinkedList 指定位置删除元素,需要先查找到该位置的元素,涉及到指针的指向操作,复杂度为 O(n)
LinkedList 改操作(set方法),需要先查找到该位置的元素,涉及到指针的指向操作,复杂度为 O(n)
LinkedList 查操作(get(int)方法),需要先查找到该位置的元素,涉及到指针的指向操作,复杂度为 O(n)
linkedList 所有操作都不是原子操作,线程不安全。