package study.collection;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class TestDemo01
{
 public static void main(String[] args)
 {
  List list = new ArrayList();
  //ArrayList:底层实现时数组,线程不安全，效率高。所以，查询快。修改、插入、删除慢。
  //LinkedList:底层实现是链表,线程不安全，效率高。所以，查询慢。修改、插入、删除快。
  //Vector:线程安全的，效率低。
  
  list.add("aaa");
  list.add("aaa");
  list.add(new Date());
  list.add(new Dog());
  list.add(1234); //注意,list集合中只能添加引用类型，这里包装类的：自动装箱！
  list.remove(new String("aaa"));
  System.out.println(list.size());
  for(int i=0;i<list.size();i++){
   System.out.println(list.get(i)); 
  }
  
  list.set(3, new String("3333"));
  list.add(4, new String("3333"));
  
  System.out.println(list.isEmpty());
  list.remove(new Dog());  //hashcode和equals
  System.out.println(list.size());
  
  List list2 = new ArrayList();
  list2.add("bbb");
  list2.add("ccc");
  
  list.add(list2);
  
  //跟顺序的操作
  String str = (String) list.get(0);
  System.out.println(str); 
  list.set(1, "ababa");
  list.remove(0);
 }

}

class Dog
{
}

public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 private static final long serialVersionUID = 8683452581122892189L;

 /**
  * 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).
  *
  * @serial
  */
 private int size;

/**
 *构造一个具有指定容量的list
 */
public ArrayList(int initialCapacity) {
super();
 if (initialCapacity < 0)
  throw new IllegalArgumentException("Illegal Capacity: "+
           initialCapacity);
this.elementData = new Object[initialCapacity];
}

/**
 * 构造一个初始容量为10的list,也就说当我们经常采用new ArrayList()的时候,实际分配的大小就为10
 */
public ArrayList() {
this(10);
}

/**
 *构造一个包含指定元素的list，这些元素的是按照Collection的迭代器返回的顺序排列的
 */
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是因为toArray可能不一定是Object类型的,因此判断如果不是就进行了拷贝转换操作
if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
}

/**
  *添加一个元素
  */
 public boolean add(E e) 
 {
  // 进行扩容检查
  ensureCapacity(size + 1); // Increments modCount!!
  //将e增加至list的数据尾部，容量+1
  elementData[size++] = e;
  return true;
 }
 
 
  /**
  *在指定位置添加一个元素
  */
 public void add(int index, E element) {
   // 判断索引是否越界
 if (index > size || index < 0)
  throw new IndexOutOfBoundsException(
  "Index: "+index+", Size: "+size);
// 进行扩容检查
 ensureCapacity(size+1); // Increments modCount!!
  // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
 System.arraycopy(elementData, index, elementData, index + 1,
    size - index);
 // 将指定的index位置赋值为element
 elementData[index] = element;
  // list容量+1
 size++;
 }
 
 
 /**
  *增加一个集合元素
  */
 public boolean addAll(Collection<? extends E> c) {
  //将c转换为数组
 Object[] a = c.toArray();
  int numNew = a.length;
  //扩容检查
 ensureCapacity(size + numNew); // Increments modCount
 //将c添加至list的数据尾部
  System.arraycopy(a, 0, elementData, size, numNew);
   //更新当前容器大小
  size += numNew;
 return numNew != 0;
 }
 
 
 /**
  * 在指定位置，增加一个集合元素
  */
 public boolean addAll(int index, Collection<? extends E> c) {
 if (index > size || index < 0)
  throw new IndexOutOfBoundsException(
  "Index: " + index + ", Size: " + size);

 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacity(size + numNew); // Increments modCount

 // 计算需要移动的长度（index之后的元素个数）
 int numMoved = size - index;
  // 数组复制，空出第index到index+numNum的位置，即将数组index后的元素向右移动numNum个位置
 if (numMoved > 0)
  System.arraycopy(elementData, index, elementData, index + numNew,
     numMoved);
// 将要插入的集合元素复制到数组空出的位置中
  System.arraycopy(a, 0, elementData, index, numNew);
 size += numNew;
 return numNew != 0;
 }
 
 
 /**
  * 数组容量检查，不够时则进行扩容
  */
 public void ensureCapacity( int minCapacity) {
  modCount++;
  // 当前数组的长度
  int oldCapacity = elementData.length;
  // 最小需要的容量大于当前数组的长度则进行扩容
  if (minCapacity > oldCapacity) {
   Object oldData[] = elementData;
   // 新扩容的数组长度为旧容量的1.5倍+1
   int newCapacity = (oldCapacity * 3)/2 + 1;
   // 如果新扩容的数组长度还是比最小需要的容量小，则以最小需要的容量为长度进行扩容
   if (newCapacity < minCapacity)
    newCapacity = minCapacity;
   // minCapacity is usually close to size, so this is a win:
   // 进行数据拷贝，Arrays.copyOf底层实现是System.arrayCopy()
   elementData = Arrays.copyOf(elementData, newCapacity);
  }
 }

