文档章节

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

ruyees
 ruyees
发布于 2014/10/05 11:47
字数 825
阅读 14
收藏 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
深圳
产品经理
​比较Collection 和Collections的区别

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

itfanr
2014/11/24
0
0
Java高级篇 -- List选择及优化

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

YOTOO
2014/05/05
0
0
关于java.util.Vector 或 java.util.Hashtable类过时的讨论

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

Barudisshu
2013/09/10
0
2
Vector、ArrayList、LinkedList 有什么区别?

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/82086185 这个问题主要是考察集合框架的问题,主要考察三者之间的设计区别,以...

兴国First
08/26
0
0
Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

Java2的集合框架,抽其核心,主要有三种:List、Set和Map。如下图所示: 需要注意的是,这里的 Collection、List、Set和Map都是接口(Interface),不是具体的类实现。 List lst = new Array...

止静
2014/09/19
0
1

没有更多内容

加载失败,请刷新页面

加载更多

Java Lock接口分析之ReentantReadWriteLock

ReentantReadWriteLock读写锁,在读线程多余写线程的并发环境中能体现出优异的性能,相比于synchronized与ReentrantLock这种独占式锁的模型,ReentantReadWriteLock采用独占式写锁与共享式读...

我爱春天的毛毛雨
17分钟前
0
0
EFK (Fluentd ElasticSearch Kibana) 采集nginx日志

本文描述如何通过FEK组合集中化nginx的访问日志。本人更喜欢按顺序来命名,所以使用FEK而不是EFK. 首先在nginx服务器上执行以下操作. 安装ruby http://blog.csdn.net/chenhaifeng2016/artic...

xiaomin0322
19分钟前
0
0
一键下载:将知乎专栏导出成电子书

老是有同学问,学了 Python 基础后不知道可以做点什么来提高。今天就再用个小例子,给大家讲讲,通过 Python 和爬虫,可以完成怎样的小工具。 在知乎上,你一定关注了一些不错的专栏(比如 ...

crossin
28分钟前
1
0
synchronized 之 对象锁 和 类锁

一、synchronized(object) 如果object没有被加锁,则获取object的锁;如果object已经被加锁则等待object的锁被释放。 二、需要加锁的情景 多线程共享同一资源会引起线程安全的情况下,才需要...

MyOldTime
29分钟前
6
0
tomcat 单机/多机 部署多应用

一.单机部署多应用: 1.在 linux 下解压安装两个 tomcat:tomcat1, tomcat2; 2.修改 /etc/profile, 增加 tomcat 环境变量: path 中加上 重新加载配置文件 source /etc/profile 3.修改 tomc...

imbiao
40分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部