Java容器篇小结之List自问自答

I. List篇

0. 什么是List

看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂

列表,什么是列表呢?

好比你到了一个村里,看到每个房子上的门牌号,如这是张村1号,下一个是张村2号,接着是3号、4号...

现在你要去张村10号,那么得,顺着这个门牌一直往下走,就能找到了

这个村落里的门牌号的形式,就特别像JDK中的 LinkedList了,找张村10号的过程基本就是 LinkedList#indexOf()根据索引获取对应值的过程了

从这个case里面,小结一下List的特点

  • 顺序性,有序(一个接一个,像冰糖葫芦似的串在一起)
  • 唯一性(一个萝卜一个坑,不允许一个索引捞出多个内容出来)

这个顺序性好说,这个唯一性是我一家之言,多半描述得不太妥当,出发是为了与Map进行对比 ,下面重点说明一下

之前的博文Java Map常见问题汇总小结 把Map比作了词典,换在这里比作村牌号,可以这么玩,将户主名和门牌号一一对应,你报一个户主名,我就告诉你他家门牌号,然后就有这么个问题了

  • 张三家的门牌是张村五号
  • 后面张五家生了个小孩,也取名叫张三,然后张三自立门户了,门牌分的是张村105号

现在我问张三家门牌是多少?是五号呢还是105呢?这个就不唯一了

换成链表的方式,你报一个门牌号,要么这门牌号无效,要么就只有一家在哪儿等着你呢,这就是我所说的唯一性

(废话比较多,可惜没有稿费)


1. 常见的List有那些

JDK中实现了一些能够覆盖绝大部分场景的List容器,罗列一些常见的如下

  • ArrayList
  • LinkedList
  • Vector
  • CopyOnWriteArrayList

2. 根据不同的分类方式,对上面的List进行划分

根据是否线程安全分类

线程安全

非线程安全

Vector, CopyOnWriteArrayList

ArrayList, LinkedList


根据获取数据的时间复杂度

O(1)

O(n)

ArrayList, Vector, CopyOnWriteArrayList

LinkedList

这个分类有点意思了,前面三个,给了索引,立马就把数据给你;这后面的一个,得遍历一把找到对应的位置再返回数据,详情建第四条


底层数据结构

数组

链表

ArrayList, Vector, CopyOnWriteArrayList

LinkedList


扩容原理分类

动态扩容

无扩容一说

ArrayList, Vector, CopyOnWriteArrayList

LinkedList


3. ArrayList怎么用,如何实现的

基于数组的链表 ArrayList, 常用做有序数据存储的容器,一般使用的三把斧

// 1. 创建数组
List<String> list = new ArrayList<>();

// 2. 添加数据
list.add("word");
list.add(0, "hello");

// 3. 获取数组
list.get(0);

实现原理简要说明

  • ArrayList底层数据结构为数组
  • add(obj)会将数据直接扔进数组中,索引为当前列表的长度size,然后size+1
  • 若数组已经满了,塞不下新的数据了,此时需要将数组扩容,优先扩容原来容量的1.5倍(若依旧不够,则扩容到恰好能容纳所有元素)
  • add(index, obj), 在索引处添加数据,会导致原数组中,索引之后的数据后移(即会出现数组拷贝)
  • 删除末尾数据,直接将其置为null
  • 删除数组内部的数据,会出现数组拷贝
  • 删除元素,不会导致数组扩容(缩容)
  • 查询索引位置内容,实际上是直接利用数组的获取方式

4. ArrayList, LinkedList区别与适用场景

两者的底层存储结构不同,直接导致最终的使用场景的区别,下面以列表方式给出对比

说明

ArrayList

LinkedList

存储结构

随机访问

根据数组索引定位,耗时 O(1)

从链表头or链表尾遍历,耗时O(n)

新增数据

列表个数超过数组容量,则数组扩容,出现数组拷贝

定位到插入位置,新增一个节点插入链表中

是否扩容逻辑

插入超过上限扩容 <br/> 1. 增加原来空间大小的一半 <br/> 2. 若仍塞不下,则扩充到填满

无扩容逻辑

应用场景

1. 适合随机访问 <br/> 2. 随机插入or删除导致数组拷贝 <br/> 3. 末尾插入,较友好 <br/>

1. 随机访问性能差,适合遍历场景<br/> 2. 随机插入or删除,先遍历获取位置,然后插入or删除<br/> 3. 链表头尾插入友好 <br/>


5. ArrayList是否线程安全,如何保证线程安全

ArrayList 非线程安全,即在遍历一个ArrayList对象时,若出现修改,则会抛一个并发修改异常,通常为了保障线程安全,请使用 CopyOnWriteArrayList代替,至于Vector,已经退出历史舞台了

Vector

线程安全的列表,其实现是在所有的方法上加了同步锁,确保同一时刻,只有一个线程在访问列表,是一种伪并发的使用方式

CopyOnWriteArrayList

写副本,替换原链表的方式实现线程安全,基本原理如下

  • 读方法不加锁;修改方法加锁,一次只能一个写线程访问
  • 修改时,会拷贝一份内容出来,对拷贝的结果进行操作,最后覆盖之前的内容
  • 遍历和读取都是基于访问时刻列表中的数组进行的;在执行过程中,链表发生修改不会影响遍历和读取的结果(即此时访问的依然是原数组内容)

6. 几种遍历方式

把这个单独拎出来有点混字数的感觉(多谢也没有啥收益,纯属手欠...)

一般的遍历方式是采用foreach语法

List<String> strList = new ArrayList<>();
// ....
for(String str: strList) {
  System.out.println(str);
}

还有一种用得较少,一般是在要遍历的过程中,修改列表的值时使用

List<String> strList = new ArrayList<>();
Iterator<String> iterator = strList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    if(xxx) {
        iterator.remove();
    }
}

那么问题来了,在第一种方式中,若是修改了会怎么样

@Test
public void testRemove() {
    List<String> strList = new ArrayList<String>();
    strList.add("hello");
    strList.add("world");
    strList.add("test1");
    strList.add("test2");
    strList.remove(0);
    int i = 0;
    for(String str: strList) {
        System.out.println(str);
        if(++i == 1) {
            strList.remove(i);
        }
    }
}

抛了并发修改异常

7. 如何设计一个线程安全的ArrayList

完全照着CopyOnWriteArrayList抄的话就没意思了,然而让自己去想一个方案,可以怎么搞?实现省略,暂时没想法。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

7620
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十九】Iterator&fail-fast机制

【Java提高十九】Iterator&fail-fast机制 Iterator详解 迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行...

411110
来自专栏WindCoder

Java漫谈-容器

除并发应用,Queue在Java SE5中仅有两个实现 LinkedList和PriorityQueue,差异在于排序行为,而不是性能。

8810
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

23190
来自专栏java一日一条

关于Java集合的小抄

在尽可能短的篇幅里,将所有集合与并发集合的特征,实现方式,性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。

7210
来自专栏Java学习网

Java中三种Set类型用法、性能大比拼

Java为开发者提供了大量的工具类,这给开发人员带来了很大方便,但是选择多了也有困扰,究竟用哪个类;我想选择什么,一是看自己具体需求,二是类本身的性能和用法;J...

88060
来自专栏java工会

面试官最喜欢问的十道java面试题

20380
来自专栏Spark学习技巧

JAVA集合框架中的常用集合及其特点、适用场景、实现原理简介

17730
来自专栏微信公众号:Java团长

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

9310
来自专栏落花落雨不落叶

leetcode 34. Search for a Range

30960

扫码关注云+社区

领取腾讯云代金券