我们知道List接口的两个常用实现类为ArrayList与LinkedList。

ArrayList底层采用数组实现，随机访问元素非常快，只需要常数时间c。但是对于删除和插入元素则比较耗时，因为它需要移动元素，需要线性时间，即O(N)。

而LinkedList底层采用链表实现，它的插入与删除操作非常快，只是更改两个指针的指向，所以 需要花常数时间c。但是随机访问则比较耗时，因为它需要从头节点或者尾节点进行依次地遍历，需要线性时间，即O(N)。

现在呢，我们就采用数组和链表分别实现自己MyArrayList与MyLinkedList。当然，这里只是实现最基础的功能。

1.MyArrayList

MyArrayList的默认大小为10。每次扩充数组的时候在原有的基础上乘以2再加1。加1是防止数组大小为0的情况。

package myList; import java.util.Iterator; import java.util.NoSuchElementException; public class MyArrayList<T> implements Iterable<T> { // 默认容量 private static final int DEFAULT_CAPACITY = 10; //实际大小 private int theSize; // 数组 private T[] theItems; public MyArrayList() { doClear(); } public int size(){ return theSize; } public boolean isEmpty(){ return size() == 0; } /** * 清除多余空间 */ public void trimToSize(){ ensureCapacity(size()); } /** * 根据索引获取元素 * @param index * @return */ public T get(int index){ if(index < 0 || index >= size()){ throw new IndexOutOfBoundsException(); } return theItems[index]; } /** * 设置新值，返回旧值 * @param index * @param newVal * @return */ public T set(int index, T newVal){ if(index < 0 || index >= size()){ throw new IndexOutOfBoundsException(); } T oldVal = theItems[index]; theItems[index] = newVal; return oldVal; } /** * 根据索引添加元素 * @param index * @param x */ public void add(int index, T x){ // 扩展容量 if(theItems.length == size()){ ensureCapacity(size() * 2 + 1); } // 向后移动 for(int i = theSize;i > index;i--){ theItems[i] = theItems[i-1]; } // 添加 theItems[index] = x; // 实际容量增加1 theSize++; } /** * 默认向最后添加 * @param x * @return */ public boolean add(T x){ add(size(), x); return true; } /** * 根据索引删除节点 * @param index * @return */ public T remove(int index){ T removedItem = theItems[index]; // 向前移动 for(int i = index;i<size()-1;i++){ theItems[i] = theItems[i+1]; } //实际容量减小1 theSize--; return removedItem; } private void doClear(){ theSize = 0; ensureCapacity(DEFAULT_CAPACITY); } /** * 数组扩展 * @param newCapacity */ 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]; } } /** * 迭代器方法 */ @Override public Iterator<T> iterator() { return new ArrayListIterator(); } /** * 迭代器。内部类 * @author Gavin * */ private class ArrayListIterator implements Iterator<T>{ private int current = 0; @Override public boolean hasNext() { return current < size(); } @Override public T next() { // 如果已经没有元素了 if(!hasNext()){ throw new NoSuchElementException(); } return theItems[current++]; } public void remove(){ MyArrayList.this.remove(--current); } } @Override public String toString() { StringBuilder line = new StringBuilder("["); for(int i = 0;i<size();i++){ line.append(theItems[i]); if(i != size()-1){ line.append(", "); }else{ line.append("]"); } } return line.toString(); } }

2.MyLinkedList

MyLinkedList采用双向链表实现。具有头节点和尾节点，头节点没有前驱结点，而尾节点没有后继节点。

package myList; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; public class MyLinkedList<T> implements Iterable<T>{ /** * 节点类 * @author Gavin * * @param <T> */ private static class Node<T>{ public T data; public Node<T> prev; public Node<T> next; public Node(T data,Node<T> prev, Node<T> next) { this.data = data; this.prev = prev; this.next = next; } } // 实际数据量 private int theSize = 0; // 该变量用于迭代时的判断 private int modCount = 0; // 头节点 private Node<T> beginMarker; // 尾节点 private Node<T> endMarker; public MyLinkedList(){ doClear(); } public void clear(){ doClear(); } public void doClear(){ beginMarker = new Node<T>(null, null, null); endMarker = new Node<T>(null, beginMarker, null); beginMarker.next = endMarker; theSize = 0; modCount ++; } /** * size()方法，返回实际的数据量大小 * @return */ public int size(){ return theSize; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return size() == 0; } /** * 私有方法。在节点p之前插入新节点，数据为x * @param p * @param x */ 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++; } /** * 私有方法。寻找Node，索引在lower和upper之间 * @param index * @param lower * @param upper * @return */ private Node<T> getNode(int index, int lower,int upper){ Node<T> p; if(index < lower || index > upper){ throw new IndexOutOfBoundsException(); } //如果是在前半段，就从前往后寻找 if(index < size()/2){ p = beginMarker.next; for(int i = 0;i<index;i++){ p = p.next; } } // 如果是在后半段，就从后往前寻找 else{ p = endMarker; for(int i = size();i>index;i--){ p = p.prev; } /*这里为什么不采用这种写法，是因为upper的值有可能为size() p = endMarker.prev; for(int i = size()-1;i>index;i--){ p = p.prev; } */ } return p; } /** * 私有方法。该方法限制index在0和size()-1之间 * @param index * @return */ private Node<T> getNode(int index){ return getNode(index, 0, size()-1); } /** * 根据index索引获取值 * @param index * @return */ public T get(int index){ return getNode(index).data; } /** * 设置某一个index索引位置上的值 * @param index * @param newVal * @return */ public T set(int index, T newVal){ Node<T> p = getNode(index); T oldVal = p.data; p.data = newVal; return oldVal; } /** * 这里的index可能为0到size()之间 * @param index * @param x */ public void add(int index,T x){ addBefore(getNode(index,0,size()), x); } /** * 该add方法直接调用add(index,x)，并且index为size() * @param x * @return */ public boolean add(T x){ add(size(), x); return true; } /** * 私有方法。删除一个节点Node * @param p * @return */ private T remove(Node<T> p){ p.prev.next = p.next; p.next.prev = p.prev; theSize--; modCount++; return p.data; } /** * 根据索引删除节点 * @param index * @return */ public T remove(int index){ return remove(getNode(index)); } /** * 迭代器方法 */ @Override public Iterator<T> iterator() { return new LinkedListIterator(); } /** * 迭代器。内部类 * @author Gavin * */ private class LinkedListIterator implements Iterator<T>{ private Node<T> current = beginMarker.next; //此变量用于限制遍历期间，MyLinkedList不能修改 private int expectedModCount = modCount; //此变量用于限制不能多次remove private boolean okToRemove = false; @Override public boolean hasNext() { return current != endMarker; } @Override public T next() { if(modCount != expectedModCount){ throw new ConcurrentModificationException(); } if(!hasNext()){ throw new NoSuchElementException(); } T nextItem = current.data; current = current.next; okToRemove = true; return nextItem; } public void remove(){ if(modCount != expectedModCount){ throw new ConcurrentModificationException(); } if(!okToRemove){ throw new IllegalStateException(); } MyLinkedList.this.remove(current.prev); expectedModCount++; okToRemove = false; } } @Override public String toString() { StringBuilder line = new StringBuilder("["); Node<T> p = beginMarker.next; while(p!=endMarker.prev){ line.append(p.data); line.append(", "); p = p.next; } line.append(p.data); line.append("]"); return line.toString(); } }