(转载请标明出处)
ArrayList 的实现：
1、MyArrayList将保持基础数组，数组的容量。以及存储在MyArrayList中的当前项数。
2、MyArrayList将提供一种机制以改变基础数组的容量。通过或者一个新数组，将老数组拷贝到新数组中改变数组的容量，允许虚拟机回收老数组。
3、MyArrayList将提供get和set的实现。
4、MyArrayList将提供基本的例程（Routine，系统对外提供的功能接口的集合），如size，isEmpty和clear，他们是典型的单行程序；还提供remove，以及两种不同版本的add。如果数组的大小和容量相同，那么这两个add例程将增加容量 。
5、MyArrayList将提供一个实现Iterator接口的类。这个类将存储迭代序列中的下一项的下标，并提供next，hasNext和和remove等方法的实现。MyArrayList的迭代器方法直接返回实现Iterator接口的该类的新构造的实例。
public class MyArrayList<T> implements Iterator<T> {
private static final int DEFAULT_CAPACITY = 10;
private int theSize;
private T[] theItems;
public MyArrayList() {
doClear();
}
public void clear(){
doClear();
}
private void doClear(){
theSize = 0;
ensureCapacity(DEFAULT_CAPACITY);
}
public int size(){
return theSize;
}
public void ensureCapacity(int newCapacity){
if(newCapacity < theSize){
return;
}
T[] old = theItems;
theItems = (T[]) new Object[newCapacity];
for(int i = 0; i < size(); i++){
theItems[i] = old[i];
}
}
public boolean add(T x){
add(size(),x);
return true;
}
public void add(int idx, T x){
if(theItems.length == size()){
ensureCapacity(size() * 2 + 1);
}
for(int i = theSize; i > idx; i--){
theItems[i] = theItems[i-1];
theItems[idx] = x;
}
theSize++;
}
public T remove(int idx){
T removeItem = theItems[idx];
for(int i = idx; i < size() - 1; i++){
theItems[i] = theItems[i + 1];
}
theSize--;
return removeItem;
}
public java.util.Iterator<T> iterator(){
return new ArrayListIterator<T>(this);
}
private static class ArrayListIterator<T> implements Iterator<T>{
private int current = 0;
private MyArrayList<T> theList;
public ArrayListIterator(MyArrayList<T> list) {
theList = list;
}
@Override
public boolean hasNext() {
return current<theList.size();
}
@Override
public T next() {
return theList.theItems[current++];
}
}
...
}
LinkedList 的实现：
1、MyLinkedList 类本身，包含到两端的链，表的大下以及一些方法。
2.、Node类，他可能是一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链，还有一些适当的构造方法。
3.、LinkedListIterator 类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。它提供了方法next，hasNext，remove的实现。
public class MyLinkedList<T> implements Iterator<T> {
private int theSize;
private int modCount = 0;
private Node<T> beginMarker;
private Node<T> endMarker;
private static class Node<T>{
public T data;
public Node<T> prev;
public Node<T> next;
public Node(T d, Node<T> p,Node<T> n){
data = d;
prev = p;
next = n;
}
}
public MyLinkedList(){
doClear();
}
public void clear(){
doClear();
}
private void doClear() {
beginMarker = new Node<T>(null,null,null);
endMarker = new Node<T>(null,beginMarker,null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
public int size(){
return theSize;
}
public boolean isEmpty(){
return size() == 0;
}
public boolean add(T x){
add(size(),x);
return true;
}
private Node<T> getNode(int idx){
return getNode(idx,0,size()-1);
}
private Node<T> getNode(int idx, int lower, int upper ){
Node<T> p;
if(idx < lower || idx > upper){
throw new IndexOutOfBoundsException();
}
if(idx < size()/2 ){
p=beginMarker.next;
for(int i= 0; i < idx; i++){
p = p.next;
}
}else{
p=endMarker;
for(int i = size();i > idx; i--){
p = p.prev;
}
}
return p;
}
public void add(int idx, T x){
addBefore(getNode(idx,0,size()),x);
}
public T get(int idx){
return getNode(idx).data;
}
public T set(int idx, T newVal){
Node<T> p = getNode(idx);
T oldVal = p.data;
p.data = newVal;
return oldVal;
}
public T remove(int idx){
return remove(getNode(idx));
}
private void addBefore(Node<T> p, T x){
Node<T> newNode = new Node<T>(x,p.prev,p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
private T remove(Node<T> p){
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++;
return p.data;
}
public java.util.Iterator<T> iterator(){
return new LinkedListIterator();
}
private class LinkedListIterator implements Iterator<T>{
private Node<T> current = beginMarker.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;
@Override
public boolean hasNext() {
return current != endMarker;
}
@Override
public T next() {
if(modCount != expectedModCount){
throw new java.util.ConcurrentModificationException();
}
if(!hasNext()){
throw new java.util.NoSuchElementException();
}
T nextItem = current.data;
okToRemove = true;
return nextItem;
}
public void remove(){
if(modCount != expectedModCount){
throw new java.util.ConcurrentModificationException();
}
if(!okToRemove){
throw new IllegalStateException();
}
MyLinkedList.this.remove(current.prev);
expectedModCount++;
okToRemove = false;
}
}
...
}
ArrayList 和 LinkedList 的区别：
结构上的区别：
对于处理一列数据项，ArrayList 的内部实现是基于内部数组Object[]，所以从概念上讲，它更像数组，但 LinkedList 的内部实现是基于一组连接的记录，所以，它更像一个链表结构；ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
性能上的区别：
查询：
二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的（访问链表中的某个元素时，就必须从链表的一端开始沿着连接方向一个一个元素地去查找，直到找到所需的元素为止）。对一个LinkedList做随机访问所消耗的时间与这个表的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。
增删：
1、若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。
2、若是批量插入或删除数据：
ArrayList 是基于数组实现的，而数组是一块连续的内存空间，当在表的前面或中间插入或删除元素时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销，当在表的后面插入或删除元素时，ArrayList和LinkedList数据量小时速度相差无几，但数据量较大时ArrayList的速度快。在末尾插入或删除数据，arraylist的速度比linkedlist的速度反而要快。注：其实在前方插入时，ArrayList可以使用后方插入，最后再使用Collections.reverse()方法反转，速度比LinkedList快。
LinkedList 插入或删除数据则只是简单的未这个元素分配一个记录，然后调整两个连接，在表的尾端插入数据与在任意位置插入数据是一样的，不会因为插入的位置靠前而导致插入的方法性能降低。
遍历列表：最简便的ForEach循环并没有很好的性能表现，综合性能不如普通的迭代器，而是用for循环通过随机访问遍历列表时，ArrayList表项很好，但是LinkedList的表现却无法让人接受，甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时，总会进行一次列表的遍历操作。性能非常差，应避免使用。
性能开销：
在LinkedList中有一个私有的内部类,
private static class Node<T>{
public T data;
public Node<T> prev;
public Node<T> next;
public Node(T d, Node<T> p,Node<T> n){
data = d;
prev = p;
next = n;
}
}
每个Node对象 reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将 有1000个链接在一起的Node对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为 它要存储这1000个Node对象的相关信息。
ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按 如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象， 那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分 配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。
总结：
1、在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
2、ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
3、LinkedList不 支持高效的随机元素访问。
4、ArrayList的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。
LinkedList的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。