java LinkedList源码分析

首先介绍一下java集合，集合接口Collection，子接口List，Set，Queue。

 

LinkedList就是子结构List的一个现实。并且它实现了其他接口，如Deque<E>-double ended queue双向队列，还有Cloneable, java.io.Serializable可克隆和可序列化结构，以及List下的子接口AbstractSequentialList顺序获取结构。

 

LinkedList的特点，它适用于需要频繁添加删除的集合，因为他的添加删除速度远高于ArrayList，并且顺序遍历的速度也高于ArrayList，但是它不适合随机获取数据。

以用thinking in java ：

--------------------------------------意思与上文相同，嫌眼晕的同学直接略过这段----------------------------------------

List：

 

Order is the most important feature of a L i s t ; it promises to maintain elements (interface) in a particular sequence. L i s t adds a number of methods to C o l l e c t i o n that allow insertion and removal of elements in the middle of a L i s t . (This is recommended only for a L i n k e d L i s t . ) A L i s t will produce a L i s t I t e r a t o r , and using this you can traverse the L i s t in both directions, as well as insert and remove elements in the middle of the list (again, recommended only for a L i n k e d L i s t ).

 

LinkedList：

 

Provides optimal sequential access, with inexpensive insertions and deletions from the middle of the list. Relatively slow for random access. (Use A r r a y L i s t instead.) Also has a d d F i r s t ( ) , a d d L a s t ( ) , g e t F i r s t ( ) , g e t L a s t ( ),r e m o v e F i r s t ( ) , and r e m o v e L a s t ( ) (which are not defined in any interfaces or base classes) to allow it to be used as a stack, a queue, and a dequeue.

 

--------------------------------------意思与上文相同，嫌眼晕的同学直接略过这段----------------------------------------

 

LinkedList的实现原理，LinkedList顾名思义，就是一个双向列表，每一个节点为Entry，数据推送完全就是链表的操作，所以他的插入，删除的速度快，但是用index查找就费劲了

 

LinkedList的关键源码分析：

 

 

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

 这个成员变量是LinkedList的关键，它在链表中没有实际数据意义，是链表的标示（要是难理解，就通俗一点理解成链表第一个无意义的元素），而且transient修饰，标示着他不会被序列化。header也可以当做队列末尾的元素，因为是双向列表，所以header.next末尾元素后边的元素就成了队首元素了，知道了这些，看一下下边的添加方法

 

 

 public void addFirst(E e) {
	addBefore(e, header.next);
    }

 public void addLast(E e) {
	addBefore(e, header);
    }

 以上是两个添加的函数，以这两个函数，讲解一下LinkedList是如何向集合推送元素的

 addFirst向队列头加元素，是将元素加到header.next-队首元素之前；

 addLast向队列未加元素，是将元素加到header之前；

 

下面看一下addBefore(E e,Entry<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;
    }

 Entry的数据结构是：

 

 private static class Entry<E> {
	E element; // 当前元素
	Entry<E> next; // 之后的元素，靠近last
	Entry<E> previous; // 之前的元素，靠近first

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }

 

明白LinkedList的数据结构和推送方式，那么其他的操作原理也就迎刃而解，讲解也就到这里，其他的代码留给有心人，愿大家技术和综合素质都共同进步

 

 

 

 

 

评论

1 楼 liuyes 2012-07-10  

子接口？Map？