歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> ArrayList LinkedList源碼解析

ArrayList LinkedList源碼解析

日期:2017/3/1 9:17:41   编辑:Linux編程

在Java中,集合這一數據結構應用廣泛,應用最多的莫過於List接口下面的ArrayList和LinkedList;

我們先說List,

public interface List<E> extends Collection<E> {
//返回list集合中元素的數量,若數量大於Integer.MAX_VALUE,則返回Integer.MAX_VALUE
int size();

//判讀集合內是否沒有元素,若沒有元素返回true
boolean isEmpty();

//判斷集合內是否包含指定的元素o
boolean contains(Object o);

//以適當的序列,返回該集合元素中的一個迭代器
Iterator<E> iterator();

//返回一個數組,該數組包含該集合中所有的元素(以從first到last的順序)
Object[] toArray();

//把集合中的元素放到數組a中,並返回
<T> T[] toArray(T[] a);
20
//向集合末尾中添加一個元素
boolean add(E e);

//從集合中刪除第一個出現的元素o
boolean remove(Object o);


//判斷集合中是否包含 指定集合c中的所有元素
boolean containsAll(Collection<?> c);

//將指定集合c中的所有元素都追加到 集合的末尾
boolean addAll(Collection<? extends E> c);

//將指定集合c中的所有元素都插入到 集合中,插入的開始位置為index
boolean addAll(int index, Collection<? extends E> c);

//將指定集合c中的所有元素從本集合中刪除
boolean removeAll(Collection<?> c);

//本集合和 集合c的交集
boolean retainAll(Collection<?> c);

//清除集合中的元素
void clear();

//比較指定對象o和本集合是否相等,只有指定對象為list,size大小和本集合size一樣,且每個元素equal一樣的情況下,才返回true
boolean equals(Object o);


int hashCode();

//返回指定位置index的元素
E get(int index);

//將元素element設置到集合的index位置(替換)
E set(int index, E element);

//將元素element插入到集合的index位置
void add(int index, E element);

//移除指定位置index的元素
E remove(int index);

//返回指定對象o在本集合中的第一個索引位置
int indexOf(Object o);

//返回指定對象o在本集合中的最後一個索引位置
int lastIndexOf(Object o);

//返回一個ListIterator的迭代器
ListIterator<E> listIterator();

//從指定位置index開始返回一個ListInterator迭代器
ListIterator<E> listIterator(int index);

//返回從位置fromIndex開始到位置toIndex結束的子集合
List<E> subList(int fromIndex, int toIndex);
}

下面我們看一看ArrayList,ArrayList是基於數組的方式來實現數據的增加、刪除、修改、搜索的。

ArrayList內部維護者兩個變量:


//該數組緩存者集合中的元素,集合的容量就是該數組的長度,elementData用transient修飾,說明在序列化時,數組elementData不在序列化范圍內。
private transient Object[] elementData;

//集合的大小 (集合中元素的數量)
private int size;


我們再看一看ArrayList的構造器:

/**
*構造一個指定容量initialCapacity的空的集合,
*super() 是調用AbstractList的默認構造器方法,該方法是一個空的方法,
*然後判斷傳入的參數initialCapacity不能小於0,否則就直接拋出非法參數異常;
*最後直接創建了一個長度為initialCapacity的數組對象,並將該對象賦值給當前實例的elementData屬性,用以存放集合中的元素。
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
*構造一個默認的容量為10的空的集合,我們平時最經常使用的List<T> list = new ArrayList<T>();是默認創建了容量為10的集合。
*/
public ArrayList() {
this(10);
}

/**
*構造一個包含了指定集合c中的所有元素的集合,該集合中元素的順序是以集合c的迭代器返回元素的順序。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

從上面的源碼中我們看到,先將c.toArray()方法的返回值賦值給elementData,將elementData.length賦值給size, 然後進行了一個判斷 if(elementData.getClass() != Object[].class),若為真,則調用Arrays.copyOf()方法創建一個新Object[]數組,將原來elementData中的元素copy到新建的Object[]數組中,最後將新建的數組賦值給elementData。

我們看一下Arrays.copyOf()方法的源碼:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

如果newType類型為Object[].class的話,則直接創建一個長度為newLength的Object數組,否則使用Array.newInstance(Class<?> componentType, int length)方法創建一個元素類型為newType.getComponentType() (該方法返回數組中元素的類型)類型的,長度為newLength的數組,這是一個native方法,然後使用System.arraycopy() 這個native方法將original數組中的元素copy到新創建的數組中,並返回該數組。

我們注意 c.toArray might (incorrectly) not return Object[],按理說一個c.toArray()返回的是一個Object[]類型,其getClass()返回的也一定是Object[].class,那為什麼還要進行逐個判斷呢? 可真實情況真的是這樣嗎?我們看下面的示例:

//定義一個父類Animal
public class Aniaml {

}

//定義Animal的子類Person
public class Person extends Aniaml{
private int id;
private String name;
private Date birthday;

public Person(int id, String name, Date birthday) {
this.id = id;
this.name = name;
this.birthday = birthday;
}

public static void main(String[] args) {
     test1();
     test2();
test3();
}

public static void test1(){
Person[] persons = {new Person(100,"lewis",new Date()),new Person(100,"lewis",new Date())};
//class [Lcom.lewis.guava.Person; Person的數組類型
System.out.println(persons.getClass());

Aniaml[] aniamls = persons;
//class [Lcom.lewis.guava.Person; Person的數組類型
System.out.println(aniamls.getClass());

//class com.lewis.guava.Person Person類型
System.out.println(aniamls[0].getClass());

//java.lang.ArrayStoreException animals[]數組中實際存儲的是Peron類型,當運行時放入非Person類型時會報錯ArrayStoreException
aniamls[0] = new Aniaml();
}

public static void test2(){
List<String> list = Arrays.asList("abc");
//class java.util.Arrays$ArrayList 由此可見該類型不是ArrayList類型
System.out.println(list.getClass());

Object[] objects = list.toArray();
//class [Ljava.lang.String; 返回的是String數組類型
System.out.println(objects.getClass());

//java.lang.ArrayStoreException: java.lang.Object 當我們將一個Object放入String數組時報錯ArrayStoreException
objects[0] = new Object();
}

public static void test3(){
List<String> dataList = new ArrayList<String>();
dataList.add("");
dataList.add("hehe");
    //class java.util.ArrayList
System.out.println(dataList.getClass());

Object[] objects1 = dataList.toArray();
    //class [Ljava.lang.Object;
System.out.println(objects1.getClass());
objects1[0]="adf";
objects1[0]=123;
objects1[0]=new Object();
}
}

我們由上面test2()方法可知,一個List,調用list.toArray()返回的Object數組的真實類型不一定是Object數組([Ljava.lang.Object;),當我們調用 Object[] objArray = collection.toArray(), objArray並不一定能夠存放Object對象,所以上面的源碼中對這種情況進行了判斷。

我們接著看ArrayList中的方法:

add(E),當我們添加數據的時候,會遇到的一個問題就是:當裡面的數組滿了,沒有可用的容量的怎麼辦?

/**
*插入對象,首先將size+1,產生一個minCapacity的變量,調用ensureCapacity(minCapacity)方法保證數組在插入一個元素時有可用的容量,然後將元素e放到數組elementData的size位置,最後將size+1
*/
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

/**
*必要時數組的擴容 (如果想調整ArrayList的容量增長策略,可以繼承ArrayList,override ensureCapacity()方法即可),
首先將modCount+1,modeCount表示修改數組結構的次數(維護在父類AbstractList中),如果入參minCapacity大於目前數組elementData的容量,則將容量擴展到 (oldCapacity * 3)/2 + 1,
若此時容量仍然小於 minCapacity,則直接將minCapacity設置為最新的容量,
最後使用Arrays.copyof()方法將原來elementData中元素copy到新的數組中,並將新數組賦值給elementData.
*/
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);
}
}

