基于链表实现的集合在查找元素的速度上肯定比不上基于数组实现的集合，但是链表实现的最大优点在于，频繁的操作节点时速度就比较快了，例如删除一个节点，不需要向数组一样，对数组中元素进行拷贝。
先看一下AbstractSequencialList抽象类：
public abstract class AbstractSequentialList<E> extends AbstractList<E> { protected AbstractSequentialList() { }
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Bulk Operations
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.iterator();
while (e2.hasNext()) {
e1.add(e2.next());
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Iterators
public Iterator<E> iterator() {
return listIterator();
}
public abstract ListIterator<E> listIterator(int index);
}
如上类实现了含有索引参数（index）的一些方法，这些方法都是随机访问List的。LinkedList底层的实现是双向链表，所以可以通过双端顺序快速定位到链表节点。，如果要自己实现一个链表集合的话，最好继承这个抽象类，这样就不用费工夫自己来实现这么多的方法了。
LinkedList就是子结构List的一个现实。如下：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
它实现了其他接口，如Deque<E> 双向队列，还有Cloneable,java.io.Serializable可克隆和可序列化结构，以及List下的子接口AbstractSequentialList顺序获取结构。
下面来研究LinkedList类，这个类是基于双向链表实现的，所以可以在两端进行操作，这就需要有两个指向首尾节点的指针：
transient int size = 0; // 节点个数 transient Node<E> first; // 指向链表第一个节点 transient Node<E> last; // 指向链表最后一个节点 // 链表节点 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; } }
通过一个内部的私有类表示链表的Node结点，这个节点中的两个指针会为查找等操作提供便利，如查找链表中第index个位置处理的节点，源代码如下：
//Returns the (non-null) Node at the specified element index. // 双向链表，从最近的一头进行查找，加快查找的速度 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // 位置离头节点比较近 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 位置离尾节点比较近 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
1、创建LinkedList
看一下构造函数：
public LinkedList() { } // 默认空的构造函数 public LinkedList(Collection<? extends E> c) {// 有参数的构造函数 this(); addAll(c); }
其实任何直接或间接实现Collection接口的集合类都会提供两个构造函数：一个是默认的无参构造函数；另外一个就是以Collection参数做为集合的构造函数。有了第二个构造函数，可以将其他集合中的元素转换为链表集合中的元素。
2、迭代元素
由于双向链表的结构特殊，所以在迭代查找元素时，比ArrayList等基于数组结构的实现要费时费事一些，如下：
private class ListItr implements ListIterator<E> { private Node<E> lastReturned = null; // 一个临时的辅助变量 private Node<E> next; // 下一个节点 private int nextIndex; // 下一个节点的索引值 private int expectedModCount = modCount; ListItr(int index) { // 构造函数中对重要变量进行初始化 // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }// end ListItr
如果要对链表操作很熟悉，如上的代码非常简单，这里就不多做介绍了。如上利用hasNext()和next()方法可以顺序遍历节点，如果要利用这两个方法进行逆序遍历，可以使用如果代码来实现：
private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }
下面来举一个例子，如下：
LinkedList<String> list=new LinkedList<>(); list.add("a"); list.add("b"); list.add("c"); Iterator sx=list.listIterator(); while(sx.hasNext()){ System.out.print(sx.next()+" "); } System.out.println(); Iterator nx=list.descendingIterator(); while(nx.hasNext()){ System.out.print(nx.next()+" "); }输出的结果如下：
a b c
c b a
3、栈操作
下面当然就是对双向链表进行节点操作了，包括删除、查询链表首尾节点、查找某个特定节点等操作，方法很简单，有兴趣的读者可以自己下去研究。顺便提醒一下，数组可以用来实现栈操作，链表同样可以，在这个类中提供了pop()、push()等方法，如果你要进行栈操作的话，同样调用这些方法可以实现。只要在双链表的一端操作就可以了。
4、克隆对象
由于这个类还实现了Conable接口，所以实现了clone()方法，但是这个方法只实现了浅克隆，源代码如下：
private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } public Object clone() { // 只进行浅克隆 LinkedList<E> clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node<E> x = first; x != null; x = x.next) clone.add(x.item); return clone; }
所以如果你操作的节点中item是基本类型的话，修改时两者不会影响。如果item中是引用类型的话，两者的值是会相互影响的，这时候就必须使用自己克隆的方法了。举个例子：
LinkedList<Number> list=new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);for(Number i:list){System.out.println(i);// 1 2 3 4 }LinkedList<Number> l=(LinkedList<Number>) list.clone();l.add(5);l.set(2, 33);for(Number i:l){System.out.println(i);// 1 2 33 4 5}
修改l的值list中的值不会受到影响，再举个例子：
String[] x={"a","c"};String[] y={"m","n"};LinkedList<String[]> list=new LinkedList<>();list.add(x);list.add(y);LinkedList<String[]> l=(LinkedList<String[]>) list.clone();l.get(1)[1]="ttttt";System.out.println(list.get(1)[1]);
这时候打印出的值为ttt，也就是修改克隆后的引用值，原值也会被修改，这时候就要用深度克隆了。如果细心且阅读过源代码的人就会发现，有些方法克隆链表元素的方法其实和clone方法是一样的，如下：
public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
public <T> T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }
所以在使用的时候要特别注意。
ArrayList 是由一个数组实现的，相当于动态数组。由于数组可以通过索引快速定位，所以随机访问效率高。由于插入和删除时，有时候会造成数组的整体移动，所以随机插入、随机删除效率很低。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率却很高。
根据不同的适用场景来选择使用不同的集合，会使得程序效率更高效。