【面经总结】Java集合 - List

ArrayList

要点

实现机制

数组

扩容机制

初始容量为空列表，第一次插入后扩容成默认大小 10。

添加元素时如果已满，会自动扩容为原始大小的 1.5 倍。

类定义

// 类定义
public class ArrayList<E> 
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  1. 实现了 RandomAccess 接口，支持随机访问。

RandomAccess 是一个标志接口，说明该类支持快速随机访问

  1. 实现了 Cloneable 接口，默认为浅拷贝。
  2. 实现了 Serializable 接口，支持序列化。
  3. 非线程安全：可以使用 Collections.synchronizedList() 包装成线程安全的

数据结构

  1. elementData：对象数组（用于存数据）
  2. size：当前数组长度
  3. DEFAULT_CAPACITY：默认大小
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;

// 对象数组
transient Object[] elementData;

// 数组长度
private int size;

构造方法

  1. 无参构造：默认初始大小（10）
  2. 指定初始大小构造：减少数组的扩容次数，提高性能
public ArrayList() {
    // 创建一个空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 根据初始化值创建数组大小
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 初始化值为 0 时，创建一个空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

访问元素

通过下标获取，复杂度 O(1)

// 获取第 index 个元素
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

添加元素

  1. 尾部添加：直接放在数组最后
  2. 任意位置添加：向后复制后半段来腾出当前位置

默认大小为 10，超过数组大小会触发扩容 1.5 倍。

// 添加元素到数组末尾
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 添加元素到任意位置
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

ArrayList 的扩容机制：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // new = old * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

删除元素

删掉当前位置元素，将后半段向前复制

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

Fail-Fast 机制

使用 modCount 来记录结构发生变化的次数，用来避免并发修改异常。

LinkedList

要点

实现机制

基于双向链表：顺序访问会非常高效，而随机访问效率比较低。

类定义

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  1. 实现了 Deque 接口，也可以被当作队列 Queue 或双端队列 Deque进行操作
  2. 实现了 Cloneable 接口，默认为浅拷贝。
  3. 实现了 Serializable 接口，支持序列化。
  4. 非线程安全：可以使用 Collections.synchronizedList() 包装成线程安全的

数据结构

  1. size：数组长度
  2. first、last：双向链表头尾节点

Node：链表的节点

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    // ...
}

// 链表长度
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;

序列化

访问元素

通过 size 和 index 判断 Node 是在前半段还是后半段，再遍历链表。时间复杂度 O(n)

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

添加元素

  1. add、addLast：尾插
  2. addFirst：头插
  3. add(index, item)：指定位置插入
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) last = newNode;
    else f.prev = newNode;
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) first = newNode;
    else l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    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++;
}

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

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size) linkLast(element);
    else linkBefore(element, node(index));
}

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

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

删除元素

遍历找到要删除的元素节点，然后调用 unlink 方法删除节点

  • 前驱节点指向后继，否则更新头指针；
  • 后继节点指向前驱，否则更新尾指针。
public boolean remove(Object o) {
    if (o == null) {
        // 遍历找到要删除的元素节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 遍历找到要删除的元素节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

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) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Vector

基于数组实现，特性与ArrayList类似。（不再推荐使用）

线程安全：使用线程同步能力，多线程互斥写入Vector。

全部操作方法都加的有 synchronized 关键字，性能雪崩。

https://blog.csdn.net/weixin_44688973/article/details/119732347

List

Arrays.asList()

  1. 不能转换基本类型的数组：数组会被当成一个对象

  2. 返回的 List 不能增删：返回的不是正常的 ArrayList，没有重写 add 和 remove 方法

  3. 原始数组的修改会影响 List：转换后直接复用了原始的数组

  4. 不能直接使用 Arrays.asList() 来转换基本类型数组。

Arrays.asList() 方法传入的是一个泛型 T 的可变参数，会导致数组整体作为了一个对象成为了 T

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
  1. 返回的 List 不支持增删操作

Arrays.asList() 返回的 List 并不是的 java.util.ArrayList，而是 Arrays 的内部类 ArrayList。没有重写 add 和 remove 方法。

  1. 对原始数组的修改会影响到我们获得的那个 List

Arrays.asList() 转换后直接复用了原始的数组

List.subList()

用途：截取集合中的一部分

问题：

  1. subList 直接引用了原始的 List，而不是一个新的 List，操作会相互影响
  2. 如果原 List 在 subList 操作期间发生了结构修改（增删操作），操作 subList 会抛异常

解决：

  1. 使用新的集合 new ArrayList
  2. 使用 stream 流的 limit 进行操作

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/712797.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

DomoAI让你轻松变身视频达人！支持20s完整视频生成！

DomoAI让你轻松变身视频达人！支持20s完整视频生成！

账号注册 官网&#xff1a;https://www.domoai.app/zh-Hant/library 功能 支持不同风格的视频类型&#xff0c;支持图片转视频&#xff0c;支持文字转图片&#xff0c;支持静态图片变为动态。 可以切换语言为中文 风格转换 选择不同风格的 支持生成20s&#xff0c;目前接触…
阅读更多...
0. 云原生之基于乌班图远程开发

0. 云原生之基于乌班图远程开发

云原生专栏大纲 文章目录 安装乌班图配置静态IP重置root密码开启root远程登录开启远程SSH访问安装docker安装docker-compose安装Edge浏览器安装搜狗输入法安装TeamViewer安装虚拟显示器安装JDK安装maven安装vscodevscode插件安装VSCode配置maven、git、jdk、自动报错vscode快捷…
阅读更多...
2024年【陕西省安全员C证】考试及陕西省安全员C证最新解析

2024年【陕西省安全员C证】考试及陕西省安全员C证最新解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 陕西省安全员C证考试参考答案及陕西省安全员C证考试试题解析是安全生产模拟考试一点通题库老师及陕西省安全员C证操作证已考过的学员汇总&#xff0c;相对有效帮助陕西省安全员C证最新解析学员顺利通过考试。 1、【多…
阅读更多...
树以及二叉树的定义和特点

树以及二叉树的定义和特点

目录 开场白 树的定义 结点的分类 结点间的关系 树的其他相关概念 树的存储结构 孩子兄弟表示法 二叉树的定义 二叉树的特点 特殊二叉树 满二叉树 完全二叉树 二叉树的性质 二叉树的存储结构 开场白 这一篇文章是关于树的知识&#xff0c;这是一个比较特…
阅读更多...
Python 学习 用Python第二册 第9章内容解八皇后问题

Python 学习 用Python第二册 第9章内容解八皇后问题

----用教授的方法学习 目录 1.八皇后问题 2.状态表示(抽象) 3.检测冲突 4.基线条件 5.递归条件 6.结尾 1.八皇后问题 深受大家喜爱的计算机科学谜题&#xff1a;你需要将8个皇后放在棋盘上&#xff0c;条件是任何一个皇后都不能威胁其他皇后&#xff0c;即任何两个皇后…
阅读更多...
利用485缓存器实现两主一丛RS485串行通信

利用485缓存器实现两主一丛RS485串行通信

作者:艺捷自动化&#xff0c;其旗下产品有艺捷自动化网站和易为二维码小程序&#xff08;微信&#xff09; 对于工控自动化领域的电气工程师来说&#xff0c;基于RS485的串行通讯是最常见的。绝大部分仪表都能支持这种通讯方式。RS485通讯&#xff0c;是一种异步半双工模式&…
阅读更多...
誉天5月红帽战报：恭喜14名学员通过RHCE认证，通过率87.5%！

誉天5月红帽战报：恭喜14名学员通过RHCE认证，通过率87.5%！

红帽认证是全球公认的Linux权威认证之一&#xff0c;对于Linux从业者来说具有很高的价值和认可度。旨在评估考生在Linux系统管理和应用方面的专业知识和技能。红帽考试是Linux从业者提升自身技能水平和职业竞争力的重要途径之一。 5月份&#xff0c;誉天14名学员通过了RHCE认证…
阅读更多...
css入门宝典

css入门宝典

3.1.4 通配符选择器 语法 : *{} 作用 : 让页面中所有的标签执行该样式,通常用来清除间距 例子 : *{ margin: 0; //外间距 padding: 0; //内间距 } 一 CSS基本语法 1基础知识 1.1概述 Css (层叠样式表)是种格式化网页的标准方式&#xff0c; 用于控制设置网页的样式&#xff…
阅读更多...
WSL Ubuntu安装TensorFlow-GPU、PyTorch-GPU

WSL Ubuntu安装TensorFlow-GPU、PyTorch-GPU

在Windows 11的WSL Ubuntu中安装TensorFlow-GPU、PyTorch-GPU 0、WSL Ubuntu安装 在Windows 11的商店中下载即可&#xff0c;此处以Ubuntu22.04.3为例 1、CUDA Toolkit安装 参考公孙启的文章Windows11 WSL Ubuntu Pycharm Conda for deeplearning前往nVidia官网下载CUDA …
阅读更多...
transformer模型首次体验代码

transformer模型首次体验代码

前言 首先是安装python&#xff0c;更新pip源到清华源。安装transformer pip install transformer安装jupyter lab&#xff0c;也简单一行 pip install jupyterlab现在不想用anaconda了&#xff0c;因为国内没有源了&#xff0c;国外的又慢。直接用pip吧。 然后开始体验之旅…
阅读更多...
DeepDriving | CUDA编程-05：流和事件

DeepDriving | CUDA编程-05：流和事件

本文来源公众号“DeepDriving”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;CUDA编程-05&#xff1a;流和事件 1 CUDA流 在CUDA中有两个级别的并发&#xff1a;内核级并发和网格级并发。前面的文章DeepDriving | CUDA编程-04&…
阅读更多...
buildroot编译出错you should not run configure as root

buildroot编译出错you should not run configure as root

虚拟机版本&#xff1a;ubuntu-22.04.4 问题 buildroot在图形配置后&#xff0c;执行 sudo make开始编译出现以下错误configure: error: you should not run configure as root (set FOenvironment to bypass this check) 在网上看到说在/etc/profile文件中添加以下内容 exp…
阅读更多...
Ngunx + Tomcat 负载均衡和动态分离

Ngunx + Tomcat 负载均衡和动态分离

目录 一、tomcat简介 二、Nginx 负载均衡 1. Nginx 应用 2. Nginx 负载均衡实现原理 2.1 正向代理 2.2 反向代理 2.3 具体过程接收请求&#xff1a;Nginx作为反向代理服务器&#xff0c;接收客户端的请求。选择后端服务器&#xff1a;根据预先配置的负载均衡算法&#xf…
阅读更多...
23种设计模式之享元模式

23种设计模式之享元模式

享元模式 1、定义 享元模式&#xff1a;运用共享技术有效的支持大量细粒度对象的复用 2、享元模式结构 Flyweight&#xff08;抽象享元类&#xff09;&#xff1a;通常是一个接口或抽象类&#xff0c;在抽象享元类中声明了具体享元类公共的方法&#xff0c;这些方法可以向外…
阅读更多...
从多线程设计模式到对 CompletableFuture 的应用

从多线程设计模式到对 CompletableFuture 的应用

大家好&#xff0c;我是 方圆。最近在开发 延保服务 频道页时&#xff0c;为了提高查询效率&#xff0c;使用到了多线程技术。为了对多线程方案设计有更加充分的了解&#xff0c;在业余时间读完了《图解 Java 多线程设计模式》这本书&#xff0c;觉得收获良多。本篇文章将介绍其…
阅读更多...
几种经典查找算法

几种经典查找算法

几种经典查找算法 顺序查找法二分查找法判定树 二叉查找树&#xff08;BST&#xff09;索引查找B-树B树散列表&#xff08;hash&#xff09;查找 顺序查找法 顺序查找的平均查找长度为&#xff1a; 时间复杂度为0&#xff08;n&#xff09;&#xff1b; 二分查找法 int bin…
阅读更多...
CNN学习（7）：用C++实现简单不同参数的卷积模型

CNN学习（7）：用C++实现简单不同参数的卷积模型

目录 一、参数说明和计算公式 1、符号约定 2、输出大小计算公式 二、不同类型的卷积 1、输入3*3*1&#xff0c;卷积核3*3*1&#xff0c;输出1*1*1 &#xff08;1&#xff09;实现代码 &#xff08;2&#xff09;代码说明 2、输入4*4*1&#xff0c;卷积核3*3*1&#xff…
阅读更多...
环保评A的意义与价值

环保评A的意义与价值

环保评A&#xff0c;这个看似简单的称谓&#xff0c;背后却蕴藏着深厚的环保理念和实践标准。在当今社会&#xff0c;环保已经成为一项全球性的议题&#xff0c;各国都在努力推动绿色发展&#xff0c;实现可持续发展目标。那么&#xff0c;环保评A究竟是全国性的认证还是地方性…
阅读更多...
Java SSTI服务端模版注入漏洞原理与利用

Java SSTI服务端模版注入漏洞原理与利用

文章目录 前言Velocity基础语法基础示例命令执行 靶场实践漏洞代码漏洞验证检测工具 FreeMarker基础示例漏洞示例CMS案例 Thymeleaf基础示例漏洞示例安全方案 总结 前言 SSTI&#xff08;Server Side Template Injection&#xff09;全称服务端模板注入漏洞&#xff0c;在 Jav…
阅读更多...
开放式耳机值得入手买吗？可以对比这几款开放式耳机看看

开放式耳机值得入手买吗？可以对比这几款开放式耳机看看

居家办公时&#xff0c;选择一款合适的耳机能够有效地提高工作效率。入耳式耳机虽然能够有效地隔绝外界噪音&#xff0c;但长时间佩戴会对耳朵造成负担&#xff0c;甚至引发耳道感染。而头戴式耳机虽然能够提供更好的音质&#xff0c;但体积较大&#xff0c;佩戴起来不够灵活。…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站