Java8集合系列之LinkedList（二）

Posted on   |   In   |     |   visitors

LinkedList

LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable，实现了List、Deque（双端队列）等接口。所以LinkedList不仅可以作为一般的list集合使用，也可以作为普通的队列使用。

Node结点数据结构

1
2
3
4
5
6
7
8
9
10
11
12
//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;//确定新添加Node的后序节点
        this.prev = prev;//确定新添加Node的前序节点
    }
}

construct

1
2
3
4
5
/**
 * Constructs an empty list.
 */
public LinkedList() {
}

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 默认将元素添加在列表末尾
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;//last指向新节点
    if (l == null)
        first = newNode;//如果原来为空，将first也指向新节点
    else
        l.next = newNode;//否则，让前序节点，后序指向新节点
    size++;
    modCount++;
}

LinkedList的add方法默认是将元素添加到list的末尾，但是由于实现了Deque双端队列接口，所以还有诸如addFirst(E e)、linkFirst(e)等方法，将元素添加到首部，学过数据结构，对这个应该不陌生，大同小异。
另外，还有offer方法则是直接调用了add方法如下所示：

1
2
3
public boolean offer(E e) {
    return add(e);
}

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    // help GC
    f.item = null;
    f.next = null; 
    //first指向下一个
    first = next;   
    if (next == null)//如果没有元素了，first、last均设为null。
        last = null;
    else
        next.prev = null;//清空前序变量
    size--;
    modCount++;
    return element;
}

LinkedList的remove方法默认是删除首部元素，当然也有removeLast()、remove(int index)等方法。

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E get(int index) {
    checkElementIndex(index);//检查索引范围是否合法
    return node(index).item;
}
//获取索引为index的节点
Node<E> node(int index) {
    //这里用了一个小小的技巧，一句话就是看index距离first和last哪一端更近，就从那边开始遍历。
    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;
    }
}

同理，LinkedList还有getFirst()、getLast()等方法，具有O(1)的时间复杂度。

1
2
3
4
5
6
public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

小结

1、底层基于双端链表实现，允许列表为null。
2、LinkedList插入元素很快，不存在ArrayList扩容的概念，只要内存够大就行。
3、基于双端链表，不能实现随机访问，查找效率低。
4、删除元素操作较快。