LinkedList源码分析

LinkedList适用于添加、删除比较频繁，随机访问不多的场合。
LinkedList扩展了AbstractSequentialList抽象类（提供了部分List接口的实现），实现了List,Deque,Cloneable,java.io.Serializable接口。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
}

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;
	}
}

1. 构造方法

   head元素不代表任何具体内容。刚初始化的时候，LinkedList为空，header与它的前一个和后一个元素相同，都是它本身：

    public LinkedList() {
        header.next = header.previous = header;
    }

2. add, addBefore方法

public boolean add(E e) {
	addBefore(e, header);
	return true;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
}

a. 首先实例化这个节点，它的下个节点是entry，前个节点是entry.previous
b. 然后把前个节点的下个节点指针指向新节点，后个节点的前个节点指针指向新节点
c. 大小加1，修改次数加1。修改次数用在侦测并发修改方面。

3. remove(Entry<E> e)方法

remove(Object o)方法包含两个部分：首先搜索到该元素（对o为null的时候做了优化），然后调用remove(E e)。

public boolean remove(Object o) {
	if (o==null) {
		for (Entry<E> e = header.next; e != header; e = e.next) {
			if (e.element==null) {
				remove(e);
				return true;
			}
		}
	} else {
		for (Entry<E> e = header.next; e != header; e = e.next) {
			if (o.equals(e.element)) {
				remove(e);
				return true;
			}
		}
	}
	return false;
}

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;
}

a. header是不可以被删除的
b. 先把需要删除的节点的值保存，用于返回值
c. 把前后节点直接关联起来
d. 该节点清空
e. 大小减1，修改次数加1

4. addAll方法

public boolean addAll(int index, Collection<? extends E> c) {
	if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index+
											", Size: "+size);
	Object[] a = c.toArray();
	int numNew = a.length;
	if (numNew==0)
		return false;
	modCount++;

	Entry<E> successor = (index==size ? header : entry(index));
	Entry<E> predecessor = successor.previous;
	for (int i=0; i<numNew; i++) {
		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
		predecessor.next = e;
		predecessor = e;
	}
	successor.previous = predecessor;

	size += numNew;
	return true;
}

a. 找到index位置的节点和前节点。
b. 在它们之间插入一组节点，设置好前后关系。
c. 链表的长度增加。

5. getFirst, getLast方法

public E getFirst() {
	if (size==0)
	    throw new NoSuchElementException();

	return header.next.element;
}

public E getLast()  {
	if (size==0)
		throw new NoSuchElementException();

	return header.previous.element;
}

获取头尾节点的速度会很快，因为离header很近。

6. contains和indexOf方法

public boolean contains(Object o) {
	return indexOf(o) != -1;
}

public int indexOf(Object o) {
	int index = 0;
	if (o==null) {
		for (Entry e = header.next; e != header; e = e.next) {
			if (e.element==null)
				return index;
			index++;
		}
	} else {
		for (Entry e = header.next; e != header; e = e.next) {
			if (o.equals(e.element))
				return index;
			index++;
		}
	}
	return -1;
}

如果o为null，单独去比较(e.element == null)，提高性能。

7. clear方法

public void clear() {
	Entry<E> e = header.next;
	while (e != header) {
		Entry<E> next = e.next; // record the next entry
		e.next = e.previous = null;
		e.element = null;
		e = next; // iterate through
	}
	header.next = header.previous = header;
	size = 0;
	modCount++;
}

a. 遍历所有的节点，清空它们的前后引用和值。
b. header节点的前后节点指向它本身。
c. 长度置为0，修改次数自增。

8. 索引访问
很明显，索引访问需要通过链表结构，速度上没有ArrayList的索引访问快。

    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;
    }

    // 拿到index位置上的元素，赋新的值，返回旧的值
    public E set(int index, E element) {
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
    }

    // 判断添加的位置：如果在末尾，就是在header前插入；否则在index元素前插入
    public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }

    // 删除index位置的元素
    public E remove(int index) {
        return remove(entry(index));
    }

    // 从后向前搜索，返回第一个符合的元素的位置
    public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }

9. 队列操作

    // 获取第一个元素，如果队列为空，返回null
    public E peek() {
        if (size==0)
            return null;
        return getFirst();
    }

    // 获取第一个元素，如果队列为空，抛NoSuchElementException异常
    public E element() {
        return getFirst();
    }

    // 删除并返回第一个元素，如果队列为空，返回null
    public E poll() {
        if (size==0)
            return null;
        return removeFirst();
    }

    // 删除并返回第一个元素，如果队列为空，抛NoSuchElementException异常
    public E remove() {
        return removeFirst();
    }

    // 在队列尾部添加一个元素，LinkedList没有大小限制，一般不会返回false
    public boolean offer(E e) {
        return add(e);
    }

10. 双向队列操作

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    public E peekFirst() {
        if (size==0)
            return null;
        return getFirst();
    }

    public E peekLast() {
        if (size==0)
            return null;
        return getLast();
    }

    public E pollFirst() {
        if (size==0)
            return null;
        return removeFirst();
    }

    public E pollLast() {
        if (size==0)
            return null;
        return removeLast();
    }

    public void push(E e) {
        addFirst(e);
    }

    public E pop() {
        return removeFirst();
    }

    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    public boolean removeLastOccurrence(Object o) {
        if (o==null) {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }