ArrayList 与 LinkedList实现比较

1、ArrayList实现是基于数组来实现的，这可由ArrayList的源码看出；

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private transient Object[] elementData;

    private int size;
    
    /*其他参数和方法*/
}

    ArrayList是List接口的长度可变的数组实现。

2、LinkedList是List和Deque接口的双向链表的实现，但是Java中并没有指针的概念，遂查看源码。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

    /**
     * 构造器，构建空表
     */
    public LinkedList() {
        header.next = header.previous = header;
    }

    /*其他参数、方法*/

    /**
    * LinkedList链表元素
    */
    private static class Entry<E> {
	E element;
	Entry<E> next;
	Entry<E> previous;

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }
 
    /**
    * LinkedList获取第一个元素的方法实现
    */
    public E getFirst() {
	if (size==0)
	    throw new NoSuchElementException();

	return header.next.element;
    }

}

    LinkedList利用私有静态类Entry定义了链表所用的数据成员。在Entry类中，每个类成员除了含有数据部分，还包括两个分别指向前一链表元素和后一链表元素的Entry类型的引用变量（跟C++中的指针很相似），由这种结构构成了LinkedList的链表结构。

 

注：ArrayList与LinkedList的实现都是不同步的。