ArrayList和LinkList剖析

16-06-27 来源：[db:作者]

收藏我要投稿

一、---概念---

ArrayList使用的是动态数组的方式，在下面的源码分析中会看到具体是怎么使用动态数组的方式。下面从定义入手来开始分析：

public class ArrayList extends AbstractList  implements List, RandomAccess, Cloneable, java.io.Serializable

从ArrayList的定义中可以看出其继承了AbstractList类，实现了RandomAccess、Cloneable、Serializable接口

（1）AbstractList提供了List接口的默认实现（个别方法为抽象方法）。

（2）RandomAccess是一个标记接口，接口内没有定义任何内容。

（3）实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝。

（4）通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。

二、---属性---

ArrayList中有两个属性：elementData和size

/*The array buffer into which the elements of the ArrayList are stored. 
      * The capacity of the ArrayList is the length of this array buffer. 
      */  
     private transient Object[] elementData;  
     /** 
      * The size of the ArrayList (the number of elements it contains). 
      */  
     private int size;

Java的serialization提供了一种持久化对象实例的机制。持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization

机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient

也就是说我们想这个持久化的机制是一种打开着的，当我们想要将其关闭的时候就需要使用transient。

通过例子来说明一下：

package TwoWeek;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

class UserInfo implements Serializable {  
    private static final long serialVersionUID = 996890129747019948L;  
    private String name;  
    private transient String psw;  
  
    public UserInfo(String name, String psw) {  
        this.name = name;  
        this.psw = psw;  
    }  
  
    public String toString() {  
        return "name=" + name + ", psw=" + psw;  
    }  
}  
  
public class TestTransient {  
    public static void main(String[] args) {  
        UserInfo userInfo = new UserInfo("张三", "123456");  
        System.out.println(userInfo);  
        try {  
            // 序列化，被设置为transient的属性没有被序列化  
            ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(  
                    "UserInfo.out"));  
            o.writeObject(userInfo);  
            o.close();  
        } catch (Exception e) {  
            // TODO: handle exception  
            e.printStackTrace();  
        }  
        try {  
            // 重新读取内容  
            ObjectInputStream in = new ObjectInputStream(new FileInputStream(  
                    "UserInfo.out"));  
            UserInfo readUserInfo = (UserInfo) in.readObject();  
            //读取后psw的内容为null  
            System.out.println(readUserInfo.toString());  
        } catch (Exception e) {  
            // TODO: handle exception  
            e.printStackTrace();  
        }  
    }  
}

---Output---

name=张三, psw=123456
name=张三, psw=null

注释中写到了别transient的psw没有被序列化也就是没有被存储。

三、---构造方法---

ArrayList中为我们提供了三个构造方法。

/** 
      * Constructs an empty list with the specified initial capacity. 
      */  
     public ArrayList(int initialCapacity) {  
     super();  
         if (initialCapacity < 0)  
             throw new IllegalArgumentException("Illegal Capacity: "+  
                                                initialCapacity);  
     this.elementData = new Object[initialCapacity];  
     }  
     /** 
      * Constructs an empty list with an initial capacity of ten. 
      */  
     public ArrayList() {  
     this(10);  
     }    
     /** 
      * Constructs a list containing the elements of the specified 
      * collection, in the order they are returned by the collection's 
      * iterator. 
      */  
     public ArrayList(Collection 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）第一个构造方法使用提供的initialCapacity来初始化elementData数组的大小。

（2）第二个构造方法调用第一个构造方法并传入参数10，即默认elementData数组的大小为10。

（3）第三个构造方法则将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为

Object[]）。

四、---其他方法---

4.1add(E e)

先调用了ensureCapacity(size+1)方法，之后将元素的索引赋给elementData[size]，而后size自增。例如初次添加时，size为

0，add将elementData[0]赋值为e，然后size设置为1（类似执行以下两条语句elementData[0]=e;size=1）。

public boolean add(E e) {  
    ensureCapacity(size + 1);  // Increments modCount!!  
    elementData[size++] = e;  
    return true;  
    }

也就是说ensureCapacity()起到的是扩充空间的作用，elementData起到的是赋值的作用，下面来看下ensureCapacity()是怎

么来进行空间的扩充的。

     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);  
     }  
     }