/**
*在指定下標Index處插入元素element,首先判斷下標index的參數是否有效(不能小於0,不能大於size),否則拋出IndexOutOfBoundsException異常,然後調用ensureCapacity(size+1)要確保數組中有足夠的容量來插入數據,
*然後調用System.arraycopy()方法, 從index下標開始,將elementData數組元素copy到 從index+1開始的地方,copy的長度為size-index,這樣index下標處的位置就空了出來,然後將元素element放到下標為index處的位置,最後將size++.
*我們看到使用這個方法相比add(E),多了一步數組元素的復制的代價。
*/
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++;
}

/**
*將元素element設值到下標為index處,返回原來index處的舊值。
*/
public E set(int index, E element) {
RangeCheck(index);
//獲取index下標的舊值
E oldValue = (E) elementData[index];
//設值新的元素element到index處
elementData[index] = element;
return oldValue;
}

//邊界檢查,index越界的話,拋出異常IndexOutOfBoundsException
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}

/**
*將指定集合c中的元素按照其迭代器返回的順序追加到本集合中,只要將任何一個元素插入到集合中都會返回true
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//確保(size+a.length)有足夠的容量去插入新元素
ensureCapacity(size + numNew); // Increments modCount
    //將數組a的內容追加到elementData數組的最後
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//只要插入的元素個數>0就返回true
return numNew != 0;
}

我們再看刪除的方法

/**
*刪除指定元素o,分為兩種情況,若指定元素o為null,則遍歷當前的elementData數組,如果某一個下標index上面的值為null(==),則調用方法fastRemove(int)快速刪除該元素,然後返回true
*若指定元素o不為0,則遍歷elementData數組,若某一個下標index處的元素和指定元素o 進行equals 為true的話,則調用fastRemove(int)快速刪除該元素,然後返回true
*由下面的源碼可知,只能刪除第一個匹配的元素。
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

/**
*快速刪除指定下標index的元素,不做邊界檢查(該方法時private的)
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
       //裡面進行了數組元素的移動,將index後面的元素往前復制一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
     //將數組elementData中最後一個位置置為null,以便釋放已用,讓gc 回收
elementData[--size] = null; // Let gc do its work
}

/**
*刪除指定下標index處的元素,該方法相比remove(Object o)方法,多了一個邊界檢查,但是少了元素的查找過程,因此性能更好一些。
*/
public E remove(int index) {
//對入參index做邊界檢查
RangeCheck(index);

modCount++;
  //取出index位置的元素
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
//返回原來index位置的舊元素
return oldValue;
}

元素的搜索:

/**
*獲取指定下標index處的元素,先進行邊界檢查,然後直接返回elementData數組中對應位置index處的元素。
*/
public E get(int index) {
RangeCheck(index);

return (E) elementData[index];
}

/**
*判斷集合中是否包含指定元素o,調用indexOf(Object o)方法實現
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

/**
*返回指定元素o在數組elementData首次出現的下標,這裡也是分為兩種情況:
*1.指定元素o為null 2.指定元素o不為null,在查詢元素的過程中,o為null,使用 == 比較,o不為null,使用equals比較,若找到了該元素,則返回其在數組elementData中的下標index,若找不到這返回-1.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

與indexOf(Object o)方法類似的是 lastIndexOf(Object o)方法,不同的是 後者返回的是最後一次出現指定元素o的位置下標。

public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

我們再看一下ArrayList的迭代器方法如何實現的:

/**
*該方法是有ArrayList的父類AbstractList持有的,返回的是一個Itr對象
*/
public Iterator<E> iterator() {
return new Itr();
}

我們看看Itr是個什麼鬼:

/**
*Itr 實現了Iterator接口,是AbstractList中的一個內部類。
*/
private class Itr implements Iterator<E> {
//當前迭代器指向的數組中元素的下一個元素的位置
int cursor = 0;

int lastRet = -1;

int expectedModCount = modCount;
//每次調用hasNext方法時,判斷當前指向的數組中的位置和數組大小是否相等,若不等則返回true(說明還有值),若相等則返回false(說明已經迭代到了數組的末尾了,沒有元素了)
public boolean hasNext() {
return cursor != size();
}
//調用next方法是,先調用checkForComodification()方法,判斷是否有其他線程對集合大小做出了有影響的動作;
//然後調用get方法獲取相應位置的元素,若獲取不到,則拋出IndexOutOfBoundsException異常,在捕獲到該異常後,調用checkForComodification()方法,
//檢測modcount若== expectedModCount(沒有其他線程對集合大小做出了有影響的操作),則拋出NoSuchElementException,若modcount != expectedModCount,則拋出ConcurrentModificationException
public E next() {
checkForComodification();
try {
E next = get(cursor);
lastRet = cursor++;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}

public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();

try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
//若modCount和期望的expectedModCount不相等,說明在迭代過程中,有其他的線程對集合大小產生了影響的動作(新增、刪除),此時拋出異常ConcurrentModificationException
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

我們在看一個方法trimToSize

/**
*將elementData數組的容量 縮小為該集合實際包含的元素數量
*/
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}

使用ArrayList的注意事項:

1.ArrayList是基於數組的方式實現的,可以通過下標索引直接查找到指定位置的元素,因此查找效率高,但每次插入或刪除元素,就要大量地移動元素,插入刪除元素的效率低。
2.ArrayList在插入元素時,可能會進行數組的擴容,但是在刪除元素時卻不會減小數組的容量,如果希望減小數組的容量,可使用trimToSize方法,在查找元素要遍歷數組時,對非null元素使用equals方法,對null元素使用==。
3.擴充容量的方法ensureCapacity。ArrayList在每次增加元素(可能是1個,也可能是一組)時,都要調用該方法來確保足夠的容量。當 容量不足以容納當前的元素個數時,就設置新的容量為舊的容量的1.5倍加1,如果設置後的新容量還不夠,則直接新容量設置為傳入的參數(也就是所需的容 量),而後用Arrays.copyof()方法將元素拷貝到新的數組。從中可以看出,當容量不夠時,每次增加元素,都要將原來的元 素拷貝到一個新的數組中,非常之耗時,也因此建議在事先能確定元素數量的情況下,才使用ArrayList,否則建議使用LinkedList
4.ArrayList不是線程安全的。

接著我們看下LinkedList,LinkedList是基於雙向鏈表的方式來實現的,雙向鏈表就是集合中的每個元素都知道其前面的一個元素的位置和它後的一個元素位置。

在LinkedList中,使用一個內部類Entry來表示集合中的節點,元素的值賦值給element屬性,節點的next屬性指向下一個節點,節點的previous屬性指向前一個節點。

private static class Entry<E> {
//element存放數據
E element;
//next屬性指向當前節點的下一個節點
Entry<E> next;
  //previous屬性指向當前節點的上一個節點
Entry<E> previous;

Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}

/**
*維護了一個header節點,header節點的element屬性為null,previouse屬性為null,next屬性為null,並且header節點是不存儲數據的
*/
private transient Entry<E> header = new Entry<E>(null, null, null);
//size表示集合包含的元素個數
private transient int size = 0;

/**
* 構造一個空的集合,將header節點的next屬性、previous屬���都指向header節點,這樣形成了一個雙向鏈表的閉環
*/
public LinkedList() {
header.next = header.previous = header;
}

新增操作

/**
*追加指定的元素e到集合尾部,其效果和方法 addLast(E e)是一致的,都是調用addBefore(e,header)方法。
*/
public boolean add(E e) {
addBefore(e, header);
return true;
}

/**
*將數據e 插入到元素entry前面(private級別,LinkedList內部調用,意味著不能直接在自己的應用程序中調用此方法,但是可以利用反射API來間接的調用(好想沒必要這樣做))
*/
private Entry<E> addBefore(E e, Entry<E> entry) {
//創建一個新節點newEntry,newEntry.element屬性設置為e,newEntry.next屬性設置為entry,newEntry.previous屬性設置為entry.previous
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
///將newEntry.previous節點的next屬性指向newEntry本身
newEntry.previous.next = newEntry;
//將newEntry.next節點的previous屬性指向newEntry本身
newEntry.next.previous = newEntry;
//將集合大小size + 1
size++;
//集合大小影響次數modCount + 1
modCount++;
  //返回新創建的節點
return newEntry;
}

更多詳情見請繼續閱讀下一頁的精彩內容: http://www.linuxidc.com/Linux/2016-03/129548p2.htm

Copyright © Linux教程網 All Rights Reserved