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

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

2024-07-22 03:05:10   225人阅读

集合使用注意事项：

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&以及两者的对比分析


联系
我们