金点网络-全网资源,一网打尽
  • 网站首页
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
登录/注册
  • 专享大神特权
立即开通开通会员抄底价

Java 基础概念·Java List

作者 : jamin 本文共6261个字,预计阅读时间需要16分钟 发布时间: 2020-10-18 共1402人阅读

Java List

本文为个人学习摘要笔记。
原文地址:List 中的 ArrayList 和 LinkedList 源码分析

List 是单列集合 Collection 下的一个实现类,List 的实现接口又有几个,一个是 ArrayList,还有一个是 LinkedList,还有 Vector,这次研究下这三个类的源码。

ArrayList

ArrayList 是我们在开发中最常用的数据存储容器,它的底层是通过数组来实现的。我们在集合里面可以存储任何类型的数据,而且他是一个顺序容器,存放的数据顺序就是和我们放入的顺序是一致的,而且他还允许我们放入 null 元素,我们可以画个图理解一下。

ArrayList

上图数组里面存放的元素的引用,再分析下源码。

源码分析

/**
 * Default initial capacity.
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 如果是数组刚初始化就会用这个空数组替代它,这是自定义容量为0的时候。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 未自定义容量,数组刚初始化就会用这个空数组替代它
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 这个elementDate就是底层使用的数组
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * 实际ArrayList集合大小 也就是实际元素的个数
 */
private int size;

DEFAULT_CAPACITY 是默认的初始容量,容量是 10,EMPTY_ELEMENTDATA 这代表的是一个空的初始化数组(自定义容量为 0)。 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 区别上边,他是未自定义容量的空数组。

EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 区别在哪?通过他的构造函数了解下。

构造

/**
 * Constructs an empty list with an initial capacity of ten.
 * 这个地方就会构造一个初始容量为10的数组
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

无参构造器构造一个初始容量为 10 的数组,但是构造函数只是给 elementDate 赋值了一个空数组,其实就是在我们添加元素的时候,容量自动扩充为 10。

总结:如果是使用无参构造时,是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 给了 elementDate ,当 initialCapacity 为 0 的时候,就把 EMPTY_ELEMENTDATA 赋值给了 elementDate,如果 initialCapacity 大于 0,就会初始化一个 initialCapacity 长度的数组给 elementDate。

迭代器

使用过 ArrayList 的人一般都知道,在执行 for 循环的时候一般情况是不会去执行 remove 的操作的,因为 remove 的操作会改变这个集合的大小, 所以会有可能出现数组角标越界异常。

具体详情可以参考:18 Java fail fast

这里再次分析下源码:

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

在这个方法内部 next 是最主要的一个方法,他首先去判断了 expectedModCount 和 modCount 是否一样,然后去看 cursor,是不是超过集合的大小和数组的长度,然后去把 cursor 的值给 lastRet,返回的是下标 lastRet 的元素,最后 cursor 加 1,这样就是说每调用一次 next 方法,cursor 和 lastRet 都会加 1。

当我们在调用 remove 方法的时候,他会去判断 lastRet 是否小于 0,然后去判断 expectedModCount 和 modCount 是否一样,然后他去调用 ArrayList.remove() 方法去删除下标是 lastRet 的元素,然后把 lastRet 赋值给 cursor,然后初始化 lastRet = -1,最后把 modCount 重新赋值给 expectedModCount。

LinkedList

LinkedList 的底层是一个双向链表的结构,它可以进行高效的插入和移除的操作。

LinkedList 节点

LinkedList 是由很多个这样的节点组成的:

  • prev 是存储的上一个节点的引用
  • element 是存储的具体的内容
  • next 是存储的下一个节点的引用

整体结构:

LinkedList 整体结构

图解中可以看出 LinkedList 有好多的 Node,并且还有 first 和 last 这两个变量保存头部和尾部节点的信息。

需要注意:LinkedList 不是一个循环的双向链表,因为他前后都是 null。

源码分析

变量

/**
* 集合元素的数量
*/
transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 * 指向第一个节点的指针
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 * 指向最后一个节点的指针
 */
transient Node<E> last;

构造方法


/**
 * Constructs an empty list.
 * 无参构造
 */
public LinkedList() {
}

