首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedList(1)

Java 容器源码分析之 LinkedList(1)

概览同 ArrayList 一样,LinkedList 也是对 List 接口的一种具体实现。不同的是,ArrayList 是基于数组来实现的,而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下:
1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList 继承自 AbstractSequentialList,实现了 List 接口,同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类,为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口,Deque 接口是一种双端队列,可以作为 FIFO 队列和 LIFO 队列(栈)来使用。LinkedList 支持所有元素,包括 null。
下面基于JDK 8 中的代码对LinkedList的实现加以分析。
底层结构LinkedList 基于双向链表进行实现,并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样,使用 modCount 来记录结构化修改的次数,并依此实现 fail-fast 机制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
*            (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
*            (last.next == null && last.item != null)
*/
transient Node<E> last;
双向链表的节点结构如下,分别用 prev 和 next 指向该节点的前驱和后继结点。
1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
返回列表