一、java.util.ArrayList的数据结构为数组结构，为可序列化类型、实现了List接口,类声明方式：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
JDK8中该类在初始化时的容量为0，在add时会将容量扩充到10，当容量较少时会进行扩容。
1.扩容逻辑
代码如下：
初始化：
private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //构造函数 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //添加数据 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //扩容逻辑 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); 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: elementData = Arrays.copyOf(elementData, newCapacity); }
可以看到，在方法ensureCapacityInternal中，选取当前size+1与默认容量10中较大的值minCapaccity，如果该值比当前容量小，则不进行扩容；如果已经大于当前容量，则进行扩容：根据当前容量oldCapacity，扩展oldCapacity的一半，并保证可以满足当前使用，否则直接使用minCapaccity的值。
2.equals
代码如下：
public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof List)) return false; ListIterator<E> e1 = listIterator(); ListIterator<?> e2 = ((List<?>) o).listIterator(); while (e1.hasNext() && e2.hasNext()) { E o1 = e1.next(); Object o2 = e2.next(); if (!(o1==null ? o2==null : o1.equals(o2))) return false; } return !(e1.hasNext() || e2.hasNext()); }
比较两个list对象中的所有元素的顺序、取值是否完全一致。
3.contains和indexOf
代码如下：
//查看是否包含某元素 public boolean contains(Object o) { return indexOf(o) >= 0; } //查看某元素在list中的第一个的位置 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; } //查看某元素在list中的最后一个的位置 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; }
indexOf（Object o）的主要作用为：遍历arrayList中的所有元素，并返回该元素所在list中的第一个位置。如果未找到则返回-1。
4.removeRange删除list中某一范围的元素
protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }
该方法主要是从toIndex的位置开始到最后一位的数据复制到fromIndex起始的位置，然后将最后几位的位置数据设置为null。
其中System.arraycopy为系统方法，为数据拷贝的方法。elementDate为需要复制的原始数组；toIndex为原始数组的起始位置；elementDate为目标数组；fromIndex为目标数组的起始位置；numMoved为拷贝的数组数据的长度。
二、java.util.LinkedList
结构：该list为链表结构，包含first节点、last节点、size值。first节点前置节点为null，last节点后继节点为null，size初始值为0。
节点结构：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
即每个节点有个一个前置节点、有一个后继节点、有一个节点值。
1.add方法
public boolean add(E e) { linkLast(e); return true; }
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
linkLast方法：首先声明两个节点，一个节点l指向list最后一个节点（last）；另一个节点newNode指向一个新节点，该节点前置节点指向l，后继节点指向null，节点值为想要插入的值。
然后，如果list为空，则list的首节点first指向newNode节点；如果list不为空，则l指向newNode，并且将list最后一个节点的后续指向newNode。并且将newNode赋值给last节点。
最后，将size加1，modCount加1。
具体modCount作用：
主要是为了检查是否有多个线程同时改变list的内容，可以查看博文的讲解：http://www.cnblogs.com/dolphin0520/p/3933551.html
2.contains和indexOf
public boolean contains(Object o) { return indexOf(o) != -1; }
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
indexOf主要是查找list中的某节点值：
1）遍历list值。从first节点开始到节点不为null为止（last节点的后继节点为null），每次遍历节点的后继节点。
2）如果查找null节点，则直接使用“==”进行比较；如果查找非null节点，则使用equals（）方法。
3）返回值为该节点在list中的位置值index，从0开始，每遍历一个节点加1，指导找到匹配的值位置，并返回index。如果未找到则返回-1；
contains方法主要是查看list中是否包含某个节点：
通过indexOf方法查找节点，找到（即indexOf方法结果不为-1）则返回逻辑判断结果true（boolean类型），否则返回false。
3.remove为删除第一个找到的节点值
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
remove通过遍历list，从first到last节点如果查找到匹配节点，则调用unlink方法进行释放当前节点。
具体方法如下：
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
该方法主要功能为：
1）如果该节点前置节点为空，则该节点为first首节点，即将first首节点指向该节点的后续节点；
如果前置节点不为空，则将前置节点的后续指向该节点的后续节点，并将该节点的前置节点置为空，相当于断掉该节点前面的链条。
2）继续判断后继节点，如果为空，则该节点为last尾节点，即将last为节点指向该节点的前置节点；
如果后继节点不为空，则将后续节点的前置节点指向该节点的前置节点，并将该节点的后继节点值为空，相当于断掉该节点后面的链条。
3）该节点的前后链条已经与list断掉，但是需要释放掉该节点的空间，并且需要将list的长度size减1，修改modCount的值加1。
4）返回值为节点的内容。
java.util.ArrayList与LinkedList两种类型的区别：
1.ArrayList结构为数组结构，LinkedList为链表结构。
2.ArrayList由于根据index位数查找字段时可以直接取出数组的位置，而LinkedList则需要遍历到指定位置才可以取出节点值，因此对于根据位置查找频繁的项目建议使用ArrayList。但是根据值查询两者相差不大。
3.ArrayList删除时需要将后面所有位数的数据全部前移，而LinkedList删除某一节点只需要释放该节点。因此ArrayList速度较慢，对于由频繁插入和删除操作的需求，建议使用LinkedList。
但是由于linkedList在删除或者插入时需要定位到该数据，因此也会对效率有影响，因此具体问题也许要综合分析。
样例如下：
List<String> sList = new ArrayList<String>();for (int i = 0; i < 10000000; i++) {sList.add(String.valueOf(i));}long begina1 = System.currentTimeMillis();System.out.println("根据位置查询arrayList的值==" + sList.get(999999));long enda1 = System.currentTimeMillis();System.out.println("根据位置查询arrayList时间==" + (enda1 - begina1));long begina2 = System.currentTimeMillis();System.out.println("根据值查询arrayList的位置==" + sList.indexOf("999999"));long enda2 = System.currentTimeMillis();System.out.println("根据值查询arrayList时间==" + (enda2 - begina2));long begina3 = System.currentTimeMillis();sList.remove(0);long enda3 = System.currentTimeMillis();System.out.println("删除arrayList中数据使用的时间==" + (enda3 - begina3));List<String> linkList = new LinkedList<String>();for (int i = 0; i < 10000000; i++) {linkList.add(String.valueOf(i));}long beginb1 = System.currentTimeMillis();System.out.println("根据位置查询linkList的值==" + linkList.get(999999));long endb1 = System.currentTimeMillis();System.out.println("根据位置查询linkList的时间==" + (endb1 - beginb1));long beginb2 = System.currentTimeMillis();System.out.println("根据值查询linkList的值==" + linkList.indexOf("999999"));long endb2 = System.currentTimeMillis();System.out.println("根据值查询linkList的时间==" + (endb2 - beginb2));long beginb3 = System.currentTimeMillis();linkList.remove(0);long endb3 = System.currentTimeMillis();System.out.println("删除linkList中数据使用的时间==" + (endb3 - beginb3));
结果为，数字为毫秒数：
根据位置查询arrayList的值==999999根据位置查询arrayList时间==0根据值查询arrayList的位置==999999根据值查询arrayList时间==16删除arrayList中数据使用的时间==6根据位置查询linkList的值==999999根据位置查询linkList的时间==12根据值查询linkList的值==999999根据值查询linkList的时间==17删除linkList中数据使用的时间==0