coding……
但行好事 莫问前程

Java编程拾遗『容器——LinkedList』

上篇文章讲了List的数组实现——ArrayList,在最后讲了ArrayList的一些特性,比如支持随机访问,插入和删除效率偏低。本篇文章来看一下List基于链表的实现LinkedList的一些细节,每一种实现都是有它特定的使用场景的,而LinkedList就可以解决ArrayList上述插入删除效率低下的问题。

1. 使用规则

LinkedList是基于双向链表实现的,声明如下:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

跟ArrayList类似,LinkedList实现了List、Cloneable、Serializable接口,继承的抽象类AbstractSequentialList跟ArrayList继承的抽象类AbstractList是相同的作用,也是实现和接口分离的思想,在AbstractSequentialList中实现一些通用方法,方便扩展。另外需要注意的是,LinkedList实现了Deque接口,可以按照队列、栈和双端队列的方式进行操作。下面简单介绍一下方法的使用规则:

1.1 构造方法

S.N. 方法 说明
1 public LinkedList() 默认构造函数
2 public LinkedList(Collection<? extends E> c) 通过一个集合对象构建LinkedList

1.2 List接口

AbstractSequentialList继承了AbstractList类,LinkedList继承AbstractSequentialList抽象类跟ArrayList继承AbstractList抽象类是一个道理,方便扩展。上图中LinkedList直接或间接实现的接口,LinkedList都是可以使用的,比如可以通过迭代器遍历LinkedList。List接口的方法之前都有详细介绍,这里再简单提一下,如下:

S.N. 方法 说明
1 boolean add(E e) 向list中末尾添加元素,如果调用改变了集合返回true
2 void add(int index, E element) 在listindex位置起添加一个元素
3 boolean addAll(Collection<?> c) 向list中末尾添加多个元素,如果调用改变了集合返回true
4 boolean addAll(int index, Collection<? extends E> c) 向list index位置添加多个元素,,如果调用改变了集合返回true
5 void clear() 清空list元素
6 boolean contains(Object o) 判断list中是否存在一个与o相等的元素,存在返回true
7 boolean containsAll(Collection<?> c) 判断list是否包含集合c中的所有元素,包含返回true
8 boolean equals(Object o) equals方法
9 E get(int index) 获取list index位置的元素
10 int hashCode() hashCode方法
11 int indexOf(Object o) 获取o在list中第一次出现的index,如果不存在返-1
12 boolean isEmpty() 判断list是否为空,为空返ture
13 Iterator<E> iterator() 返回list的Iterator迭代器
14 int lastIndexOf(Object o) 返回o在list中的最后一次出现的index
15 ListIterator<E> listIterator() 返回list index 0开始的ListIterator双向迭代器
16 ListIterator<E> listIterator(int index) 返回list index位置开始的ListIterator双向迭代器
17 E remove(int index) 删除list中index位置的元素
18 boolean remove(Object o) 删除list中等于o的元素,如果有元素被删除,返回true
19 boolean removeAll(Collection<?> c) 从list中删除另一个集合c中的所有元素,如果调用改变了集合返回true
20 default void replaceAll(UnaryOperator<E> operator) Java 8新方法,根据UnaryOperator规则,将list中每一个元素映射为另一个元素
21 boolean retainAll(Collection<?> c) 从list中保留另一个集合c中的所有元素,如果调用改变了集合返回true
22 E set(int index, E element) 将list index位置的元素设置为element
23 int size(); 返回list 中元素的个数
24 default void sort(Comparator<? super E> c) Java8新方法,根据Comparator排序规则,对list进行排序
25 default Spliterator<E> spliterator() Java8新方法,返回集合的Spliterator迭代器
26 List<E> subList(int fromIndex, int toIndex) 返回list从fromIndex到toIndex索引位置(区间左闭右开)的subList
27 Object[] toArray() 将list的所有元素转为一个Object数组
28 <T> T[] toArray(T[] a) 将list的所有元素转为特定类型的数组

这部分方法在之前的文章中都有讲解,不多解释了。

1.3 Deque接口

LinkedList实现了Deque接口,Deque是一个双向队列,接口中定义了支持栈和队列的相关方法,所以可以使用LinkedList实现栈、队列的相关操作。Deque继承了Queue接口,Queue是一个单向队列,入队操作只能在尾部,出队操作只能在头部。下面来看一下Deque接口中的相关方法。

1.3.1 Queue接口

上面讲到,Deque实现了单向队列Queue接口,下面来看一下Queue接口中定义的方法,如下:

S.N. 方法 说明
1 boolean add(E e) 向单向队列尾部添加一个元素,队列为满时,抛出IllegalStateException异常
2 boolean offer(E e) 向单向队列尾部添加一个元素,队列为满时,返回false,不抛异常
3 E remove() 从单向队列队头删除一个元素,队列为空时,抛出NoSuchElementException异常
4 E poll() 从单向队列队头删除一个元素,队列为空时,返回null,不抛异常
5 E element() 返回队头元素,不改变队列,队列为空时,抛出NoSuchElementException异常
6 E peek() 返回队头元素,不改变队列,队列为空时,返回null,不抛异常

可以发现,队列同一个操作都有两个方法实现,主要区别在于对于一些极端情况的处理上,比如队列为空、队列满时的操作。另外需要注意的是,对于LinkedList实现的队列而言,队列容量没有限制,可以无限大,但是对于像ArrayDeque这样的队列,就有容量限制,产生队列满的情况。

1.3.2 Deque中栈操作方法

接触过数据结构的肯定都清楚,栈是一种后进先出的数据结构。在Java API java.util包中,存在一个Stack类,就是栈这一数据结构在Java中的实现,但是现在很少使用了。Deque中定义了一些栈相关操作的方法,并在LinkedList中给予实现,所以使用LinkedList可以实现队列操作。下面来简单看一下Deque接口中定义的栈操作相关方法,如下:

S.N. 方法 说明
1 void push(E e) 入栈,如果栈容量已满,抛IllegalStateException异常
2 E pop() 出栈,如果栈为空,抛NoSuchElementException异常
3 E peek() 查看栈顶元素,栈为空时,返回null,不抛异常

1.3.3 Deque中双向队列操作方法

栈只操作头部,队列两端都操作,但尾部只添加、头部只查看和删除。有一个更为通用的操作两端的接口Deque,Deque扩展了Queue,包括了栈的操作方法,下面来看一下Deque中用于支持双向队列操作的方法,如下:

S.N. 方法 说明
1 void addFirst(E e) 向双向队列头部添加元素,如果队列已满,抛IllegalStateException异常
2 void addLast(E e) 向双向队列尾部添加元素,如果队列已满,抛IllegalStateException异常
3 boolean offerFirst(E e) 向双向队列头部添加元素,如果队列已满,返回false,不抛异常
4 boolean offerLast(E e) 向双向队列尾部添加元素,如果队列已满,返回false,不抛异常
5 E getFirst() 获取双向队列头部元素,不改变结构,如果队列为空,抛NoSuchElementException异常
6 E getLast() 获取双向队列尾部元素,不改变结构,如果队列为空,抛NoSuchElementException异常
7 E peekFirst() 获取双向队列头部元素,不改变结构,如果队列为空,返回null,不抛异常
8 E peekLast() 获取双向队列尾部元素,不改变结构,如果队列为空,返回null,不抛异常
9 E removeFirst() 删除双向队列头部元素,如果队列为空,抛NoSuchElementException异常
10 E removeLast() 删除双向队列尾部元素,如果队列为空,抛NoSuchElementException异常
11 E pollFirst() 删除双向队列头部元素,如果队列为空,返回null,不抛异常
12 E pollLast() 删除双向队列尾部元素,如果队列为空,返回null,不抛异常
13 boolean removeFirstOccurrence(Object o) 删除双向队列中第一次出现的o元素,如果双向队列中不包含o,返回false
14 boolean removeLastOccurrence(Object o) 删除双向队列中最后一次出现的o元素,如果双向队列中不包含o,返回false
15 Iterator<E> descendingIterator() 返回双向队列逆序迭代器Iterator

2. 实现源码分析

在上篇介绍ArrayList的文章中讲过,ArrayList底层是基于数组实现的,内部存储的元素在物理存储上都是连续存放的。但LinkedList不同的是,LinkedList在物理存储上是非连续的,LinkedList中的各个元素是链表的一个节点,节点跟节点之间是通过引用链接到一起的,这一点跟C和C++的指针很像,如下图所示(下图为单向的链表,LinkedList是双向链表):

 Java API LinkedList实现中,定义了一个内部类Node,用于表示链接的各个元素,如下所示:

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

可以看到,Node类中定义了一个节点包括实际的元素item,同时有两个链接,分别指向前一个节点(前驱)prev,和后一个节点(后继)next。

LinkedList声明定义如下,内部主要包含如下三个成员变量:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

}  

类的继承关系上面已经讲过,成员变量size表示链表长度,默认为0,first指向双向链表头节点,last指向双向链表尾节点,初始值为null。

2.1 构造函数

Java API中LinkedList存在两个构造函数,一个无参默认构造函数,另一个是通过一个Collection对象构造LInkedList的构造函数,如下:

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
} 

