数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

class Array {
   arrays[40];
   int size;
}

/**
    * 
       ArrayList的元素存储在其中的数组缓冲区。
            ArrayList的容量是这个数组缓冲区的长度。当添加第一个元素时，任何具有elementData == EMPTY_ELEMENTDATA的空ArrayList将展开为DEFAULT_CAPACITY。
私有包允许从java.util.Collections访问。
    */
   transient Object[] elementData;

   /**
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
   private int size;


       /**
    * Default initial capacity.
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * Shared empty array instance used for empty instances.
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

// 定义容量 也就是数组的大小
public ArrayList(int initialCapacity) {
       super();
       // 若传入的值小于0 抛出异常
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
       //初始化数组
       this.elementData = new Object[initialCapacity];
   }

   /**
    * 默认构造函数 初始化一个空的数组
    */
   public ArrayList() {
       super();
       // private static final Object[] EMPTY_ELEMENTDATA = {};
       this.elementData = EMPTY_ELEMENTDATA;
   }

   /**
    * 构造一个含有元素的列表
    *
    * @param c the collection whose elements are to be placed into this list
    * @throws NullPointerException if the specified collection is null
    */
   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);
   }

public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //进行完数组的自增长后才向数组中添加元素
       elementData[size++] = e;
       return true;
   }

   private void ensureCapacityInternal(int minCapacity) {
       //如果elementData 是个空数组 没有元素
       if (elementData == EMPTY_ELEMENTDATA) {
           //minCapacity 取DEFAULT_CAPACITY 和 minCapacity 的最大值 
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
   }
   // 确保显式容量
   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;

       // overflow-conscious code minCapacity 必须大于数组的长度 才可自增长
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }

    // 实现数组的自增长
    private void grow(int minCapacity) {
       // overflow-conscious code 添加元素之前的数组长度
       int oldCapacity = elementData.length;
       // 新的数组长度
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       // 若新的数组长度 小于 最小增长的数组长度,则 newCapacity = minCapacity
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       //数组长度达到最大值    
       if (newCapacity - MAX_ARRAY_SIZE > 0)
       //数组的最大长度
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       // 对数组进行copy 扩大数组的长度
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

      private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }

public void add(int index, E element) {
       if (index > size || index < 0)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

       ensureCapacityInternal(size + 1);  // Increments modCount!!
       // 将插入元素 之后的数组后移一位 其实就是对数组的copy
           src:源数组； 
           srcPos:源数组要复制的起始位置；
           dest:目的数组；  
           destPos:目的数组放置的起始位置；    l
           ength:复制的长度。
       System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
      // 向数组中添加元素
       elementData[index] = element;
       size++;
   }

public E get(int index) {
 if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

       return (E) elementData[index];
   }

public E set(int index, E element) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

       E oldValue = (E) elementData[index];
       elementData[index] = element;
       return oldValue;
   }

```
public E remove(int index) {
       // 删除元素的位置必须大于或等于数组的大小
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

       modCount++;
       // 获取要删除的元素
       E oldValue = (E) elementData[index];
       //数据移动
       int numMoved = size - index - 1;
       // 若删除的不是最后一个
       if (numMoved > 0)
           //对数组进行copy 
           src:源数组； 
           srcPos:源数组要复制的起始位置；
           dest:目的数组；  
           destPos:目的数组放置的起始位置；    l
           ength:复制的长度。
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       // size - 1 前一位置空                     
       elementData[--size] = null; // clear to let GC do its work
       // 返回删除的元素
       return oldValue;
   }
```

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

   /*
    * Private remove method that skips bounds checking and does not
    * return the value removed.
    */
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
   }
```

```
class Node{
   Object data;
   Node next;
}
```