集合框架 List篇(1)—ArrayList、LinkedList

  categories:资料  author:

来源:互联网

List
———–
1.ArrayList(jdk1.5以前版本中Vector)
2.LinkedList(jdk1.5以前版本中Stack)
3.CopyOnWriteArrayList

——————————

ArrayList是数组的实现形式(内部存储结构是一个数组):

public class ArrayList<E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

  private transient Object[] elementData;//存储元素的数组

//ArrayList的构造方法

public ArrayList(int initialCapacity) {//initialCapacity表示要创建的数组的容量
         super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];//创建initialCapacity长度的数组
    }

    /**
     *默认的构造 容量为10

     */
    public ArrayList() {
       this(10);
    }

    /**
     * 通过传入集合变量的形式初始化创建list的数组

     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
     }
—————————–

//添加新的元素到数组末尾时,如果超过了当前容量,就要对数组进行扩容,扩充为原来大小的1.5倍,

//由于扩容牵涉到整个数组的copy,对性能影响较大,所以如果知道要存放容量的大小,尽量在创建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 = Arrays.copyOf(elementData, newCapacity);
}

}

———————————–

//get方法实现很简单,就是指定到数组的index下标处,效率很高

public E get(int index) {
RangeCheck(index);

return (E) elementData[index];
}

——

添加元素后扩容情况的效果图:

wps_clip_image-31187[4][1]

//添加元素的方法,注意先调用ensureCapacity,保证有足够的容量(如果不足就扩容,上面有该方法介绍)

//由于add方法添加元素时,可能导致扩容操作,这也影响了其效率

public boolean add(E e) {
  ensureCapacity(size + 1);  

  elementData[size++] = e;
  return true;
}

—–

删除元素的效果图:

wps_clip_image-28812[4][1]

//删除元素的remove操作,牵涉到删除位置index后边元素的copy,所以ArrayList的remove操作效率不高

public E remove(int index) {
RangeCheck(index);

modCount++;
E oldValue = (E) elementData[index];

int numMoved = size – index – 1;//删除位置后边的元素个数
   if (numMoved > 0)//把要删除位置index后边的元素重新copy到数组的index处及以后
     System.arraycopy(elementData, index+1, elementData, index,  numMoved);

   elementData[–size] = null; // 把最后一个位置的元素置空,便于垃圾回收

    return oldValue;
}

——————

ensureCapacity

说明:ArrayList就是一个数组实现,适用于,  查找操作较多,而修改操作(add和delete)较少的情况,由于实现较为简单,就不再过多介绍,如果想更详细了解其实现,可以查看其源码。

下面要介绍的LinkedList适用于:查找较少,修改较多的情况(这与LinkedList的链式结构是有关系的)。

——————————-

LinkedList是链表结构的实现形式(内部存储结构是一个链表形式):

wps_clip_image-20528[4][1]

                                                                                           存储结构图示

LinkedList的类结构

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList的成员变量

private transient Entry<E> header = new Entry<E>(null, null, null);//链表的头结点
private transient int size = 0;//链表中元素的个数

LinkedList的构造方法

    /**
     * 构造一个空链表
     */
    public LinkedList() {
        header.next = header.previous = header;
    }

    /**
     * 通过传入一个集合初始化新链表

     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

  //addAll方法

public boolean addAll(int index, Collection<? extends E> c) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew==0)
            return false;
        modCount++;

        Entry<E> successor = (index==size ? header : entry(index));//后继结点,如果index==size时,后继结点指向header头结点
        Entry<E> predecessor = successor.previous;//前驱结点
        for (int i=0; i<numNew; i++) {//把集合元素连成一个双向子链表
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
            predecessor.next = e;
            predecessor = e;
         }
         successor.previous = predecessor;//“原始的后继结点"的前驱指向新子链表的最后一个结点

         size += numNew;//更新size大小
        return true;
    }

LinkedList的节点存储结构

private static class Entry<E> {//以内部类的形式定义Entry
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的get操作

//get操作,调用entry(index)方法,获得位置index位置的Entry对象
public E get(int index) {
    return entry(index).element;
}
//通过index得到指定位置的Entry结点
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)) {//优化了查找操作,如果index<size/2就从头结点向后遍历
       for (int i = 0; i <= index; i++)
          e = e.next;
   } else {//否则,向前遍历
       for (int i = size; i > index; i–)
          e = e.previous;
   }
   return e;
}

LinkedList的add操作

添加新元素到链表的末端,图示如下:

wps_clip_image-23692[4][1]

//add操作,把元素添加到链表的未段
public boolean add(E e) {
   addBefore(e, header);
   return true;
}

//把新元素e添加到entry的前面,当entry为header头结点时,相当于添加到链表的末端,如上图所示
private Entry<E> addBefore(E e, Entry<E> entry) {
   Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//以entry作为后继,以entry的前驱作为前驱
   newEntry.previous.next = newEntry;//更新引用
   newEntry.next.previous = newEntry;
   size++;//元素个数 加1
   modCount++;//修改次数 加1

  return newEntry;
}

—————————-

LinkedList的delete操作

删除元素E3,图示如下:

wps_clip_image-4500[4][1]

//remove操作,先调用entry(index)方法(上面有介绍)获得Entry对象,然后调用remove(entry)
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引用
   e.next.previous = e.previous;//改变e后继结点的previous引用
   e.next = e.previous = null;//把e置空,便于GC回收
   e.element = null;

   size–;//元素个数 减1
   modCount++;//修改次数 加1

  return result;
}

———-

另外,由于LinkedList实现了双向队列Deque接口,所以也具有队列的相关操作,可以当做一个队列使用。

http://hi.baidu.com/yao1111yao/item/3f358a5dd43f8314aaf6d791



快乐成长 每天进步一点点      京ICP备18032580号-1