当调用无参构造函数时,size为0,头节点first、尾节点last都为null。

2.2 add(E e)方法

add(E e)方法的功能是向链表尾部添加一个元素,跟ArrayList不同的是,ArrayList在物理存储上是连续的,内部通过数组实现,在添加元素时,要保证容量足够,但是LinkedList在物理上时一个个逻辑上相连的节点,没有容量的定义,所以在add操作时,也不用像ArrayList那样提前分配一个余量,在添加元素时,只要新增一个节点,然后修改一下链接就可以了。定义如下:

public boolean add(E e) {
    linkLast(e);
    return true;
} 

add方法中调用了linkLast方法,向链表尾部添加一个元素,如下:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

其中比较重要的就是调用Node的构造函数,生成一个Node用于存储带插入的数据e,并进行链接。

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

在生成Node时,对Node的prev和next指针进行链接(这里为了方便表述,本篇文章之后都通过指针表述链接)。在linkLast方法中拿到新生成的Node,尾插法进行连接,修改last指针,first指针指向,并对链表的size和modCount进行自增操作。如下:

 看一个具体的例子,如下:

2.3 add(int index, E element)方法

add(int index, E element)方法时像链表index索引位置添加一个元素,定义如下:

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

首先还是通过checkPositionIndex方法,检查index索引的合法性,跟上节讲ArrayList插入操作时一样,index索引位置要求只能在size范围内,如下:

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

接下来通过index和size的关系,判断时在尾部插入还是在尾部之前的位置插入,如果时尾部插入就跟之前的add(E element)操作一致,直接调用linkLast方法即可。如果在size之前的位置插入,调用linkBefore方法进行插入操作,如下:

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

操作也比较简单,就是将带插入的元素生成一个Node,并对Node前后的节点的next、prev指针进行链接,对size和modCount进行自增操作上面已经讲述了,这里不重复讲解了,可以参考下图:

2.4 remove(int index)方法

remove(int index)用来删除指定index位置的元素,如下:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

首先调用checkElementIndex方法检查待删除的index,index范围要求index >= 0 && index < size。然后调用unlink方法,删除node(index)前后节点的链接指针,并进行重链接,如下:

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

首先让x前驱Node的next指针指向x的后继Node,如果x没有前驱Node,说明删除的是头节点,则修改头节点指向x的后继Node。然后让x的后继Node的prev指针指向x的前驱Node,如果x没有后继Node,说明删除的是尾节点,则修改尾节点指向x的前驱Node。 如下图:

2.5 remove(Object o)方法

LinkedList中还有一个remove方法,如下:

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

删除LinkedList中所有与o相等的元素,就是通过藏头遍历LinkedList,然后通过上述unlink操作删除节点。

2.6 get(int index)方法

get方法用于获取指定index位置的元素,定义如下:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

首先通过checkElementIndex方法,检查index索引的合法性,index范围要求index >= 0 && index < size。然后返回index索引位置的Node的item,如下:

Node<E> node(int index) {
    // assert isElementIndex(index);

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

size>>1等于size/2,如果索引位置在前半部分 (index<(size>>1)),则从头节点开始查找,否则,从尾节点开始查找,这样效率会高一些。同时也验证了之前的一个结论,ArrayList支持随机访问,查询效率比较高,LinkedList不支持随机访问,需要从头或尾遍历,效率相对较低,时间复杂度为O(N)。

2.6 迭代器

LinkedList中存在四种可用的迭代器,可以通过如下方式获取:

  • iterator(),继承自AdstractList类,返回LinkedList从头向尾的单向Iterator迭代器
  • descendingIterator(),继承自Deque接口,LinkedList中实现,返回从尾向头的单向Iterator迭代器
  • listIterator(int index),继承自List接口,LinkedList中实现,返回LinkedList index位置开始的的双向迭代器
  • spliterator(),返回LinkedList的并行Spliterator迭代器

跟ArrayList相似,在使用迭代器进行迭代过程中,如果修改了LinkedList结构,也会抛ConcurrentModificationException异常。

3. LinkedList特点

  • 各元素之间逻辑上连续,物理存储上不连续
  • 不支持随机访问,按照索引位置访问效率比较低,必须从头或尾顺着链接找,效率为O(N/2)
  • 按照内容查找元素,效率都比较低,必须逐个比较,效率为O(N)
  • 在两端添加、删除元素的效率很高,为O(1)
  • 在中间插入、删除元素,要先定位,效率比较低,为O(N),但修改本身的效率很高,效率为O(1),不需要像ArrayList那样移位

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『容器——LinkedList』
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址