美文网首页
LinkedList源码阅读

LinkedList源码阅读

作者: kindol | 来源:发表于2018-05-08 21:00 被阅读0次

    双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项前后项即可,插入数据较快;其实主要是数据结构的东西

    三个属性:头尾节点、size

    L1.jpg

    Node节点(内部静态私有类)

    L2.jpg

    构造方法:

    无参:构造一个空链表。

    有参构造函数:

    public LinkedList(Collection<? extends E> c) {
            this();//调用无参构造方法构造一个空的链表
            addAll(c);
        }
    

    先产生一个空链表,再调用addAll(Collection<? extends E> c)方法,再有addAll调用addAll(int index, Collection<? extends E> c),传入的index为size,在构造函数这也就是从0开始覆盖,

    add过程:先对index的两种情况进行了处理:一种是index==size(在尾部插入),另一种是index,遍历传入的c(将c转换为Object),创建newNode,依次循环即可

    支持放入null元素,但不是说节点为null,而是节点中的item为null

    add方法:

    直接调用linkLast,在尾部添加节点

    L3.jpg

    linkLast的步骤:

    获得last节点为l,创建新对象(设置传入的对象的prev为l节点,next为null),再设置last为新创建的对象,最后判断l是否为空,如果是,first为新创立的节点,否则,l.next为新创立的对象,再修改size

    此时堆栈的形式为:

    L4.jpg

    最后,双向链表:

    L5.jpg

    remove方法:

    嗯,记得先覆盖equals方法

    L6.jpg

    util集合支持往里面放入null值元素(不是null)。当然了,代码主要功能是调用了unlink方法

    unlink步骤为:先判断前后节点是否为空并设置,最后另x.item = null,更新size等,返回

    复杂度:

    LinkedList底层链表删除元素只是简单的修改了一下引用地址,时间复杂度为O(1)。

    参考:https://zhuanlan.zhihu.com/p/28101975
    

    相关文章

      网友评论

          本文标题:LinkedList源码阅读

          本文链接:https://www.haomeiwen.com/subject/uktgrftx.html