LinkedList源码分析

LinkedList的源码分析

      LinkedList是一个双向循环链表，既然是双向的列表，就不能像ArrayList一样交给一个Object数组来存储。LinkedList需要定义新的数据类型来解决链表的问题，他就是Entry，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;
	}
    }

 

 

  element：  当前节点的值

  previous： 指向前一个节点

  next：       指向后一个节点

几个重要的方法：

add（E e)方法

 

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

 

 

再看addBefore

 

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

 

 

上面这方法代码没几行，但是理解还是结合我们在学校学的数据结构把思路给缕一缕，直接看图说话：

0：调用add(E e)时，相当于把元素插在最后一个位置

1、2：相当于初始化一个newEntry对象

Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);

 

因为这是一个循环双向队列，最后一个元素的next始终指向header，同时header的previous始终指向最后一个元素，那么就刚好对应

1:newEntry.next=head,

2:newEntry.previous=header.previous

这两步还仅仅是newEntry的初始化过程，给newEntry的属性赋值而已，header和未插入之前的最后那个元素的关系并没有断开。

这里假设把原来最后那个元素叫tail

 3：就是把tail.next指向newEntry，相应的代码就是：

 

newEntry.previous.next = newEntry;

 

 4：header的preview需要指向新的最后一个元素newEntry:

 

newEntry.next.previous = newEntry;

 

这样整个插入过程基本上就完成了。add(E e)的时间复杂度o(1)，大家猜猜如果要是在中间某个位置插入又是怎么实现的呢？

add(int index E e)方法

 

 public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }

 

 

为了找到插入点需要，如果不是插在最后一个位置的话，需要调用entry(index)

 

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

 

看到没有，从header开始找，并不是一味的header.next.next.....,而是当index小于size/2是往next方向找，小于size/2时逆向查找，这样它的复杂度就是o(n/2)，这点和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(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;
    }

 

 因为LinkedList是由Entry维护，Entry即我们所说的节点，为了删除对象o时，就不能去找到由o构成的Entry对象，移除Entry对象时，刚好与add相反，删除它的操作很简单，只要把前一个节点的next属性指下一个节点（e.previous.next = e.next;），然后下一个节点的previous指向当前节点的前一个节点（e.next.previous = e.previous;），最后把当前节点的next，previous、element置为null，以便GC回收（e.next = e.previous = null; e.element = null;）删除操作就完成了，我们从中可以看出这个方法的时间复杂度仅为O(1),所以他的操作是非常快的。但是为了找到Entry,他要从header节点开始找，直到找到那个值与传入的参数值相等,我们可以看出他的时间复杂度就不是我们普遍认为的O(1)了，而变成了O(n)。

再来看看下面这个方法

 

 public E remove(int index) {
        return remove(entry(index));
    }

 

 这是删除某个指定位置元素的方法，与add(int index E e)对应

 

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

 

总结：相对于ArrayList来说，普遍认为对数据的修改频繁时最好使用LinkedList，但是我们发现针对LinkedList要移除某个元素时，发现其效率也并不见得非常的高，因为其中还涉及到一个查询的操作。,所以，要是性能要求很高的话，可以自己实现满足要求的LinkedList，而不用jdk提供的通用的java.util.LinkedList。