加入收藏 | 设为首页 | 会员中心 | 我要投稿 核心网 (https://www.hxwgxz.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 电商 > 正文

【数据结构】2.java源码关于LinkedList

发布时间:2021-04-01 13:10:17 所属栏目:电商 来源:网络整理
导读:关于LinkedList的源码关注点 1.从底层数据结构,扩容策略 2.LinkedList的增删改查 3.特殊处理重点关注 4.遍历的速度,随机访问和iterator访问效率对比 ? 1.从底层数据结构,扩容策略 构造函数不做任何操作,只要再add的时候进行数据初始化操作,以操作推动逻
副标题[/!--empirenews.page--]

关于LinkedList的源码关注点


1.从底层数据结构,扩容策略
2.LinkedList的增删改查
3.特殊处理重点关注
4.遍历的速度,随机访问和iterator访问效率对比

?

1.从底层数据结构,扩容策略

构造函数不做任何操作,只要再add的时候进行数据初始化操作,以操作推动逻辑,而且linkedlist是一个双向链表,所以可以向前向后双向遍历
由于构造函数并没有任何操作,其实这里我们可以先看新增操作,并且因为用的是链表所以无法随机访问,这里随机读取就会比较慢

?

【数据结构】2.java源码关于LinkedList

?


底层结构就是size,首节点,尾节点,还有就是一个List都有的共性就是modCount,这值用来记录这个list被修改了多少次

?

?2.LinkedList的增删改查

?2.1 add操作,linklast

?

Add操作的实质就是进行linklast操作

linklast的操作就是再最后吧节点添加到尾部,并修正size大小

?

【数据结构】2.java源码关于LinkedList

?

?

    public boolean add(E ele) {
        linkLast(ele);
        return true;
    }

?

我们看看如果是在指定的位置插入元素的操作
首先要确认index再指定范围内
这里有个小优化,如果是在末尾进行添加的话,我们直接调用linklast就可以了
如果不是最后一个,那么首先要获取指定位置的node节点,我们遍历指定位置的时候
可以确定index的位置如果过半了,那么就从后往前,如果没有过半,那么就从前往后
1.直接再index创建一个节点,然后前后合并一下
2.吧原来的index位置的节点断开,吧这个节点的pre指向新节点
3.判断前置节点是否到头了,为空
4.把前置节点的next指向新节点

?先看看node定位操作

?

【数据结构】2.java源码关于LinkedList

?

?然后我们看看linkbefore,前置插入

?

public 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++;
    }

那么我们需要插入到指定的位置的方法就可以很简单的实现了
Linkbefore(e,node(index))即可

?

【数据结构】2.java源码关于LinkedList

2.2 删除

?

查看源码,比较remove(),remove(object),remove(index)等等操作,归根到底还是一个unlink操作
我们需要对指定的节点进行unlink操作
就2步操作
1.当前节点的前一个节点指向当前节点的下一个节点,说白了node.pre.next = node.next;
2.当前节点的下一个节点的前置节点指向当前节点的上一个节点:node.next.pre = node.pre;
其他细节部分就是首尾节点的处理

?

?

public E unlink(Node<E> node) {
        // assert x != null;
        //这里需要操作的就是三个节点,前置节点,当前节点,后置节点
        final E element = node.item;
        final Node<E> prev = node.prev;
        final Node<E> next = node.next;

        //当前节点的前一个节点指向当前节点的下一个节点,说白了node.pre.next = node.next;
        if (prev == null) {
            //避免首节点操作
            first = next;
        } else {
            prev.next = next;
            node.prev = null; //断开原始连接
        }

        //当前节点的下一个节点的前置节点指向当前节点的上一个节点:node.next.pre = node.pre;
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

        //清除当前节点
        node.item = null;
        size--;
        modCount++;
        return element;
    }

其余操作基本就是调用unlink方法进行操作

【数据结构】2.java源码关于LinkedList

?

?修改set和获取get就不多说了,就注意一点就是set操作的时候,会返回旧值,并且这两个操作不会修改modCount值,也就是不会产生链表变动

?

?3.特殊处理重点关注,iterator,序列化

?

?

对于iterator这个就不多说了,其实还是调用上面的那些方法,遍历也就是next和pre和循环遍历没差别
但是注意一点就是通过迭代器进行remove和add是可以的,但是注意一点,如果使用迭代器进行remove或者add操作的通过,还使用了一般的remove和add那么就会使迭代器失效


序列化这里我们先只做一个了解,后续开章节专门学习一下java的序列化:

(编辑:核心网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

热点阅读