几种常见的数据结构的JAVA实现

线性表的实现有很多种，如数组线性表，单链表，双链表，环链表，带头节点和不带头节点的链表。每种的结构的操作效率和存储效率都不一样，一般用数组实现的线性表的插入，删除效率低（O(n)），但访问节点的效率高（O(1)），而链式线性表的插入，删除效率高（O(1)），访问效率低（O(n)），同时多了指向下一个节点或者上一个节点的指针或引用，存储空间有所浪费。具体应用时需要根据不同的需求，选用恰当的线性表，这需要建立在对各种线性表实现方式的了解基础上。
如果只是单纯地实现线性表的数据结构，还是比较容易的。因为线性表和队列，栈一样是线性的数据结构，和非线性的数据结构比起来，从理解上和实现上要容易得多。但是如果想要程序变得更加通用，则要考虑很多其他的因素，如与其他集合类的合并，删除，并发，迭代，序列化等，因而程序的实现就变得复杂得多。JDK里LinkedList的实现就充分考虑了很多如上面所说的通用性方面的因素。
看JDK的源码是件非常惬意的事情，大师们考虑很多我们平时没有考虑到的细节，这些细节的考虑必须要有足够的编程基础和实战经验，对基础和经验都不是足够的我来说看着这些代码的细节就像站在春风吹过的麦田里一样舒畅。
本文的LinkedList的实现是一边看JDK源码一遍实现的，只实现了List<E>接口，并没有实现Deque<E>, Cloneable, java.io.Serializable，因此不具备足够的通用性，只是为了更深刻地理解它，并掌握JDK实现该数据结构的技巧。
下面是原代码：
package utility.structure;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class LinkedList<E> implements List<E>{
private int size = 0;
private int modCount = 0;
private Entry head = new Entry(null);

public LinkedList() {

head.next = head;

head.previous = head;
}
public boolean add(E e) {

addBefore(e, head);

return true;
}
public void add(int index, E element) {

addBefore(element,(index == size ? head :entry(index)));

}
public boolean addAll(Collection<? extends E> c) {

for (E e : c)
add(e);

return true;
}
pu