/**
 * 将集合C中的所有的元素都插入到链表中
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Node 节点

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

addAll


/**
 * 将集合插入到链表的尾部
 */
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;
    // 如果新增元素为0,则不添加,并且返回false
    if (numNew == 0)
        return false;

    // 定义index节点的前置节点,后置节点
    Node<E> pred, succ;

    // 判断是不是链表的尾部,如果是,那么就在链表尾部追加数据
    // 尾部的后置节点一定是null,前置节点是队尾
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 如果不是在链表的末尾而是在中间位置的话,
        // 取出index节点,作为后继节点
        succ = node(index);
        // index节点的前节点,作为前驱的节点
        pred = succ.prev;
    }

    // 链表批量的增加,去循环遍历原数组,依次去插入节点的操作
    for (Object o : a) {
        @SuppressWarnings("unchecked")
        // 类型转换
        E e = (E) o;
        // 前置节点为pred,后置节点为null,当前节点值为e的节点newNode
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果前置节点为空, 则newNode为头节点,否则为pred的next节点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        // 将新节点标记为前置节点,之后在此节点后添加新节点
        pred = newNode;
    }
    // 循环结束后,如果后置节点是null,说明此时是在队尾追加的
    if (succ == null) {
        last = pred;
    } else {
        // 否则是在队中插入的节点 ,更新前置节点 后置节点
        pred.next = succ;
        succ.prev = pred;
    }
    // 修改数量size
    size += numNew;
    // 修改modCount
    modCount++;
    return true;
}

addFist

将 e 元素添加到链表并且设置其为头节点 Fist:

public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 * 将e元素弄成链接列表的第一个元素
 */
private void linkFirst(E e) {
    final Node<E> f = first;

    // 链表开头前驱为空,值为e,后继为f
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;

    // 若f为空,则表明列表中还没有元素,last也应该指向newNode
    if (f == null)
        last = newNode;
    else
        // 否则,前first的前驱指向newNode
        f.prev = newNode;
    size++;
    modCount++;
}

addLast

将元素添加到链表,并且设置为尾部的节点 next:

public void addLast(E e) {
    linkLast(e);
}

/**
 * Links e as last element.
 * 将e元素弄成链接列表的last元素
 */
void linkLast(E e) {
    final Node<E> l = last;

    // 前驱为前last,值为e,后继为null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;

    // 最后一个节点为空,说明列表中无元素
    if (l == null)
        // first同样指向此节点
        first = newNode;
    else
        // 否则,前last的后继指向当前节点
        l.next = newNode;
    size++;
    modCount++;
}

需要注意:ArrayList 和 LinkedList 都是线程不安全的,因为,他内部的方法都没有进行方法同步,或者说是加锁。

Vector

Vector 并不常用,他是一个可实现自动增长的数组,同时也是一个线程安全的数组。

// 它底层也是个数组 但是他的修饰符确实protected的而ArrayList是一个transient的。
protected Object[] elementData;

// 它的方法都是通过synchronized关键字来修饰的
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

synchronized 关键字表面的意思是:当有两个并发线程同时访问一个对象代码块的时候,在同一个时刻,只能有一个线程得到执行,而另外的一个线程受到阻塞,必须等待当前线程的代码执行完这个代码块之后才能执行该代码。

也就是说在执行 synchronized 代码块的时候会锁定当前的对象,只有执行完改代码块之后才能释放锁,下一个线程开始锁定对象执行。

总结

List 实现类:

  • ArrayList–>数组结构–>线程不安全,效率高–>查询快,增删慢–>容量不够扩容,当前容量长度*1.5+1;默认长度为 10,第一次扩充后的长度为 16,第二次扩充后的长度为 25,第三次扩从后的长度为 38.5,不取用四舍五入,为 38; 但是要注意,JDk1.7 是 1.5+1;而 JDK8 是 1.5,所以视情况而定
  • LinkedList–>双向链表结构–>线程不安全,效率高–>查询慢,增删快–>链表直接在头部尾部新增都可以,所以没有倍数;
  • Vector–>数组结构–>线程安全,效率低–>查询快,增删慢–>扩容长度是:当前容量长度*2;
Atom ExecutorService ForkJoin Java ReentrantLock synchronized ThreadLocal volatile 后台
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络-全网资源,一网打尽 » Java 基础概念·Java List

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用
jamin

jamin 大神

下一篇
网络协议-组播介绍

相关推荐

放置三国H5页游(魔兽H5)【Linux手工端】+服务器搭建视频

放置三国H5页游(魔兽H5)【Linux手工端】+服务器搭建视频

Java 基础概念·Java BiFunction 和 BinaryOperator

Java 基础概念·Java BiFunction 和 BinaryOperator

网页游戏盛世遮天单机版服务端GM刷元宝金币装备属性xp/win7/8/10

网页游戏盛世遮天单机版服务端GM刷元宝金币装备属性xp/win7/8/10

梦幻西游【免虚拟机一键端】笑傲仿官方

梦幻西游【免虚拟机一键端】笑傲仿官方

完美国际镜像端+架设教程+修改工具

