LinkedList源码解析（Jdk6）

Java的LinkedList是基于双向链表实现的List集合类。它的特点有：

1.没有容量限制。

2.添加，删除元素比较快；检索元素较慢（较ArrayList）。

3.可能实现为队列，栈

4.线程不安全

下面来看其源码实现：

1.类定义

 

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

LinkedList继承自AbstractSequentialList，AbstractSequentialList继承AbstractList的大部分功能，实现List，Deque接口，Deque定义了双端队列的一些个方法。可克隆，可被序列化。

2.属性定义

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

size：集合的大小。

Entry：LinkedList存储数据的地方，就是靠它实现双向链接，每new一个新的ArrayList实例，就会创建一个空的header，它表示链表的头，来看它的实现：

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

a.首先它支持泛型

b.属性element用来存储我们实际的值，可以是普通类型，也可以引用类型。

c.属性next和previous实现双向链接的下一个节点，上一个节点

3.构造方法,来看我们new LinkedList()都干了什么

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

这是无参构造方法，因为上面讲了，每次new都会创建一个空的header节点，那构造方法做的就是它的下一个节点和上一个节点，这里都是指向自身，从而形成一个闭环。

4.add()，我们看添加元素，它是怎么实现的

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

它调用了addBefore（）方法，在之前插入，那就是每次在header之前插入了，看它实现：

a.new一个新的Entry节点，element为我们添加的元素对象，next节点为header，上一个节点为entry.previous＝header.previous=header，即下一个节点和上一个节点都为header。

b.newEntry.previous.next=header.next=newEntry，即将header的下一个节点设置为新创建的Entry节点。

c.newEntry.next.previous=header.previous = newEntry，即将header的上一个节点设置为新创建的Entry节点。这时新插入的newEntry节点便和header形成一个新的闭环。LinkedList就是这样来插入新的元素。

d.size++，LinkedList大小加1。

e.modCount++，修改次数加1。

转一张图过来，其实我自己也用笔画出来了。

理解这个add()方法，能自己画出这张图，LinkedList的实现原理就搞明白了,后面都是它的应用。

5.get()方法

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

它调用entry（），size >> 1这个是右位运算，意思是size除以2^1，左移就是乘以2^1，所以这里检索的方法是用被检索的索引值与LinkedList集体大小的一半比较，小于它，从前面开始找，大于它，则从后面开始找。所以它的检索效率没有ArrayList高，但是它插入，删除高效啊。

6.remove()

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

a.首先找到这个节点，然后调用remove()方法，

b.把它的上一个节点的next指向它的下一个节点，下一个节点的previous指向它的上一个节点，有点绕，但是好理解， 

c.把它自己的下一个节点和上一个节点指向都设置为null,

d.把它的值设置为null

e.修改次数加1，并返回该元素的值。

其它方法还有很多，但理解上面这些，LinkedList就是没问题了

据其它网友的总结：

1.对LinkedList的遍历采用新特性的for循环，效率较高，

for (Integer integ:list) 
    ; 

其次是迭代，千万不要用随机访问，那是ArrayList的强项。

 

参考：

http://www.cnblogs.com/hzmark/archive/2012/12/25/LinkedList.html

http://www.cnblogs.com/skywang12345/p/3308807.html