1 public class ArrayList<E> extends AbstractList<E> 2 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
LinkedList的定义：
1 public class LinkedList<E> 2 extends AbstractSequentialList<E> 3 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
从定义上可以看到ArrayList和LinkedList都实现了List接口，ok看下List接口的定义：
1 public interface List<E> extends Collection<E> { 2 int size(); 3 boolean isEmpty(); 4 boolean contains(Object o); 5 Iterator<E> iterator(); 6 Object[] toArray(); 7 <T> T[] toArray(T[] a); 8 boolean add(E e); 9 boolean remove(Object o); 10 boolean containsAll(Collection<?> c); 11 boolean addAll(Collection<? extends E> c); 12 boolean addAll( int index, Collection<? extends E> c); 13 boolean removeAll(Collection<?> c); 14 boolean retainAll(Collection<?> c); 15 void clear(); 16 boolean equals(Object o); 17 int hashCode(); 18 E get( int index); 19 E set( int index, E element); 20 void add( int index, E element); 21 E remove( int index); 22 int indexOf(Object o); 23 int lastIndexOf(Object o); 24 ListIterator<E> listIterator(); 25 ListIterator<E> listIterator( int index); 26 List<E> subList( int fromIndex, int toIndex); 27 }
可以看到List中对容器的各种操作add、remove、set、get、size等进行了统一定义，同时List实现了Collection接口，继续看下Collection接口的定义（先不关心Iterator）：
1 public interface Collection<E> extends Iterable<E> { 2 int size(); 3 boolean isEmpty(); 4 boolean contains(Object o); 5 Iterator<E> iterator(); 6 Object[] toArray(); 7 <T> T[] toArray(T[] a); 8 boolean add(E e); 9 boolean remove(Object o); 10 boolean containsAll(Collection<?> c); 11 boolean addAll(Collection<? extends E> c); 12 boolean removeAll(Collection<?> c); 13 boolean retainAll(Collection<?> c); 14 void clear(); 15 boolean equals(Object o); 16 int hashCode(); 17 }
有了这两个接口，对于ArrayList和LinkeList的操作是不是就可以这么写了呢？
1 Collection<String> collection = new ArrayList<String>(); 2 collection.add("hello"); 3 collection.add("java"); 4 collection.remove("hello");
对于ArrayList的实现不满意，ok换成LinkedList实现，
1 Collection<String> collection = new LinkedList<String>(); 2 collection.add("hello"); 3 collection.add("java"); 4 collection.remove("hello");
对于用户来说，add、remove等操作是没有任何影响的，好了，到这里了解了统一接口，面向接口编程的好处，接下来在思考另外一个问题，怎么给容器提供一种遍历方式。
1 /** Implementing this interface allows an object to be the target of 2 * the "foreach" statement. 3 * @since 1.5 4 */ 5 public interface Iterable<T> { 6 7 /** 8 * Returns an iterator over a set of elements of type T. 9 * 10 * @return an Iterator. 11 */ 12 Iterator<T> iterator(); 13 }
英文注释说，实现iterable接口的类可以使用“foreach”操作，然后并要求实现Iterator<T> iterator()方法，该方法返回一个Iterator接口对象，来看下Iterator接口，
1 public interface Iterator<E> { 2 // 是否还有元素 3 boolean hasNext(); 4 // 下一个元素 5 E next(); 6 // 将迭代器返回的元素删除 7 void remove(); 8 }
Iterator接口一共有三个方法，通过这三个方法就可以实现通用遍历了，ok，我们来试一下。
1 Collection<String> collection = new ArrayList<String>(); 2 collection.add("hello"); 3 collection.add("java"); 4 5 Iterator<String> iterator = collection.iterator(); 6 while (iterator.hasNext()) { 7 System. out.println(iterator.next()); 8 }
1 public interface MyIterator { 2 Object next(); 3 boolean hasNext(); 4 }
容器统一接口：
1 public interface MyCollection { 2 void add(Object o); 3 int size(); 4 MyIterator iterator(); 5 }
容器实现类和Iterator实现类（Iterator实现类为容器内部类）：
1 public class MyArrayList implements MyCollection { 2 3 private Object[] data ; 4 private int size; 5 6 public MyArrayList() { 7 data = new Object[10]; 8 } 9 10 public void add(Object o) { 11 if (size == data. length) { 12 Object[] newData = new Object[data .length * 2]; 13 System. arraycopy(data, 0, newData, 0, data.length ); 14 data = newData; 15 } 16 data[size ] = o; 17 size++; 18 } 19 20 public int size() { 21 return size ; 22 } 23 24 @Override 25 public MyIterator iterator() { 26 return new Itr(); 27 } 28 29 private class Itr implements MyIterator { 30 private int index = 0; 31 32 @Override 33 public boolean hasNext() { 34 if (index >= size) { 35 return false; 36 } else { 37 return true; 38 } 39 } 40 41 @Override 42 public Object next() { 43 Object o = data[index ]; 44 index++; 45 return o; 46 } 47 48 } 49 }
应用一下：
1 public class Test { 2 3 public static void main(String[] args) { 4 MyCollection c = new MyArrayList(); 5 c.add( "t"); 6 c.add( "s"); 7 c.add( "t"); 8 c.add( "d"); 9 10 System. out.println(c.size()); 11 12 MyIterator itr = c.iterator(); 13 while (itr.hasNext()) { 14 System. out.println(itr.next()); 15 } 16 } 17 18 }
看看结果：
4
t
s
t
d
没问题，很容易就实现了对不对，当然这里只是简单模拟，没有过多的追求效率和优雅的设计。
1 public Iterator<E> iterator() { 2 return new Itr(); 3 }
和自己实现的一样，采用内部类实现 Iterator接口。
1 private class Itr implements Iterator<E> { 2 // 将要next返回元素的索引 3 int cursor = 0; 4 // 当前返回的元素的索引，初始值-1 5 int lastRet = -1; 6 7 /** 8 * The modCount value that the iterator believes that the backing 9 * List should have. If this expectation is violated, the iterator 10 * has detected concurrent modification. 11 */ 12 int expectedModCount = modCount; 13 14 public boolean hasNext() { 15 // 由于cursor是将要返回元素的索引，也就是下一个元素的索引，和size比较是否相等，也就是判断是否已经next到最后一个元素 16 return cursor != size(); 17 } 18 19 public E next() { 20 checkForComodification(); 21 try { 22 // 根据下一个元素索引取出对应元素 23 E next = get( cursor); 24 // 更新lastRet为当前元素的索引，cursor加1 25 lastRet = cursor ++; 26 // 返回元素 27 return next; 28 } catch (IndexOutOfBoundsException e) { 29 checkForComodification(); 30 throw new NoSuchElementException(); 31 } 32 } 33 34 public void remove() { 35 // remove前必须先next一下，先取得当前元素 36 if (lastRet == -1) 37 throw new IllegalStateException(); 38 checkForComodification(); 39 40 try { 41 AbstractList. this.remove(lastRet ); 42 // 确保lastRet比cursor小、理论上永远lastRet比cursor小1 43 if (lastRet < cursor) 44 // 由于删除了一个元素cursor回退1 45 cursor--; 46 // 重置为-1 47 lastRet = -1; 48 expectedModCount = modCount ; 49 } catch (IndexOutOfBoundsException e) { 50 throw new ConcurrentModificationException(); 51 } 52 } 53 54 final void checkForComodification() { 55 if (modCount != expectedModCount) 56 throw new ConcurrentModificationException(); 57 } 58 }
1 public Iterator<E> iterator() { 2 return listIterator(); 3 }
AbstractList的实现：
1 public ListIterator<E> listIterator() { 2 return listIterator(0); 3 } 4 public ListIterator<E> listIterator(final int index) { 5 if (index<0 || index>size()) 6 throw new IndexOutOfBoundsException( "Index: "+index); 7 8 return new ListItr(index); 9 }
看一下ListItr实现：
1 private class ListItr implements ListIterator<E> { 2 // 最后一次返回的节点，默认位header节点 3 private Entry<E> lastReturned = header; 4 // 将要返回的节点 5 private Entry<E> next ; 6 // 将要返回的节点index索引 7 private int nextIndex; 8 private int expectedModCount = modCount; 9 10 ListItr( int index) { 11 // 索引越界检查 12 if (index < 0 || index > size) 13 throw new IndexOutOfBoundsException( "Index: "+index+ 14 ", Size: "+size ); 15 // 简单二分，判断遍历的方向 16 if (index < (size >> 1)) { 17 // 取得index位置对应的节点 18 next = header .next; 19 for (nextIndex =0; nextIndex<index; nextIndex++) 20 next = next .next; 21 } else { 22 next = header ; 23 for (nextIndex =size; nextIndex>index; nextIndex --) 24 next = next .previous; 25 } 26 } 27 28 public boolean hasNext() { 29 // 根据下一个节点index是否等于size，判断是否有下一个节点 30 return nextIndex != size; 31 } 32 33 public E next() { 34 checkForComodification(); 35 // 遍历完成 36 if (nextIndex == size) 37 throw new NoSuchElementException(); 38 39 // 赋值最近一次返回的节点 40 lastReturned = next ; 41 // 赋值下一次要返回的节点（next后移） 42 next = next .next; 43 // 将要返回的节点index索引+1 44 nextIndex++; 45 return lastReturned .element; 46 } 47 48 public boolean hasPrevious() { 49 return nextIndex != 0; 50 } 51 52 // 返回上一个节点（双向循环链表嘛、可以两个方向遍历） 53 public E previous() { 54 if (nextIndex == 0) 55 throw new NoSuchElementException(); 56 57 lastReturned = next = next. previous; 58 nextIndex--; 59 checkForComodification(); 60 return lastReturned .element; 61 } 62 63 public int nextIndex() { 64 return nextIndex ; 65 } 66 67 public int previousIndex() { 68 return nextIndex -1; 69 } 70 71 public void remove() { 72 checkForComodification(); 73 // 取出当前返回节点的下一个节点 74 Entry<E> lastNext = lastReturned.next ; 75 try { 76 LinkedList. this.remove(lastReturned ); 77 } catch (NoSuchElementException e) { 78 throw new IllegalStateException(); 79 } 80 // 确认下次要返回的节点不是当前节点，如果是则修正 81 if (next ==lastReturned) 82 next = lastNext; 83 else 84 // 由于删除了一个节点，下次要返回的节点索引-1 85 nextIndex--; 86 // 重置lastReturned为header节点 87 lastReturned = header ; 88 expectedModCount++; 89 } 90 91 public void set(E e) { 92 if (lastReturned == header) 93 throw new IllegalStateException(); 94 checkForComodification(); 95 lastReturned.element = e; 96 } 97 98 public void add(E e) { 99 checkForComodification(); 100 lastReturned = header ; 101 addBefore(e, next); 102 nextIndex++; 103 expectedModCount++; 104 } 105 106 final void checkForComodification() { 107 if (modCount != expectedModCount) 108 throw new ConcurrentModificationException(); 109 } 110 }