首页 > 代码库 > jdk集合常用方法分析之ArrayList&LinkedList&以及两者的对比分析

jdk集合常用方法分析之ArrayList&LinkedList&以及两者的对比分析

集合使用注意事项:

1、集合当中只能放置对象的引用,无法放置原生数据类型,我们需要使用原生数据类型的包装类才能加入到集合当中去(JDK5之后会进行自动的装箱和拆箱操作,表面上看集合中是可以直接放置原生数据类型进去,但实质上是进过自动装箱成对象操作的);

2、集合当中放置的都是Object类型,因此取出来的也是Object类型(可以放置任意类型的数据),那么必须要使用强制类型转换将其转换为真正的类型(放置进去的类型)。

 

ArrayList

ArrayList常用方法:

boolean add(E e)void add(int index, E element)void clear()E get(int index)int indexOf(Object o)boolean isEmpty()E remove(int index)boolean remove(Object o)int size()Object[] toArray()

ArrayList常用方法分析:

1、构造方法

List list = new ArrayList();

ArrayList底层采用数组实现,当使用不带参数的构造方法生成ArrayList对象时,实际上会在底层生成一个长度为10的Object类型数组来存放对象(的地址)。详见jdk源码:

public ArrayList() {    this(10);}public ArrayList(int initialCapacity) {    super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);    this.elementData = http://www.mamicode.com/new Object[initialCapacity];}private transient Object[] elementData;

2、add()方法

如果添加的元素个数超过了10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1

然后将原数组的内容复制到新数组当中,并且后续增加的内容都会放到新数组中;当新数组无法容纳增加的元素时,重复该过程。详见jdk源码:

public boolean add(E e) {    ensureCapacity(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}public void ensureCapacity(int minCapacity) {    modCount++;    int oldCapacity = elementData.length;    if (minCapacity > oldCapacity) {        Object oldData[] = elementData;        int newCapacity = (oldCapacity * 3)/2 + 1;            if (newCapacity < minCapacity)        newCapacity = minCapacity;            // minCapacity is usually close to size, so this is a win:            elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);    }}public static <T> T[] copyOf(T[] original, int newLength) {        return (T[]) copyOf(original, newLength, original.getClass());}

 

public void add(int index, E element) {    if (index > size || index < 0)        throw new IndexOutOfBoundsException(        "Index: "+index+", Size: "+size);    ensureCapacity(size+1);  // Increments modCount!!    System.arraycopy(elementData, index, elementData, index + 1, size - index);    elementData[index] = element;    size++;}public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

3、size()方法

返回List的长度

public int size() {    return size;}private int size;

4、remove()方法

public E remove(int index) {    RangeCheck(index);    modCount++;    E oldValue = (E) elementData[index];    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; // Let gc do its work    return oldValue;}public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

5、ArrayList常用方法总结:

1、对于ArrayList所有方法都不是同步的,而Vector大部分的public的方法都是同步的;

2、对于ArrayList元素的,添加和删除操作,需要将被删除或者添加到元素的后续元素向前或者向后移动,代价比较高。但是查找速度非常快(由数组的特点来决定的);

3、ArrayList在添加或者删除元素的时候,是需要移动大量元素的借助System.arraycopy()来实现拷贝移动;在查找时,可依靠数组下标快速定位

 

LinkedList

LinkedList常用方法有:

public void addFirst(E e)public void addLast(E e)public E getFirst()public E getLast()public E peek()public E pop()E remove(int index)public void push(E e)

LinkedList常用方法分析:

1、构造方法

LinkedList list = new LinkedList();
public LinkedList() {        //初始化时,将结点的前驱和后续都指向自己(header).形成了循环。        header.next = header.previous = header;}//LinkedList头结点的定义:private transient Entry<E> header = new Entry<E>(null, null, null);private transient Entry<E> header = new Entry<E>(null, null, null);  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;    }}

其中element就是我们想LinkedList中所添加到元素,然后Entry又构造好了向前与向后的引用previous和next,最后将生成的这个Entry对象加入到了链表当中;

换句话说,LinkedList中所维护的是一个个的Entry对象

2、add()方法

public boolean add(E e) {    addBefore(e, header);        return true;}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;}

3、remove()方法

调用remove()方法的时候只是改变了它的previous和next所指向的对象

public E remove(int index) {        return remove(entry(index));}private E remove(Entry<E> e) {    if (e == header)        throw new NoSuchElementException();    E result = e.element;    e.previous.next = e.next;    e.next.previous = e.previous;    e.next = e.previous = null;    e.element = null;    size--;    modCount++;        return result;}

ArrayList和LinkedList比较

1、ArrayList底层采用数组实现,它本质上是对象引用的一个可变长的数组;LinkedList底层采用双向链表实现

2、当执行插入或者删除操作时(本质上是由双向循环链表的特点决定的),采用LinkedList比较好;

3、当执行查找操作时(本质上是由数组的特点决定的),采用ArrayList比较好;

 

常见面试题:

问题1:ArrayList的大小是如何自动增加的?你能分享一下你的代码吗?

当试图在arraylist中增加一个对象的时候,Java会去检查arraylist,以确保已存在的数组中有足够的容量来存储这个新的对象

如果没有足够容量的话,那么就会新建一个长度更长的数组,旧的数组就会使用Arrays.copyOf方法被复制到新的数组中去现有的数组引用指向了新的数组

//ArrayList Add方法:public boolean add(E e){    ensureCapacity(size+1); //Increment modCount!!    elementData[size++] = e;    return true;} //ensureCapacity方法:处理ArrayList的大小public void ensureCapacity(int minCapacity) {    modCount++;    int oldCapacity = elementData.length;    if (minCapacity > oldCapacity) {    Object oldData[] = elementData;    int newCapacity = (oldCapacity * 3)/2 + 1;    if (newCapacity < minCapacity)        newCapacity = minCapacity;    // minCapacity is usually close to size, so this is a win:    elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);    }}

一定要注意如下三点:

1)新建了一个数组;

2)旧数组的对象被复制到了新的数组中;

3)并且现有的数组指向新的数组;

 

问题2:什么情况下你会使用ArrayList?什么时候你会选择LinkedList?

多数情况下,当遇到访问元素比插入或者是删除元素更加频繁的时候,应该使用ArrayList

另外一方面,当你在某个特别的索引中,插入或者是删除元素更加频繁,或者压根就不需要访问元素的时候,应该会选择LinkedList

这里的主要原因是:

1)在ArrayList中访问元素的最糟糕的时间复杂度是”1″,而在LinkedList中可能就是”n”了;

2)在ArrayList中增加或者删除某个元素,通常会调用System.arraycopy方法,这是一种极为消耗资源的操作,因此,在频繁的插入或者是删除元素的情况下,LinkedList的性能会更加好一点。

 

