transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; /** * Constructs an empty list. */ public LinkedList() { }
LinkedList的属性和构造方法
//添加的方法
public boolean add(E e) { linkLast(e); return true; }
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
linkLast的原理是：新添加元素的pre是原集合中的最后一个元素，（next）下一个元素是null，新添加进来的元素就成了最后一个元素。如果原集合中没有元素，则新添加的元素既是first,也是last.
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
linkFirst原理：新添加进来的元素成了新集合的第一个元素，新添加元素的pre为null,新添加元素的next为原集合的fist。如果原集合没有元素，那么第一个添加进来的元素既是first也是last。
Node类是LinkedList的私有内部类
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; } }
取值：先检查查找的索引是否大于等于0且小于等于集合的长度（size）
public E get(int index) { checkElementIndex(index); return node(index).item; }
/** * 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; } }
有两种情况的取值，如果查找的索引在集合长度的二分之一前，从前往后查找，否则从后往前查找。如从第一个元素开始，一直first.next.next.next...直到查找的索引为止。从后往前是last.pre.pre.pre....
原文：http://www.cnblogs.com/hjy9420/p/5034271.html