LinkedList源码了解

LinkedList源码理解
LinkedList源码0.首先这个类中的两个变量

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

下面的这个size就不用说了，是大小，现在先着重看看 Entry<E> header，

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

???

?

??? 就是一个链表，有父节点和子节点，父子节点都是一个对象的引用。

??? 还有就是这个类是LinkedList的内部类，所以变量自然能再外部直接调用了。

??? 这个对象在声明的时候已经new了一个对象，所以这里可以直接使用里面的方法
??? 节点的子节点和父节点都自己。

//无参构造    public LinkedList() {        header.next = header.previous = header;    }

??

??? 这里是无参构造后header的示意图，父子节点都指向自己。只是最初的header对象。

??? 这里所指向的“一个对象”在初始化中为null。并且没有改变过。

//有参构造 ? public LinkedList(Collection<? extends E> c) {??? ??? ??? //这一句可不能忘，对头节点的初始化很重要。??? ??? ??? this();??? ??? ??? addAll(c);??? }

?? 在有了添加元素的操作后，entry的指针会指向不同地方。

??? 这个方法主要是讲原来

??? 返回是否成功

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

//在第几个位置添加     public void add(int index, E element) {         //如果在最后的位置添加，直接和上面的添加一样，如果不是，则        addBefore(element, (index==size ? header : entry(index)));    }        private Entry<E> entry(int index) {        if (index < 0 || index >= size)            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);        //取得头结点        Entry<E> e = header;        //循环节点，从头节点开始循环，这个处理很聪明，先计算index的大小，小于一半的话正向遍历，大于一半的话反向遍历。        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 void addFirst(E e) {       //只是在header的下一个开始添加，不多看了。addBefore(e, header.next);    }

?

  public void addLast(E e) {     //这个和add方法一样，所以普通的添加方法也是添加到最后的位置。     addBefore(e, header);    }

??? 这个是完整的情况，添加，删除都会断开相应的next和previous。同时注意header内部的element不会存储元素。他所指向的对象是null，在前面也说过。

? 主要是讲要删除元素的Entry调整父子节点就可实现删除。

public E remove() {        return removeFirst();    }        public E removeFirst() {            return remove(header.next);    }        private E remove(Entry<E> e) {     //不能删除头节点                if (e == header)                    throw new NoSuchElementException();                //这个是用来返回的              E result = e.element;              //父节点的子节点指向e的子节点。                e.previous.next = e.next;                //子节点的父节点指向e的父节点                e.next.previous = e.previous;                //将e设为空。                    e.next = e.previous = null;                    e.element = null;              //大小--                size--;                modCount++;             return result;    }

?删除元素。这里面的匹配和indexof方法很像。在indexof里面讲。

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

?

?

//还是对equals比较，都是正向循环。没什么新意，循环到头指针后结束。     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;    }

? ? 还有一些找第几个元素，返回元素数量，找到头元素，找都最后元素。