zy19982004--容器学习八：LinkedList源码分析

一.概述

1. LinkedList继承Deque，所以LinkedList的插入删除操作遵循先进性出FIFO。
2. LinkedList继承Deque，所以Linkedist实现了Deque的操作，比喻offer peek pollfirst/last等操作。其实这些操作也就是建立在getFirst getLast addFirst addLast removeFirst removeLast这几个操作上的。

 

二 .成员变量

//头节点
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

 

三 .节点Entry对象

//节点
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;
    }
}

 

 四.构造函数

//初始化
public LinkedList() {
    header.next = header.previous = header;
}

 

五 .存数据

//默认插入到最后
public boolean add(E e) {
    addBefore(e, header);
    return true;
}

//把元素e插入最前
public void addFirst(E e) {
    //等价于把元素e插入到原第一个节点header.next的前面
    addBefore(e, header.next);
}

//把元素e插入最后
public void addLast(E e) {
    //等价于把元素e插入到header的前面，因为是双链表
    addBefore(e, header);
}

//在指定位置插入元素e，原index处和以后的元素往后移
public void add(int index, E element) {
    //index == size,把元素e插入到header的前面
    //其他情况把元素e插入entry(index)的前面
    addBefore(element, (index == size ? header : entry(index)));
}


//把元素e插入到指定entry的前面
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;
}

 

五 .取数据

//取指定位置的元素
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;
    //在链表中取值时，需要遍历整个链表，
    //即使优化成遍历半个链表，相对于ArrayList的随机访问，还是慢的
    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;
}

//取第一个节点处的元素
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;
}

//和ArrayList一样的算法，只是ArrayList遍历数组，LinkedList遍历链表
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;
}

 

 六.删数据

//remove默认删除第一个位置的元素
public E remove() {
    return removeFirst();
}

public E removeFirst() {
    return remove(header.next);
}

public E removeLast() {
    return remove(header.previous);
}

//和ArrayList一样的算法，只是ArrayList遍历数组，LinkedList遍历链表
public boolean remove(Object o) {
    if (o == null) {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (e.element == null) {
                //转换成remove(Entry)
                remove(e);
                return true;
            }
        }
    } else {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (o.equals(e.element)) {
                //转换成remove(Entry)
                remove(e);
                return true;
            }
        }
    }
    return false;
}

//转换成remove(Entry)
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;
}

 

七 .遍历

private class ListItr implements ListIterator<E> {
        private Entry<E> lastReturned = header;
        private Entry<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

                //初始化的时候next = header.next;
        ListItr(int index) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: " + index
                        + ", Size: " + size);
            if (index < (size >> 1)) {
                next = header.next;
                for (nextIndex = 0; nextIndex < index; nextIndex++)
                    next = next.next;
            } else {
                next = header;
                for (nextIndex = size; nextIndex > index; nextIndex--)
                    next = next.previous;
            }
        }

        public boolean hasNext() {
            return nextIndex != size;
        }
                //遍历的时候next = next.next，按照从头往后遍历，也就是FIFO的顺序
        public E next() {
            checkForComodification();
            if (nextIndex == size)
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.element;
        }


    }