1、LinkedList元素在内部存储的实现，节点定义即指向前一元素的指针，后一元素的指针，当前元素的值。
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
2、创建一个空链表。默认有个头指针header。
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
3、在链表的末端添加一个元素。
/**
* Appends the specified element to the end of this list.
*
* @param o element to be appended to this list.
* @return <tt>true</tt> (as per the general contract of
* <tt>Collection.add</tt>).
*/
public boolean add(E o) {
addBefore(o, header);
return true;
}
private Entry<E> addBefore(E o, Entry<E> e) {
Entry<E> newEntry = new Entry<E>(o, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
4、删除链表中指定位置的元素。
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to removed.
* @return the element previously at the specified position.
*
* @throws IndexOutOfBoundsException if the specified index is out of
* range (<tt>index < 0 || index >= size()</tt>).
*/
public E remove(int index) {
return remove(entry(index));
}
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
/**
* Return the indexed entry.
*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}