Java源码分析 - LinkedList双向链表源码分析 | IT宅-帅旋的专业知识分享

LinkedList就传说中的双向链表了。是List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

查看LinkedList的构造函数：

/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}

这里的header变量的定义如下：

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

表示双向循环链表的头结点。其中的Entry定义了双向链表的结构：

private static class Entry {
E element;
Entry next;
Entry previous;

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

}

Entry中包括数据元素、前续结点和后续结点。

构造函数即是初始化一个只包含header头结点一个元素的双向链表。

可以得出：LinkedList实质上就是一个双向链表，并把header作为头结点。

查看LinkedList的add(E)方法：

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

add(E)方法主要指向了addBefore(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;
}

这个方法中传入的第二个参数entry为header头结点，表示把元素插入到header头结点之前。然后后两句分别表示设置前续结点的后续结点和后续结点的前续结点。以便连接成双向链表。

可以得出：LinkedList的add(E)方法把新结点插入到header头结点之前，即列表的结尾。

查看LinkedList的set(int, E)方法：

/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
Entry e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}

这个函数主要是设置某个索引位置的结点。首先调用了entry(int)方法：

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

这里首先判断需要设置的位置是否越界，如果越界则抛出异常。然后通过循环找到需要替换的结点。

接下来回到set(int ,E)函数，把旧的结点替换成新的结点，并返回旧的结点。

可以得出：set(int ,E)方法需要循环遍历链表，时间开销比较大。

查看LinkedList的push(E)方法：

/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
*

This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}

push(E)方法主要调用了addFirst(E)方法：

/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
addBefore(e, header.next);
}

这里继续调用addBefore(E, Entity)表示把新节点插入到header头结点之后。

可以得出：push(E)方法主要是把新节点插入到header头结点之后。

查看LinkedList的pop()方法：

/**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
*

This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
public E pop() {
return removeFirst();
}

这里继续调用了removeFirst()方法：

/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
return remove(header.next);
}

这里继续调用remove(Entry)方法：

/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
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;

}

在调用remove(Entry)方法时，传入了header的下一个结点。如果传入的下一个结点是header的话，表示此事链表中只有一个结点header，此时抛出异常。如果找到则删除该节点（注意这里双向链表删除结点时的步骤），并返回被删除的结点。

可以得出：pop()方法删除的是header头结点之后的结点，并返回被删除的结点。

★ LinkedList实质上就是一个双向链表，并把header作为头结点。 ★ LinkedList的add(E)方法把新结点插入到header头结点之前。 ★ set(int ,E)方法需要循环遍历链表，时间开销比较大。 ★ push(E)方法主要是把新节点插入到header结点之前 ★ pop()方法删除的是header头结点之后的结点，并返回被删除的结点。