/**
  * 根据索引位置删除元素
  */
 public E remove(int index) {
  // 数组越界检查
  RangeCheck(index);
 
  modCount++;
  // 取出要删除位置的元素，供返回使用
  E oldValue = (E) elementData[index];
  // 计算数组要复制的数量
  int numMoved = size - index - 1;
  // 数组复制，就是将index之后的元素往前移动一个位置
  if (numMoved > 0)
   System. arraycopy(elementData, index+1, elementData, index,
       numMoved);
  // 将数组最后一个元素置空（因为删除了一个元素，然后index后面的元素都向前移动了，所以最后一个就没用了），好让gc尽快回收
  // 不要忘了size减一
  elementData[--size ] = null; // Let gc do its work
 
  return oldValue;
 }
 
 /**
  * 根据元素内容删除，只删除匹配的第一个
  */
 public boolean remove(Object o) {
  // 对要删除的元素进行null判断
  // 对数据元素进行遍历查找，知道找到第一个要删除的元素，删除后进行返回，如果要删除的元素正好是最后一个那就惨了，时间复杂度可达O(n) 。。。
  if (o == null) {
   for (int index = 0; index < size; index++)
    // null值要用==比较
    if (elementData [index] == null) {
     fastRemove(index);
     return true;
    }
  } else {
   for (int index = 0; index < size; index++)
    // 非null当然是用equals比较了
    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++;
  // 原理和之前的add一样，还是进行数组复制，将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
 }
 
 /**
  * 数组越界检查
  */
 private void RangeCheck(int index) {
  if (index >= size )
   throw new IndexOutOfBoundsException(
    "Index: "+index+", Size: " +size);
 }

/**
  * 将底层数组的容量调整为当前实际元素的大小，来释放空间。
  */
 public void trimToSize() {
  modCount++;
  // 当前数组的容量
  int oldCapacity = elementData .length;
  // 如果当前实际元素大小 小于 当前数组的容量，则进行缩容
  if (size < oldCapacity) {
   elementData = Arrays.copyOf( elementData, size );
  }

/**
  * 将指定位置的元素更新为新元素
  */
 public E set( int index, E element) {
  // 数组越界检查
  RangeCheck(index);
 
  // 取出要更新位置的元素，供返回使用
  E oldValue = (E) elementData[index];
  // 将该位置赋值为行的元素
  elementData[index] = element;
  // 返回旧元素
  return oldValue;
 }

/**
  * 查找指定位置上的元素
  */
 public E get( int index) {
  RangeCheck(index);
 
  return (E) elementData [index];
 }

/**
  * Returns <tt>true</tt> if this list contains the specified element.
  * More formally, returns <tt>true</tt> if and only if this list contains
  * at least one element <tt>e</tt> such that
  * <tt>(o==null ? e==null : o.equals(e))</tt>.
  *
  * @param o element whose presence in this list is to be tested
  * @return <tt> true</tt> if this list contains the specified element
  */
 public boolean contains(Object o) {
  return indexOf(o) >= 0;
 }
 
 /**
  * Returns the index of the first occurrence of the specified element
  * in this list, or -1 if this list does not contain the element.
  * More formally, returns the lowest index <tt>i</tt> such that
  * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
  * or -1 if there is no such index.
  */
 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;
 }
 
 /**
  * Returns the index of the last occurrence of the specified element
  * in this list, or -1 if this list does not contain the element.
  * More formally, returns the highest index <tt>i</tt> such that
  * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
  * or -1 if there is no such index.
  */
 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;
 }

