LinkedList

LinkedList源码的一点笔记：

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list

1，底层存储实现方式：

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;//list的数量

Entry是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，构造方法

public LinkedList(){
    //将header的前一个节点和后一个节点都指向自身  
    header.next = header.previous = header;
}

3，新增

private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry(e, entry, entry.previous);//临时，创建一个要新增的Entry
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

图片来源：https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list

4，删除

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;
    //置为null，确保及时回收 to let gc do its work
    e.next = e.previous = null;
    e.element = null;
    size--;
    modCount++;
    return result;
}

如图：

　　

 5，查找

public E get(int index) {
    return entry(index).element;
}
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;
}