2019-12-04 Java-LinkedList源码解读

作者: LH_0811 | 来源:发表于2019-12-04 11:19 被阅读0次

1、链表数据结构

链表分为单向链表和双向链表，他们的区别在于，单向链表只能单向寻址，而双向链表可以双向寻址。
链表中的每个单位是一个node（节点）。
双向链表：每个节点都保存 data(数据)、prev(上一个节点)、next(下一个节点)
单向链表：每个节点都保存 data(数据)、next(下一个节点)

链表数据结构的特点是：

每个节点的存储地址是不连续的通过指针寻址找到相邻的节点。
方便节点的增删
不方便查询，需要通过指针寻址遍历节点

2、LinkedList 与ArrayList的区别

LinkedList是基于链表的实现，ArrayList是基于数组实现的。
LinkedList是基于链表实现的所以不需要考虑扩容的问题。
LinkedList节点的增加删除效率要高于ArrayList。
LinkedList的查询效率要低于ArrayList。

为什么链表方便做节点的增删不方便查询？

  这是一个双向列表 : A <---> B <---> C <---> D
  每个节点都存放了 其prev(上一个节点) 和 next(下一个节点) 的指针 以便确定 双向链表的顺序。

  默认情况下,如果要添加一个节点 E,则是在链表的尾部进行添加

  D元素的next 指向 E节点 ，E节点的prev指向 D
  于是整个链表变成了:  A <---> B <---> C <---> D <---> E

  如果此时要删除 C 节点
  只需要将 B节点(C节点的prev)的next 指向 D(C 节点的next)
  同时 D节点(C节点的next)的prev 指向 B(C节点的prev)
  并把 C节点的 prev 和 next 都置为空
  于是整个链表变成了: A <---> B <---> D <---> E       C(已经不会作为任何一个节点的prod 或者 next 没有引用的节点 会等待GC的回收)

从上面的例子可以看出。

链表在删除的时候只需要修改节点之前的引用关系就行了。而数组则是需要移动被删除元素后面的所有元素的下标。增加的时候也是同理。

但是查询的时候链表只能通过寻址来找对应的index ，而数组则是可以通过index来确定元素所在的位置。

3、LinkedList 成员变量