/**
  * Returns the number of elements in this list.
  *
  * @return the number of elements in this list
  */
 public int size() {
  return size ;
 }
 
 /**
  * Returns <tt>true</tt> if this list contains no elements.
  *
  * @return <tt> true</tt> if this list contains no elements
  */
 public boolean isEmpty() {
  return size == 0;
 }

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
 System.out.println(synchronizedList.get(i));
}

private transient Object[] elementData;

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

private void writeObject(java.io.ObjectOutputStream s)
  throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
  // Write out array length
  s.writeInt(elementData.length);
 // Write out all elements in the proper order.
for (int i=0; i<size; i++)
   s.writeObject(elementData[i]);
 if (modCount != expectedModCount) {
   throw new ConcurrentModificationException();
 }
}

package study.collection;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class MyArrayList implements List {

 //底层用一个数组接收
 private Object[] elementData;
 
 //用于记录集合的元素个数
 private int size;
 
 /**
  * 无参数构造,默认为大小10
  */
 public MyArrayList() 
 {
  this(10);
 }
 
 /**
  * 初始化带容量的构造方法
  * @param cap
  */
 public MyArrayList(int cap)
 {
  super();
  if(cap < 0)
  {
   throw new IllegalArgumentException("Illegal cap: "+
     cap);
  }
  elementData = new Object[cap];
 }

 @Override
 public boolean add(Object e) {
  //1.添加之前确认集合中的大小是够,因此扩容判断
  ensureCapacity(size +1); //添加元素一个一个添加,因此size+1;
  //2.填充元素
  elementData[size++] = e;
  return true;
 }

 /**
  * 扩容判断,因为只要添加元素,就需要判断容器的大小是否满足
  * @param i
  */
 private void ensureCapacity(int minCapacity) {
  //扩容前,需要获取当前的数组元素的大小
  int oldCapacity = elementData.length;
  //只有当前的容量不满足,则扩容处理
  if(oldCapacity < minCapacity)
  {
   //新大小的比例,采用原来大小的1.5倍
   int newCapacity = (oldCapacity * 3)/2 + 1;
   //如果新算出来的大小不满足当前需要扩容的大小,则就以用户需要的为主,如果以满足则以算出来的最佳大小为主
   if(newCapacity < minCapacity)
   {
    newCapacity = minCapacity; 
   }
   //比例算好后,开始执行数组的拷贝操作
   Arrays.copyOf(elementData, newCapacity,Object[].class);
  }
 }

 @Override
 public void add(int index, Object element) {
  //添加指定位置,首先需要做的就是确保索引满足要求,如果要添加的索引超过了元素个数中的大小
  if(index > size || index < 0)
  {
   throw new IndexOutOfBoundsException(
     "Index: "+index+", Size: "+size);
  }
  //如果没有超过,那么就需要开始添加元素,这个时候同样需要判断扩容
  ensureCapacity(size +1); //添加元素一个一个添加,因此size+1;
  //接着需要做的事情是需要将原来位于index 位置的元素,向后面移动
  //首先判断,index的后面是否还有元素
  int modNum = size - index;
  if(modNum > 0)
  {
   System.arraycopy(elementData, index, elementData, index+1, size - index);
  }
  //如果没有元素或者已经拷贝完成,则直接在对应的索引处放置元素即可
  elementData[index] = element;
  //元素个数加+1
  size++;
 }

 @Override
 public boolean addAll(Collection c) {
  //添加集合元素,首先需要将集合转换为数组,计算出数组的大小
  Object[] a = c.toArray();
  //计算出需要的长度
  int numNew = a.length;
  //开始扩容判断
  ensureCapacity(size +numNew); //添加元素的个数为numNew
  //开始数组拷贝
  System.arraycopy(a, 0, elementData, size, numNew);
  size += numNew;
  return numNew != 0;
 }

 @Override
 public boolean addAll(int index, Collection c) {
  //首先索引的正确性
  if (index > size || index < 0)
   throw new IndexOutOfBoundsException(
   "Index: " + index + ", Size: " + size);
  //添加的元素集合转换为数组,计算要拷贝的长度,准备扩容
  Object[] a = c.toArray();
  int numNew = a.length;
  ensureCapacity(size + numNew); // Increments modCount
  //因为是指定位置扩容,因此需要判断下index后面是否有元素
  int numMoved = size - index;
  //如果大于0,说明要先空出位置来给a数组
  if(numMoved > 0)
  {
   System.arraycopy(elementData, index, elementData, index+1, size-index);
  }
  //空出为位置后,然后将集合的元素放到空出的位置上面
  System.arraycopy(a, 0, elementData,index, numNew);
  size += numNew;
  return numNew != 0;
 }

 @Override
 public void clear() {
  for (int i = 0; i < size; i++)
   elementData[i] = null;
  size = 0;
 }

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

 @Override
 public boolean containsAll(Collection c) {
  //迭代器暂不去实现
  return false;
 }

 @Override
 public Object get(int index) {
  //对于数组而言,根据索引获取元素非常简单,但需要先检查inde的合法性,避免越界
  RangeCheck(index);
  return elementData[index];
 }

 private void RangeCheck(int index) {
  if (index >= size)
   throw new IndexOutOfBoundsException(
   "Index: "+index+", Size: "+size);
  }
 
 @Override
 public int indexOf(Object o) {
  //循环遍历,找出元素,注意是equals比较
  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;
 }

 @Override
 public boolean isEmpty() {
  return size == 0;
 }

 @Override
 public Iterator iterator() {
  //涉及迭代器,暂不去关注
  return null;
 }

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

 @Override
 public ListIterator listIterator() {
  //涉及迭代器,暂不去关注
  return null;
 }

 @Override
 public ListIterator listIterator(int index) {
  //涉及迭代器,暂不去关注
  return null;
 }

 @Override
 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 void fastRemove(int index) {
  int numMoved = size - index - 1;
  if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
  elementData[--size] = null; 
  
 }

 @Override
 public Object remove(int index) {
  //合法性检查
  RangeCheck(index);
  //取出原来老的元素,以便返回
  Object oldValue = elementData[index];
  //需要开始拷贝数组,因为删除了索引处的元素,那么则需要向前移动元素
  //需要看后面有没有移动的元素,-1 是减去当前这个删除的元素
  int numMoved = size - index - 1;
  if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index,
      numMoved);//从index+1 开始拷贝到 index 处
  elementData[--size] = null; //元素个数减去一,同事最后一个位置置空,等待垃圾回收
  
  return oldValue;
 }

 @Override
 public boolean removeAll(Collection c) {
  ////涉及迭代器,暂不去关注
  return false;
 }

 @Override
 public boolean retainAll(Collection c) {
 ////涉及迭代器,暂不去关注
  return false;
 }

 @Override
 public Object set(int index, Object element) {
  RangeCheck(index);

  Object oldValue = elementData[index];
  elementData[index] = element;
  return oldValue;
 }

 @Override
 public int size() {
  return size;
 }

 @Override
 public List subList(int fromIndex, int toIndex) {
 ////涉及迭代器,暂不去关注
  return null;
 }

 @Override
 public Object[] toArray() {
   return Arrays.copyOf(elementData, size);
 }

 @Override
 public Object[] toArray(Object[] a) {
  if (a.length < size)
   // Make a new array of a's runtime type, but my contents:
   return Arrays.copyOf(elementData, size, a.getClass());
  System.arraycopy(elementData, 0, a, 0, size);
  if (a.length > size)
   a[size] = null;
  return a;
 }

 //测试
 public static void main(String[] args) 
 {
  MyArrayList list = new MyArrayList();
  list.add("333");
  list.add("444");
  list.add("5");
  list.add("344433");
  list.add("333");
  list.add("333");
  System.out.println(list.size()); 
//  System.out.println(list.get(6));
  list.remove("444");
  System.out.println(list.size());
 }
}