文档章节

Java集合工具类之List - ArrayList & LinkedList

ruyees
 ruyees
发布于 2014/10/05 11:47
字数 825
阅读 14
收藏 0
点赞 0
评论 0

1.ArrayList 的数据结构和工作原理

与 Vector 一样, ArrayList 的 基本数据结构也是一个可变(动态)数组,数组的元素可以是任意对象。

ArrayList 的构造器有两种:

public ArrayList()

默认构造器的数组的长度是 10

public ArrayList(int initialCapacity)

指定 ArrayList 的初始化大小很重要, ArrayList 当添加元素的数量大于初始化(或上一次)数组的大小时,数组自动扩容成 oldSize*3/2+1, 新数组的元素是从老的数组 copy 而来的。

 

2.ArrayList 使用时需要注意的问题

1) ArrayList 使用时,最好能够预期需要存放元素的个数,这样可以避免数组长度频繁的改变而引起数据的 copy带来的开销,同时会引起内存大小的增加。

2 )使用 ArrayList 需要知道 ArrayList 是非线程安全的。因此,在使用时,最好是考虑这个对象会不会因为多个线程访问该 ArrayList 对象,如果确认多个线程访问,则可以用 Vector 或者 CopyOnWriteArrayList 来代替 ArrayList。

 

. LinkedList 的数据结构和工作原理

LinkedList 的基本数据结构是双向循环链表。链表的优点是插入和删除快,而查找或者修改比较慢。因为插入操作不会像 ArrayList 那样基于数组的数据结构,当插入时,超过原数组尺寸时,会将原数组的尺寸变成原来的3*size/2+1, 然后将原来数组的元素拷贝到新数组中,基于链表的操作只需将目标元素的尾部链接到原来链表的尾部就可以了。删除机制是同样的,基于数组的 ArrayList ,要删除元素,需要将该元素后面所有的元素向前 move一位。

 

构造器:

private transient Entry<E> header new Entry<E>( null null null );

 

// 初始花一个空的 header 链表,并将首尾相连成一个双向循环链表

public LinkedList() {

        header . next header . previous header ;

}

/**

核心方法之一:获取 index 位置的链表信息。此方法在 get , remove , add , set 都会用到

此处用到了二分查找来提高效率,如果 index

* 是在链表的前半段,则从头开始遍历,如果 index 在链表的后半部分,则从链尾遍历

  */

    private Entry<E> entry ( int index) {

        if (index < 0 || index >= size )

            throw new IndexOutOfBoundsException( "Index: " +index+

                                                ", Size: " + size );

        Entry<E> e = header ;

        if (index < ( size >> 1)) {

            for ( int i = 0; i <= index; i++)

                e = e. next ;

        } else {

            for ( int i = size ; i > index; i--)

                e = e. previous ;

        }

        return e;

}

 

/**

核心方法之一:将新的 e 元素, add 在指定 entry 的前面

  */

private Entry<E> addBefore (E e, Entry<E> entry) {

    Entry<E> newEntry = new Entry<E>(e, entry, entry. previous );

    newEntry. previous . next = newEntry;

    newEntry. next . previous = newEntry;

    size ++;

    modCount ++;

    return newEntry;

}

/**

将指定元素放在 header 之前,实际上就是放在链表的尾部

  */

public boolean add (E e) {

    addBefore(e, header );

        return true ;

}

/**

找到指定位置的元素,并将指定元素放在查找处的前面

  */

 

public void add ( int index, E element) {

        addBefore(element, (index== size header : entry(index)));

}

 

2. LinkedList 的其它应用

LinkedList 的双向性,可以轻松做一个 Stack 和 Queue :

public class LinkedListQueue <E> extends LinkedList<E>{

   

    //Like poll/remove

    public E dequeue(){

       return this .removeFirst();

    }

   

    //Like offer/add

    public void enqueue(E e){

       this .add(e);

    }

   

    //Like peek

    public E getHeader(){

       return this .getFirst();

    }

   

    public boolean empty(){

       return this .size()==0;

    }

}

本文转载自:http://zuoqiang.iteye.com/blog/1554845

共有 人打赏支持
ruyees
粉丝 3
博文 71
码字总数 0
作品 0
深圳
产品经理
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin ⋅ 05/25 ⋅ 0

Java编程学习:集合框架详解

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/30 ⋅ 0

并发编程(二):非线程安全集合类

前言 线程不安全的集合类 ArrayList: 结果一: 结果二: 抛出异常:ArrayIndexOutofBoundsException异常; 现象:出现null值; 出现输出不全的现象; 抛出异常; 原因: ArrayList中的add方...

mengdonghui123456 ⋅ 2017/08/14 ⋅ 0

java集合入门和深入学习,看这篇就差不多了