问题3:如何复制某个ArrayList到另一个ArrayList中去?写出你的代码? 

1)使用clone()方法,比如ArrayList newArray = oldArray.clone();

2)使用ArrayList构造方法,比如:ArrayList myObject = new ArrayList(myTempObject);

3)使用Collection的copy方法

注意1和2是浅拷贝(shallow copy)。

 

问题4:ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

在ArrayList中增加或者是删除元素,要调用System.arraycopy这种效率很低的操作,如果遇到了需要频繁插入或者是删除的时候,你可以选择其他的Java集合,比如LinkedList。

在ArrayList的某个索引i处添加元素:

 public void add(int index, E element) {    if (index > size || index < 0)        throw new IndexOutOfBoundsException(        "Index: "+index+", Size: "+size);    ensureCapacity(size+1);  // Increments modCount!!    System.arraycopy(elementData, index, elementData, index + 1, size - index);    elementData[index] = element;    size++;    }

删除ArrayList的某个索引i处的元素:

public E remove(int index) {    RangeCheck(index);    modCount++;    E oldValue = (E) elementData[index];    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; // Let gc do its work    return oldValue;    }

 

问题5:ArrayList、LinkedList以及Vector的区别?

1)ArrayList底层是使用数组来实现的,并且该数组的类型是Object类型的;

2)List list = new ArrayList();时,底层会生成一个长度为10的数组来存放对象;

3)对于ArrayList与Vector来说,底层都是采用数组方式来实现,该数组是一个Object类型的数组;

4)对于ArrayList,所以的方法都不是同步的,对于Vector,大部分public的方法都是同步的。(对比记忆StringBuffer和StringBuilder);

5)对于ArrayList,查找速度非常快,删除、增加操作非常慢,本质上是由数组的特点来决定的;

6)对于LinkedList,底层采用双向循环链表实现。查找非常慢,增加、删除操作非常快,本质上是由双向循环链表来决定的;

7)ArrayList是线程不安全的,但是效率高;Vector线程安全,但是效率低;

 

jdk集合常用方法分析之ArrayList&LinkedList&以及两者的对比分析