完美国际镜像端+架设教程+修改工具

标签云
Android Atom ExecutorService ForkJoin GM GM后台 GM授权后台 H5 Java Javascript Linux手工服务端 pipbestcom Python ReentrantLock synchronized ThreadLocal volatile Win一键即玩服务端 一键端 传奇 写作 创业 单机 后台 商业端 外网 安卓 安卓苹果双端 工具 手工端 手游 搭建教程 教程 数据分析 文案 游戏源码 端游 经典 网单 职场 自媒体 视频教程 详细搭建教程 运营后台 页游

近期文章

  • 回合手游【逍遥西游之繁华西游】最新整理单机一键既玩镜像服务端_Linux手工端_GM后台_教程
  • 最新整理精品回合制手游【天书奇谈3D混沌完整版】VM一键单机版_linux手工外网端_隐盟视频教程_授权GM后台_双端
  • 典藏修真页游【诸仙列传OL】最新整理Win系服务端_GM工具_详细外网搭建教程
  • MT3换皮MH【浮生若梦尊享挂机修复版】最新整理单机一键即玩镜像端_Linux手工服务端_安卓苹果双端_GM后台_详细搭建教程
  • 大话回合手游【最新引擎之缥缈西游渡劫版】最新整理Linux手工服务端_安卓苹果双端_管理后台_CDK后台_详细搭建教程_视频教程

分类

  • | wordpress插件 |
  • | wordpress模板 |
  • | 其它模板 |
  • | 帝国模板 |
  • | 织梦插件 |
  • | 织梦模板 |
  • A5源码
  • Android软件
  • APP引流
  • E语言
  • H5
  • LUA
  • QQ营销
  • SEO推广
  • Windows软件
  • 体育运动
  • 信息数据
  • 创业专题
  • 办公教程
  • 口才演讲
  • 名师讲座
  • 商城/淘客/交易
  • 小吃技术
  • 小说/漫画/阅读
  • 建站教程
  • 引流脚本
  • 影视/音乐/视频
  • 影视资源
  • 微信/微商/微擎
  • 微信小程序
  • 微信营销
  • 微擎模块
  • 手游源码
  • 技能学习
  • 抖音课程
  • 摄影教程
  • 棋牌教程
  • 模板/主题/插件
  • 游戏源码
  • 爆粉引流
  • 理财/金融/货币
  • 生活老师
  • 电商客
  • 电子文档
  • 电脑教程
  • 社群营销
  • 站长工具
  • 精品网单
  • 系统工具
  • 素材资料
  • 综合资料
  • 编程经验
  • 网站源码
  • 网络安全
  • 网赚教程
  • 网赚源码
  • 考研资料
  • 脚本/AI/智能
  • 自媒体
  • 英语学习
  • 营销软件
  • 设计素材
  • 说书小说
  • 贴吧引流
  • 软件工具
  • 软文营销
  • 逆向软件
  • 音频讲座
  • 页游源码

提供最优质的资源集合

立即加入 友好社区
金点网络-全网资源,一网打尽

新一代全网资源综合门户网(www.pipbest.com-金点网络)专注服务于互联网,提供各类最新最全的免费源码下载(PHP、ASP、JSP、.NET),更提供免费工具,免费源码下载,软件下载,素材下载,赚钱教程下载,交流论坛等网站运营相关的一切内容,为网友搜罗最有价值的网站源码下载与技术教程等服务!

服务目录
  • 金点OpenAPI
  • 金点云
  • 金点支付
友情链接
  • 数媒派
  • 国家电网
快速搜索

本站由Nice强力驱动

声明: 本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!

本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!
© 2016-2023 PipBest.Com - 金点网络 & 金点部落. All rights reserved 京ICP备2022005359号-1
  • 关注有礼
  • 签到
  • 客服
    官方QQ群 常见问题 FAQ

    在线客服

    点我联系

    直接说出您的需求!
    切记!带上资源连接与问题!

    工作时间: 9:30-21:30

  • 暗黑
    模式
  • 全屏
  • 投稿
    赚钱
  • 首页

  • 签到

  • 切换

  • 客服

金点网络-全网资源,一网打尽
  • 登录
  • 注册
or
or
忘记密码?
金点网络-全网资源,一网打尽
  • 网站首页 ►
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习 ►
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程 ►
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码 ►
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码 ►
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料 ►
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座 ►
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具 ►
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    ►
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
×
u3** 刚刚下载了 爆款吸金文案训练

    全网资源·一网打尽

  • 金点出品,必属精品!
  • 发布原创内容,获取高额提成!
  • 我们与你共创美好数字生态!
  • 无特殊说明密码默认:pipbest.com