集合框架: Java中的集合框架大类可分为Collection和Map;两者的区别: Collection是单列集合;Map是双列集合 Collection中只有Set系列要求元素唯一;Map中键需要唯一,值可以重复 Collecti...

sihailoveyan ⋅ 05/04 ⋅ 0

阿里专家与你分享:你必须注意的Java编程细节

摘要:本文主要关注如何在Java中操作一系列对象,介绍了Java的内建类型——数组,并介绍了一些操作数组的方法;随后,介绍了JDK中的集合类,一元对象的存储使用了Collection,详细介绍了Colle...

nirvanalucky ⋅ 05/03 ⋅ 0

2018学习计划——Java基础之集合

Java——集合 前言 相信做开发的老铁们,不管你是做Java、Android、还是其他的语言,我相信很多都遇到过集合这个名词,而且我相信很多的老铁在进行大公司面试的时候,一定不可避免的会被问到...

Ray丶Cxy ⋅ 05/10 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb ⋅ 05/08 ⋅ 0

Java面试2018常考题目汇总及答案带走不谢!

一、JAVA基础篇-概念 1.简述你所知道的Linux: Linux起源于1991年,1995年流行起来的免费操作系统,目前, Linux是主流的服务器操作系统, 广泛应用于互联网、云计算、智能手机(Android)等...

java高级架构牛人 ⋅ 06/14 ⋅ 0

java编程语言知识要点学习java基础英语单词表

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/19 ⋅ 0

学习File类,并教你写FileUtil

写在前面的话 程序包括代码、数据、文档。在当今,数据对我们来说,尤为重要。或存数据库或写入文件。这样对于File类的学习,就显得十分必要。 编码 1、用什么编码写,就用什么编码读 2、掌握...

Wenyi_Feng ⋅ 05/15 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

tcp/ip详解-链路层

简介 设计链路层的目的: 为IP模块发送和接收IP数据报 为ARP模块发送ARP请求和接收ARP应答 为RARP模块发送RARP请求和接收RARP应答 TCP/IP支持多种链路层协议,如以太网、令牌环往、FDDI、RS-...

loda0128 ⋅ 41分钟前 ⋅ 0

spring.net aop代码例子

https://www.cnblogs.com/haogj/archive/2011/10/12/2207916.html

whoisliang ⋅ 57分钟前 ⋅ 0

发送短信如何限制1小时内最多发送11条短信

发送短信如何限制1小时内最多发送11条短信 场景: 发送短信属于付费业务,有时为了防止短信攻击,需要限制发送短信的频率,例如在1个小时之内最多发送11条短信. 如何实现呢? 思路有两个 截至到当...

黄威 ⋅ 昨天 ⋅ 0

mysql5.7系列修改root默认密码

操作系统为centos7 64 1、修改 /etc/my.cnf,在 [mysqld] 小节下添加一行:skip-grant-tables=1 这一行配置让 mysqld 启动时不对密码进行验证 2、重启 mysqld 服务:systemctl restart mysql...

sskill ⋅ 昨天 ⋅ 0

Intellij IDEA神器常用技巧六-Debug详解

在调试代码的时候,你的项目得debug模式启动,也就是点那个绿色的甲虫启动服务器,然后,就可以在代码里面断点调试啦。下面不要在意,这个快捷键具体是啥,因为,这个keymap是可以自己配置的...

Mkeeper ⋅ 昨天 ⋅ 0

zip压缩工具、tar打包、打包并压缩

zip 支持压缩目录 1.在/tmp/目录下创建目录(study_zip)及文件 root@yolks1 study_zip]# !treetree 11└── 2 └── 3 └── test_zip.txt2 directories, 1 file 2.yum...

蛋黄Yolks ⋅ 昨天 ⋅ 0

聊聊HystrixThreadPool

序 本文主要研究一下HystrixThreadPool HystrixThreadPool hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java /** * ThreadPool used to executed {@link Hys......

go4it ⋅ 昨天 ⋅ 0

容器之上传镜像到Docker hub

Docker hub在国内可以访问,首先要创建一个账号,这个后面会用到,我是用126邮箱注册的。 1. docker login List-1 Username不能使用你注册的邮箱,要用使用注册时用的username;要输入密码 ...

汉斯-冯-拉特 ⋅ 昨天 ⋅ 0

SpringBoot简单使用ehcache

1,SpringBoot版本 2.0.3.RELEASE ①,pom.xml <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.3.RELE......

暗中观察 ⋅ 昨天 ⋅ 0

Spring源码解析(八)——实例创建(下)

前言 来到实例创建的最后一节,前面已经将一个实例通过不同方式(工厂方法、构造器注入、默认构造器)给创建出来了,下面我们要对创建出来的实例进行一些“加工”处理。 源码解读 回顾下之前...

MarvelCode ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部