首先modCount是整个list结构被改变的次数，增加modCount之后，判断minCapacity（即size+1）是否大于oldCapacity（即

elementData.length），若大于，则调整容量为max((oldCapacity*3)/2+1,minCapacity)，调整elementData容量为新的容量，

即将返回一个内容为原数组元素，大小为新容量的数组赋给elementData，否则不做操作。

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++;  
     }

首先也是进行数组容量的扩充，然后将数组index及后面的内容向后移动一位，最后将element插入到index的位置上。

4.3contains(Object)

数组中是否包含某个对象

public boolean contains(Object o) {  
     return indexOf(o) >= 0;  
     }

其中indexOf()中的判断null的过程是非常值得去学习的，这体现了源代码的全面性和严谨性

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;  
     }

4.4removeRange

removeRage(int fromIndex, int toIndex)，指的是移除一个范围的元素，源代码如下：

protected void removeRange(int fromIndex, int toIndex) {  
     modCount++;  
     int numMoved = size - toIndex;  
         System.arraycopy(elementData, toIndex, elementData, fromIndex,  
                          numMoved);  
   
     // Let gc do its work  
     int newSize = size - (toIndex-fromIndex);  
     while (size != newSize)  
         elementData[--size] = null;  
     }

执行过程是将elementData从toIndex位置开始的元素向前移动到fromIndex，然后将toIndex位置之后的元素全部置空顺便修改

size。也就是将大于newSize坐标的元素全都置为0

以上是对ArrayList中几个典型方法的源代码分析，还有很多就不一一列举了。

-------------------------------------------------LinkList-------------------------------------------------------

一、---概念---

LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。除此之外，LinkedList还提供了一些可以使其作为栈、队列、双端队列的方法。这些方法中有些彼此之间只是名

称的区别，以使得这些名字在特定的上下文中显得更加的合适。以下是LinkList的定义：

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

从这段代码中我们可以清晰地看出LinkedList继承AbstractSequentialList，实现List、Deque、Cloneable、Serializable。（1）AbstractSequentialList提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作,从而以减少实现List接口的复杂度。

（2）Deque一个线性 collection，支持在两端插入和移除元素，定义了双端队列的操作。

二、---属性---

在LinkList中提供了两个基本的属性，一个是size，一个是header，其中size代表的是LinkList的大小，header是代表的链表的头

private transient Entry header = new Entry(null, null, null);  
private transient int size = 0;

private static class Entry {  
        E element;        //元素节点  
        Entry next;    //下一个元素  
        Entry previous;  //上一个元素  
        Entry(E element, Entry next, Entry previous) {  
            this.element = element;  
            this.next = next;  
            this.previous = previous;  
        }  
    }

上面是Entry()也就是一个LinkList的一个结点，从中可以看出，这是一个双向链表。

三、---构造方法---

LinkedList提高了两个构造方法：LinkedLis()和LinkedList(Collectionc)。

/** 
     *  构造一个空列表。 
     */  
    public LinkedList() {  
        header.next = header.previous = header;  
    }  
    /** 
     *  构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。 
     */  
    public LinkedList(Collection c) {  
        this();  
        addAll(c);  
    }

LinkedList(Collectionc)：构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。该构造函数首先会调用LinkedList()，构造一个空列表，然后调用了addAll()方法将Collection中的所有元素添加到列表中。

四、---其他方法---

4.1addAll( )

构造函数首先会调，以下是addAll()代码，如下：