LinkedList基于链表实现，其中的节点抽象成了静态内部类Node

 // 内部静态类 链表数据节点
    private static class Node<E> {
        // 数据元素
        E item;
        // 下一个节点
        LinkedList.Node<E> next;
        // 上一个节点
        LinkedList.Node<E> prev;

        Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

LinkedList中有几个重要的成员变量

    // 实际存储的节点数量
    transient int size = 0;

    // 头节点
    transient Node<E> first;

    // 尾节点
    transient Node<E> last;

4、 LinkedList 的基本实现（详细注解）

package com.lhit.collection;


import java.util.Collection;

public class LinkedList<E> {


///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////以下是LinkedList 基于双向链表数据结构实现的基础描述////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
/*
  这是一个双向列表 : A <-> B <-> C <-> D
  每个节点都存放了 其prev(上一个节点) 和 next(下一个节点) 的指针 以便确定 双向链表的顺序。

  默认情况下,如果要添加一个节点 E,则是在链表的尾部进行添加

  D元素的next 指向 E节点 ，E节点的prev指向 D
  于是整个链表变成了:  A <-> B <-> C <-> D <-> E

  如果此时要删除 C 节点
  只需要将 B节点(C节点的prev)的next 指向 D(C 节点的next)
  同时 D节点(C节点的next)的prev 指向 B(C节点的prev)
  并把 C节点的 prev 和 next 都置为空
  于是整个链表变成了: A <-> B <-> D <-> E    C(已经不会作为任何一个节点的prod 或者 next 没有引用的节点 会等待GC的回收)
*/

///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////以下是LinkedList中主要的成员变量和内部类//////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////

    // 实际存储的节点数量
    transient int size = 0;

    // 头节点
    transient Node<E> first;

    // 尾节点
    transient Node<E> last;


    // 内部静态类 链表数据节点
    private static class Node<E> {
        // 数据元素
        E item;
        // 下一个节点
        LinkedList.Node<E> next;
        // 上一个节点
        LinkedList.Node<E> prev;

        Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

///////////////////////////////////////////////////////////////////////////////////////////
    ///////////LinkedList 1. 构造方法 包含 构造方法调用到的add(Collection c)方法////
//////////////////////////////////////////////////////////////////////////////////////////

    // 1. 构建一个空的List
    public LinkedList() {
    }

    // 1. 构建一个包含集合指定元素的list，并且顺序也是按照集合迭代器所返回的顺序
    public LinkedList(Collection<? extends E> c) {
        this();

        // 1.1 向list中添加集合中的所有元素
        addAll(c);
    }


    // 1.1 向list中添加集合中的所有元素
    // 追加指定集合中的全部元素到list的尾部，顺序与集合的迭代器返回的顺序一致
    // 如果在操作进行期间修改了指定的集合，则此操作的行为是不明确的，就是不知道会发生啥事情。(注意，如果指定的集合是当前列表，并且它不是空的，则会发生这种情况。)
    public boolean addAll(Collection<? extends E> c) {
        // 1.1.1 从指定index位置开始 向list中插入集合中的全部元素
        return addAll(size, c);
    }

    // 1.1.1 插入指定集合中的全部元素到当前的list中，从指定的index坐标开始。
    // 将当前位于该位置的元素(如果有的话)和随后的元素向右移动(增加它们的索引)
    // 新元素将按指定集合的迭代器返回它们的顺序 插入到列表中。
    public boolean addAll(int index, Collection<? extends E> c) {
        // 1.1.1.1 确定 index，检查坐标是否越界
        checkPositionIndex(index);

        // 1.1.1.2 把集合转成数组处理
        Object[] a = c.toArray();
        // 1.1.1.3 获取到集合的元素个数
        int numNew = a.length;
        // 1.1.1.4 如果是一个空的集合 直接返回false 不做后续操作
        if (numNew == 0)
            return false;

        // 1.1.1.5 确定 要插入的新节点 的前一个节点
        // 初始化pred-上一个节点 和 succ 需要要操作的节点
        LinkedList.Node<E> pred, succ;

        // 1.1.1.6 找到新出入元素的上一个节点 并 找到 需要操作的原来在index位置的succ节点
        // 判断要插入的坐标 是不是与当前list的实际长度相同
        if (index == size) {
            // 1.1.1.6.1 如果相同的话
            // 不需要操作节点
            // 新插入节点的上一个节点就是 原来list的 last(最后一个)节点
            succ = null;
            pred = last;
        } else {
            // 1.1.1.6.2 如果不同 就是需要操作原来在index坐标位置的节点
            // 找到当前 list 指定坐标的节点
            succ = node(index);
            // 原来在index位置的节点的 前一个节点 就是 新节点的前一个节点
            pred = succ.prev;
        }

        // 1.1.1.7 遍历数组元素 从index 位置 插入到到list中
        for (Object o : a) {
            // 1.1.1.7.1 把当前数组元素包装成 list的node节点
            @SuppressWarnings("unchecked") E e = (E) o;
            LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, null);
            // 1.1.1.7.2 确定新节点的上一个节点
            if (pred == null)
                // 1.1.1.7.2.1 如果上一步没有找到 新元素的前一个节点 那就说明原来list是一个空的list 所以 新的节点就是list的头
                first = newNode;
            else
                // 1.1.1.7.2.1 如果找到了新元素的前一个节点 那前一个节点的next（下一个节点）就是要指向新的节点
                pred.next = newNode;
            // 1.1.1.7.2 最后新节点当做 下一个元素节点的前一个节点 保证节点的顺序与数组的迭代器返回的顺序是一样的。
            pred = newNode;
        }

        // 1.1.1.8 确定 要插入的新节点 的下一个节点
        if (succ == null) {
            // 1.1.1.8.1 如果 原来list中在index位置的节点 succ 为空 说明 index后面没有要操作的元素 所以 最后一个新节点(pred) 就是 list的last节点 不用找下一个节点了
            last = pred;
        } else {
            // 1.1.1.8.2 如果 原来list中在index位置的节点 succ 不为空 那么 最后一个新的节点（pred） 的下一个节点就是 之前的succ节点 并且succ节点的前一个节点就是 最后一个新的节点(pred)
            pred.next = succ;
            succ.prev = pred;
        }

        // 1.1.1.9 list实际存储的node的数量加上 集合的元素个数
        size += numNew;
        return true;
    }

    // 1.1.1.1 / 3.1 确定 index，检查坐标是否越界
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    // 1.1.1.6.2.1 找到当前 list 指定坐标的节点
    LinkedList.Node<E> node(int index) {
        // assert isElementIndex(index);
        // 这里查询过程中做了一个优化
        // 1.先判断index 是距离first 节点近 还是距离 last节点近
        // 2.如果距离first节点近 就从first节点 向后 找next节点 当 i == (index-1) 时x.next 就是index坐标对应的节点 于是找到目标节点
        // 3.如果距离last节点近 就从last节点 向前找prev节点  当 i == (index +1) 是x.prev 就是index坐标对应的节点 于是找到目标节点

        // 这样做的处是 可以减少链表查询的路径长度 。假设我们链表的总长度为20（index是 0-19）.我们找 index=18的元素
        // index > (size >> 1) 所以距离 last节点近
        // 这时 只需要找到 last 的index是19 > 18 找到了x.prev 就是 目标节点了 下次循环条件不成立就跳出 返回了目标结果
        // 这种情况下 我们节省了 大部分的寻址次数。
        if (index < (size >> 1)) {
            LinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            LinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    // 返回LinkedList中实际存储节点的数量
    public int size() {
        return size;
    }

///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////LinkedList add方法//////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////

    // 2. 添加单个节点
    // 在list的尾部 追加新节点
    public boolean add(E e) {
        // 2.1.1 追加新节点到链表的尾部
        linkLast(e);
        return true;
    }

    // 3. 添加单个节点到指定index
    // 添加节点到list的指定位置，将当前位于该位置的元素(如果有的话)和随后的任何元素向右移动(将一个元素添加到它们的索引中)。
    public void add(int index, E element) {
        // 3.1 检查数据越界
        checkPositionIndex(index);

        if (index == size)
            // 3.2 如果 index == size 其实就是在list的后面追加新的节点，就相当于是add(E e)方法
            linkLast(element);
        else
            // 3.3 在指定节点之前 添加新的元素节点
            linkBefore(element, node(index)/*这里首先搜索到指定index的节点*/);
    }


    // 2.1/3.2 追加新节点到链表的尾部
    void linkLast(E e) {
        // 2.1.1 找到 list的last节点
        final LinkedList.Node<E> l = last;
        // 2.1.2 新节点的prev节点 就是last节点 没有 next节点
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
        // 2.1.3 更新last节点
        last = newNode;
        if (l == null)
            // 如果last节点为null 那其实就是空的list 所以 first节点也是新节点
            first = newNode;
        else
            // 如果last节点不为null 那原来last节点额next就是新节点
            l.next = newNode;
        // 2.1.4 最后list的容量+1
        size++;
    }

    // 3.3 在非空节点succ之前插入元素e。
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // 这里的succ节点 就是原list中 index坐标所对应的节点

        // 3.3.1 找到succ节点的前一个节点
        final Node<E> pred = succ.prev;
        // 3.3.2 创建新的节点
        // 新节点的pred 就是 succ节点的prev
        // 新节点next节点 就是succ节点
        final Node<E> newNode = new Node<>(pred, e, succ);

        // 3.3.3 更新节点关系
        // succ节点的前一个节点就是新节点
        succ.prev = newNode;
        if (pred == null)
            // succ的节点的前一个节点如果是null 其实就是插入到整个list的最前面 所以 first节点就是新节点
            first = newNode;
        else
            // succ的节点的前一个节点如果不是null 就需要更新pred节点的next 为新节点
            pred.next = newNode;
        // 3.3.4 最后size +1
        size++;
    }


///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////LinkedList contains  indexof 方法 判断list中是否包含某个元素////////////
//////////////////////////////////////////////////////////////////////////////////////////

    // 4. 判断list是否报案某个元素
    public boolean contains(Object o) {
        // 4.1 获取某个元素对应节点的坐标
        return indexOf(o) != -1;
    }


    // 4.1 从第0个节点开始查找 获取某个元素对应节点的坐标 所以只能找到第一个匹配的元素的index
    public int indexOf(Object o) {
        // 默认从0开始查找节点
        int index = 0;
        // 如果o是null 就开始从第0个节点找元素为null的节点 如果找到第一个为null的节点 就返回index
        if (o == null) {
            for (LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            // 如果o不是null 就开始从第0个节点 与对象o equals 的元素 找到第一个equals节点后返回对应的index
            for (LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    // 4.2  与indexOf对应的 lastIndexOf方法 则是从最后一个节点开始查找 所以只能找到最后一个匹配的元素的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 unlink 方法 在list中移除节点////////////
//////////////////////////////////////////////////////////////////////////////////////////

    // 5. 断开非空节点x的链接
    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节点
            first = next;
        } else {
            // 如果上一个节点不为null 那上一个节点的next 就是 移除节点的next
            prev.next = next;
            // 断开要移除节点对上一个节点的引用
            x.prev = null;
        }


        if (next == null) {
            // 如果next节点为空 那prev节点 就是last节点
            last = prev;
        } else {
            // 如果next节点不为空 那next节点的prev就是 要移除节点的prev
            next.prev = prev;
            // 断开要移除节点 与next节点的引用
            x.next = null;
        }

        // 存储元素置空
        x.item = null;
        // size -1
        size--;
        // 返回被移除的元素数据
        return element;
    }

    // 6. 断开头元素
    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--;
        return element;
    }

    // 7. 断开尾元素
    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--;
        return element;
    }


///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////LinkedList get set remove 方法////////////
//////////////////////////////////////////////////////////////////////////////////////////


    // 8. 获取指定位置的元素
    public E get(int index) {
        // 8.1 检查越界问题
        checkElementIndex(index);
        // 8.2 找到指定元素的节点，返回存储元素
        return node(index).item;
    }

    // 9. 设置指定位置的节点的存储元素
    public E set(int index, E element) {
        // 9.1 检查越界
        checkElementIndex(index);
        // 9.2 获取到指定位置的节点
        Node<E> x = node(index);
        // 9.3 获取到老的元素数据
        E oldVal = x.item;
        // 9.4 设置节点元素为新元素
        x.item = element;
        // 9.5 返回老元素数据
        return oldVal;
    }


    // 10.移除指定位置的节点
    public E remove(int index) {
        // 10.1 检查越界
        checkElementIndex(index);
        // 10.2 断开指定位置的节点链接
        return unlink(node(index));
    }

    // 10.1/9.1/8.1 检查越界
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }


///////////////////////////////////////////////////////////////////////////////////////////
    //////////////////LinkedList clear 方法////////////
//////////////////////////////////////////////////////////////////////////////////////////


    public void clear() {
        // 遍历node节点
        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
        size = 0;
    }


}

5、LinkedList如何优化查询的？

 LinkedList.Node<E> node(int index) {
        // assert isElementIndex(index);
        // 这里查询过程中做了一个优化
        // 1.先判断index 是距离first 节点近 还是距离 last节点近
        // 2.如果距离first节点近 就从first节点 向后 找next节点 当 i == (index-1) 时x.next 就是index坐标对应的节点 于是找到目标节点
        // 3.如果距离last节点近 就从last节点 向前找prev节点  当 i == (index +1) 是x.prev 就是index坐标对应的节点 于是找到目标节点

        // 这样做的处是 可以减少链表查询的路径长度 。假设我们链表的总长度为20（index是 0-19）.我们找 index=18的元素
        // index > (size >> 1) 所以距离 last节点近
        // 这时 只需要找到 last 的index是19 > 18 找到了x.prev 就是 目标节点了 下次循环条件不成立就跳出 返回了目标结果
        // 这种情况下 我们节省了 大部分的寻址次数。
        
        if (index < (size >> 1)) {
            MyLinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            MyLinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

2019-12-04 Java-LinkedList源码解读

1、链表数据结构

2、LinkedList 与ArrayList的区别

3、LinkedList 成员变量

4、 LinkedList 的基本实现（详细注解）

5、LinkedList如何优化查询的？

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读