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

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。

 

1 ． 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;

    }

}