首页 > 编程笔记

Java LinkedList的用法(非常详细)

LinkedList 常用来和 ArrayList 进行比较,事实上,这一类的问题都是顺序访问序列和随机访问序列的比较。LinkedList 的两个主要的特性为:顺序访问和写快读慢。下面,将通过对 JDK 源码的解析,来分析 LinkedList 的实现原理。

1. 父类和接口

1)java.util.AbstractSequentialList

该抽象类继承自 java.util.AbstractList,提供了顺序访问存储结构,只要类似于 LinkedList 这样的顺序访问 List,都可以继承该类。它提供了get\set\add\addAll\remove 等方法的迭代器方式的实现,前提是必须提供对迭代器接口 java.util.Iterator 的实现。

2)java.util.Deque

双向队列接口,继承自 java.util.Queue。LinkedList 为什么要实现该接口呢?因为 Queue 的特性是“先进先出”,也就是说,可以在尾部增加数据,头部获取数据。Deque 则可以同时在头尾处完成读写操作。在此基础上,LinekdList 还能操作头尾之间的任意结点,所以 LinkedList 在实现 Deque 的同时实现了 java.util.List。

3)java.lang.Cloneable、java.util.List 和 java.lang.Serialiable

这三个接口的讲解与 ArrayList 文章中一样,请转到 ArrayList 文中查看。

2. 成员变量和常量

这里重点介绍 3 个成员变量:

引申:可以注意到,所有成员变量都被transient修饰符修饰,在 ArrayList 文章中介绍过,该修饰符用于标记无需序列化的成员变量。也就是说,LinkedList 的所有成员都无需序列化。那么,结合之前讲解过的 Serialiable 接口的知识,可以得出结论,LinkedList 一定提供了 readObject 和 writeObject 方法,读者可以自行阅读LinkedList 源码查证。与 ArrayList 的实现原理类似。

常量:private static final long serialVersionUID=876323262645176354L;

这个常量提供给 Serialiable 序列化接口使用,在 ArrayList 文中里有详细讲解,不再赘述。

3. 构造方法

LinkedList 有两个重载的构造方法:
与 ArrayList 需要一个定长的数组不同,链表无需初始化任何对象,所以无参构造方法里没有做任何操作;Collection 形参的构造方法中,调用了addAll(Collection) 方法,该方法的具体实现将会在后面讲解。

4. Deque双向队列的实现

LinkedList 是一个在双向队列基础上搭建的双向链表,面试时候经常会问到其底层实现原理;因此,不仅要求掌握底层实现使用的数据结构,而且还需要掌握底层的具体实现原理。

双向链表的关键方法主要有以下几个:

这些方法都是通过操作成员变量 first 和 last 来实现的。first 和 last 的类型是私有类 Node<E>。实现很简洁,Java 代码如下所示:
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;
    }
}
熟悉双向链表数据结构的读者一定知道:“链表是由结点构成的,结点分为数据域和指针域,双向链表里的单个结点会保存上前驱结点和后继结点的指针(在 Java 语言中是引用)”。

这个 Node,是不是就符合和双向链表的结点概念?

构造方法中清晰体现了它们的初始化过程。这样就能很好地理解之前提及的四个方法是如何实现了。

比如,addLast(E),新建一个 Node 结点 n,数据域为方法形参,n.prev 设置为当前的 last,last.next 设置为 n,然后 last=n,即可完成需求。其他方法的实现原理类似。

5. getFirst/getLast/get方法实现

getFirstgetLast这两个方法分别用于取出头或尾的数据,在理解了 first 和 last 这两个 Node 之后,就很好理解了,直接返回 first.item 和 last.item 即可实现。

get(int) 方法则不一样,LinkedList 是顺序存储结构,要取到第 i 个数据,必须顺序遍历到 i 结点,所以这个方法的时间复杂度为 O(n)。具体实现时,在这个基础上进行了优化,实现代码如下所示:
if(index<(size>>1)){

    Node<E> x=first;
    for(int i=0;i<index; i++)
        x=x.next;
    return x;
}else{
    Node<E> x=last;
    for(int i=size-1;i>index;i--)
        x=x.prev;
    return x;
}
如果 index 小于 size(成员变量,代表链表长度)的一半,那么正序遍历,反之倒序遍历。虽然这依然是个 O(n) 级别的算法,但是遍历规模小了一倍。这里也体现了双向队列的应用。

6. set/add/addAll的实现

与 ArrayList 不同的是,LinkedList 的 add 方法比 set 更加迅速。add 的本质是在尾部增加一个结点,LinkedList 维护有成员变量 last,很快就能实现。而 set 则需要遍历查找到指定结点 i,并替换之。

addAll(Collection) 等价于调用 add(E) 多次。

7. removeFirst/removeLast/remove方法实现

removeFirst 与 removeLast 方法用于移除头尾结点并返回数据,remove 则是遍历到指定结点,然后移除它。都很好理解,这里需要注意的是它们都会调用的方法unlinkFirst/unlinkLast/unlink。而这三个方法都是用于解除 Node 指针域的指向关系,也就是把 Node.prev 或 Node.next 指向 null。

remove方法的删除操作只需要修改待删除结点后继结点的 pre 与前驱结点的 next 的指向,而不需要像 ArrayList 的 remove 操作一样移动数据,因此,删除操作有更高的效率。

8. 迭代器

ListIteractor<E>listIterator() 方法返回了一个内部类 ListItr,该类即是 LinkedList 迭代器的实现。由于 LinkedList 本身就是顺序结构,该迭代器除了记录 nextIndex 之外没有做特殊处理。此外 LinkedList 的迭代器也具备 fail-fast 特性。

优秀文章