LinkedList的源码分析

LinkedList的源码分析

一、LinkedList概况：

      LinkedList属于一个双向循环的链表，其内部是用一个Entry来维护的

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

      在Entry中就包含链表的三个属性，previous、next、element

 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：指向当前节点的后一个节点

二、接下来重点分析一下方法：

由

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

 引出

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

 可以看出remove(Entry<E> e)是一个私有方法，所有我们是没法直接去调用此方法的，该方法就是为LinkedList本身服务的，因为LinkedList是由Entry维 护，Entry即我们所说的节点，删除它的操作很简单，只要把当前节点的前一个节点的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),也就是说删除LinkedList中第一个元素和最后一个元素的时间复杂的 仅为O(1),所以他的操作是非常快的。

三、但是如果我们是想删除某个具体的对象时，它又是怎么实现的呢？看源码

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

我们发现这方法的内部又调用了一个前面已经分析过的remove(Entry<E> e）方法， 在这个方法中却多了一个for循环，他要从一个节点开始找，直到找到那个值于传入的参数值相等,我们可以看出他的时间复杂度就不是我们普遍认为的O(1) 了，而变成了O(n),之所以这样是LinkedList作为一个通用性的链表结构，由Entry去维护该数据结构，而不是拿我们直接保存在 LinkedList的值，相当于做了一层包装，所以你要删除某个值，你还得去找到那个对应的Entry对象。

四、再来看看下面这个方法：

 public E remove(int index) {
        return remove(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;
    }

 我们很惊奇的发现，哇，原来删除某个位置的元素还是这样实现的，为了找到index位置的 Entry元素，它根据index元素与LinkedList大小的一半(size>>1)做了次比较，如果比size/2小,它就由前往后 找，如果比size/2大，它就从后往前找，并不是我们所想的一味的又前往后找，这样一来，除去比较所消耗的时间，他的时间复杂度为O(n/2)

五、相对来说添加的操作就没那么复杂了

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

 这方法的意思是说，把e对应的节点添加到entry的前面，首先构造newEntry对象，即新节点，然后是新节点的前一个节点的next指向当前的新节点，当前新节点的下一个元素的previous也指向新节点.

 

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

 

 

写的很好啊，学习了 。。。怎么没人回复

删除某个位置的元素 用的是二分法查找吗?

这和二分查找不一样，感兴趣的话可以读读Arrays.binarySearch和Collections.binarySearch方法

呵呵，不知道该怎么说？貌似都知道，就是不会去真的去写，LZ真的很细心。
如果可以的话Entry<KEY,VALUE>与泛型之间的联系，以及早期JDK版本的做一个比较。

 

1. 如果涉及按值查找再删除，LinkedList显然比ArrayList快。因为两者都需要一次顺序查找，而ArrayList还需要移动元素。

2. ArrayList的优势是按index访问（随机访问），并主要在尾部增删的场合

3. 如果需要兼顾随机访问和增删的性能，可以考虑使用java.util.LinkedHashMap。不过它只能按key访问，而不是按index访问。

4. 画这种图可以用graphviz，很方便的。 （www.graphviz.org)

 

例如你输入

 

digraph structs {
    rankdir = LR
    node [shape=record]
    {
    	s1 [label="<p> previous|<e> head |<n> next"]
   	s2 [label="<p> previous|<e> middle |<n> next"]
    	s3 [label="<p> previous|<e> tail |<n> next"]
    
    	s1:n -> s2:e
    	s2:n -> s3:e
    	
    	s1:p -> s3:e
    	s2:p -> s1:e
    	s3:p -> s2:e
    	
    	s3:n -> s1:e
    }
}

  就能得到

补充的很周到，感谢！！！特别是画图工具

有时候那么好的文章好多人投隐藏啊 新手啊。。。这个文章这么新手的却都投良。。想不同

每个人的评判标准不一样，仁者见仁，智者见智。觉得这篇文章对自己有帮助就可以投个良好

楼主写得不错,好学的态度也很好
有时间把HashMap(内部实现,Set、Entry、KeySet、Values的关系等),以及concurrent包下各种容器,都看一看