文档章节

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

ruyees
 ruyees
发布于 2014/10/05 11:47
字数 825
阅读 15
收藏 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 Connection集合分析之List

Java Connection集合家庭分析 Java集合大致可以分为Set、List、Queue和Map四种体系,其中Set代表无序、不可重复的集合;List代表有序、重复的集合;而Map则代表具有映射关系的集合,Java 5 ...

我爱春天的毛毛雨
11/14
0
0
Java高级篇 -- List选择及优化

在java编程中,我们常常使用到java自带的集合类List 以下为几点简单的优化建议: 1.Vector还是ArrayList Vector有其特有有点,其每个方法都为同步方法【synchronized】,所以是线程安全的,在...

YOTOO
2014/05/05
0
0
​比较Collection 和Collections的区别

1、java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最...

itfanr
2014/11/24
0
0
从 Java 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
568
3
关于java.util.Vector 或 java.util.Hashtable类过时的讨论

某些高级IDE在检测代码成熟问题时,会报告集合是否过时的问题。目前过时的集合类有两个java.util.Vector 和 java.util.Hashtable 。 Vector的api描述是:从jdk 1.2版本开始,该类被修正为实现...

Barudisshu
2013/09/10
0
2

没有更多内容

加载失败,请刷新页面

加载更多

EOS docker开发环境

使用eos docker镜像是部署本地EOS开发环境的最轻松愉快的方法。使用官方提供的eos docker镜像,你可以快速建立一个eos开发环境,可以迅速启动开发节点和钱包服务器、创建账户、编写智能合约....

汇智网教程
今天
8
0
《唐史原来超有趣》的读后感优秀范文3700字

《唐史原来超有趣》的读后感优秀范文3700字: 作者:花若离。我今天分享的内容《唐史原来超有趣》这本书的读后感,我将这本书看了一遍之后就束之高阁了,不过里面的内容一直在在脑海中回放,...

原创小博客
今天
14
0
IC-CAD Methodology知识图谱

CAD (Computer Aided Design),计算机辅助设计,指利用计算机及其图形设备帮助设计人员进行设计工作,这个定义同样可以用来近似描述IC公司CAD工程师这个岗位的工作。 早期IC公司的CAD岗位最初...

李艳青1987
今天
15
0
CompletableFuture get方法一直阻塞或抛出TimeoutException

问题描述 最近刚刚上线的服务突然抛出大量的TimeoutException,查询后发现是使用了CompletableFuture,并且在执行future.get(5, TimeUnit.SECONDS);时抛出了TimeoutException异常,导致接口响...

xiaolyuh
今天
8
0
dubbo 搭建与使用

官网:http://dubbo.apache.org/en-us/ 一,安装监控中心(可以不安装) admin管理控制台,monitor监控中心 下载 bubbo ops 这个是新版的,需要node.js环境,我没有就用老版的了...

小兵胖胖
今天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部