/** 
     *  添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。 
     */  
    public boolean addAll(Collection c) {  
        return addAll(size, c);  
    }     
    /** 
     * 将指定 collection 中的所有元素从指定位置开始插入此列表。其中index表示在其中插入指定collection中第一个元素的索引 
     */  
    public boolean addAll(int index, Collection c) {  
        //若插入的位置小于0或者大于链表长度，则抛出IndexOutOfBoundsException异常  
        if (index < 0 || index > size)  
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);  
        Object[] a = c.toArray();  
        int numNew = a.length;    //插入元素的个数  
        //若插入的元素为空，则返回false  
        if (numNew == 0)  
            return false;  
        //modCount:在AbstractList中定义的，表示从结构上修改列表的次数  
        modCount++;  
        //获取插入位置的节点，若插入的位置在size处，则是头节点，否则获取index位置处的节点  
        Entry successor = (index == size ? header : entry(index));  
        //插入位置的前一个节点，在插入过程中需要修改该节点的next引用：指向插入的节点元素  
        Entry predecessor = successor.previous;  
        //执行插入动作  
        for (int i = 0; i < numNew; i++) {  
            //构造一个节点e，这里已经执行了插入节点动作同时修改了相邻节点的指向引用  
            Entry e = new Entry((E) a[i], successor, predecessor);  
            //将插入位置前一个节点的下一个元素引用指向当前元素  
            predecessor.next = e;  
            //修改插入位置的前一个节点，这样做的目的是将插入位置右移一位，保证后续的元素是插在该元素的后面，确保这些元素的顺序  
            predecessor = e;  
        }  
        successor.previous = predecessor;  
        //修改容量大小  
        size += numNew;  
        return true;  
    }

首先要获取插入位置处的结点，然后再获取插入位置处结点的前一个结点，然后再执行插入的动作。

在addAll()方法中，涉及到了两个方法，一个是entry(int index)，该方法为LinkedList的私有方法，主要是用来查找index位置的节点元素。

/** 
     * 返回指定位置(若存在)的节点元素 
     */  
    private Entry entry(int index) {  
        if (index < 0 || index >= size)  
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: "  
                    + size);  
        //头部节点  
        Entry e = header;  
        //判断遍历的方向  
        if (index < (size >> 1)) {  
            for (int i = 0; i <= index; i++)  
                e = e.next;  
        } else {  
            for (int i = size; i > index; i--)  
                e = e.previous;  
        }  
        return e;  
    }

4.2add( E e )

将指定元素添加到该链表的结尾处

public boolean add(E e) {  
    addBefore(e, header);  
        return true;  
    }

调用addBefore()方法，将元素和链表相链接

private Entry addBefore(E e, Entry entry) {  
        //利用Entry构造函数构建一个新节点 newEntry，  
        Entry newEntry = new Entry(e, entry, entry.previous);  
        //修改newEntry的前后节点的引用，确保其链表的引用关系是正确的  
        newEntry.previous.next = newEntry;  
        newEntry.next.previous = newEntry;  
        //容量+1  
        size++;  
        //修改次数+1  
        modCount++;  
        return newEntry;  
    }

4.3remove( Object e )

移除该链表的指定元素，该链表的源代码如下：

public boolean remove(Object o) {  
        if (o==null) {  
            for (Entry e = header.next; e != header; e = e.next) {  
                if (e.element==null) {  
                    remove(e);  
                    return true;  
                }  
            }  
        } else {  
            for (Entry e = header.next; e != header; e = e.next) {  
                if (o.equals(e.element)) {  
                    remove(e);  
                    return true;  
                }  
            }  
        }  
        return false;  
    }

上面的代码中设计到了remove方法，remove(Entry e)，remove(Entry e)为私有方法，是LinkedList中所有移除方法的基础方法。

private E remove(Entry e) {  
        if (e == header)  
            throw new NoSuchElementException();  
  
        //保留被移除的元素：要返回  
        E result = e.element;    
        //将该节点的前一节点的next指向该节点后节点  
        e.previous.next = e.next;  
        //将该节点的后一节点的previous指向该节点的前节点  
        //这两步就可以将该节点从链表从除去：在该链表中是无法遍历到该节点的  
        e.next.previous = e.previous;  
        //将该节点归空  
        e.next = e.previous = null;  
        e.element = null;  
        size--;  
        modCount++;  
        return result;  
    }

上面的只是几个简单的方法介绍，初次之外还有contains()，clear()， getFirst()，get()等方法。

点击复制链接与好友分享!回本站首页