LinkedList源码浅析 - JAVA

LinkedList源码简单分析

LinkedList的声明

view plaincopy to clipboardprint public class LinkedList
extends AbstractSequentialList
implements List, Deque/*这是双端队列接口，这个接口扩展了Queue接口，提供了更多的方法，比如push,pop等*/, Cloneable, java.io.Serializable
public class LinkedList
extends AbstractSequentialList
implements List, Deque/*这是双端队列接口，这个接口扩展了Queue接口，提供了更多的方法，比如push,pop等*/, Cloneable, java.io.Serializable

所以LinkedList可以被用作Stack,Queue和Deque

来看一下链表结点的定义

view plaincopy to clipboardprint private static class Entry {
E element;
Entry next;
Entry previous; //由此可以看出LinkedList是一个双向链表

Entry(E element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
private static class Entry {
E element;
Entry next;
Entry previous; //由此可以看出LinkedList是一个双向链表

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

LinkedList中声明了下面两个实例变量：

//头结点，起标记作用，并不记录元素

private transient Entry header = new Entry(null, null, null);

//链表的大小，即链表中元素的个数

private transient int size = 0;

我们可以看到这两个就是都被声明成了transient，所以在序列化的过程中会忽略它们，但是LinkedList提供的序列化方法writeObject(java.io.ObjectOutputStream s)中却序列化了size，并且将除header之外的所有结点都写到序列化文件中了，那为什么要把size声明成transient呢，不解。。求解释。。

几个重要的方法：

view plaincopy to clipboardprint /**
* Returns the indexed entry.
根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry 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;
}
/**
* Returns the indexed entry.
根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry 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;
}

view plaincopy to clipboardprint /**
*将元素e添加到entry结点之前
*/
private Entry addBefore(E e, Entry entry) {
Entry newEntry = new Entry(e, entry, entry.previous);
newEntry.previous.next = newEntry; //将新结点与前后结点相连接
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

/**
*删除给定的结点e
*/
private E remove(Entry 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;
}

/**
*从表头开始遍历，返回此元素在表中的第一个位置
*/
public int indexOf(Object o) {
int index = 0;
if (o==null) { //如果传入的元素是null，则不能调用 eqauls方法进行比较
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)

LinkedList源码浅析 (一)