成员变量

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

我们看到LinkedList的成员变量只有3个，比ArrayList还要少。

  • size：链表大小。
  • first：Node类的引用，指向表头
  • last：Node类的引用，指向表尾
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;
    }
}

其中Node是一个内部类

  • item：节点数据
  • next：下一个节点
  • prev：上一个节点

构造方法

1
2
3
4
5
6
7
public LinkedList() {
}

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

LinkedList有两个构造方法，一个不带参数，一个Collection类做为参数。所以想要初始化一个链表，还可以用一个Collection的子类做为参数。

1
2
3
4
5
6
7
8
9
10
public class Test1 {
    public static void main(String[] args) {
        List<Integer> arraylist = new ArrayList<>();
        arraylist.add(1);
        arraylist.add(2);

        List<Integer> list1 = new LinkedList<>(arraylist);
        System.out.println(list1);
    }
}

主要方法

add(E e)

末尾插入一个节点。

1
2
3
4
public boolean add(E e) {
    linkLast(e);
    return true;
}

直接调用**linkLast(e)**方法。

1
2
3
4
5
6
7
8
9
10
11
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++;
}

添加第一个节点过程如下

插入第二个节点

从这可以看出LinkedList是一个双向链表。

add(int index, E element)

指定位置插入一个节点。

1
2
3
4
5
6
7
8
void add(int index, E element) {
    checkPositionIndex(index);

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

调用checkPositionIndex函数，检查index是否符合规范。

1
2
3
4
5
6
7
8
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

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

索引符合条件后，再判断索引值是不是最后一个，如果是最后一个就调用linkLast方法，这个方法和add方法是一样的，在链表末尾插入一个节点。

我们重点看看linkBefore方法。

1
2
3
4
5
6
7
8
9
10
11
12
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++;
}

succ参数就是通过node(int index)查找到的索引位置的节点，node是一个很简单变历链表寻找节点的方法，大家可以自行去看源码。

我们还是以画图为例，假设现在链表有两个节点，我们要往中间插入一个节点。

可以看到这是一个非常简单高效的算法。

getFirst() & getLast()

得到链表首位元素

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

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

removeFirst() & removeLast()

删除首位元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

调用了unlinkFirst和unlinkLast函数

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
27
28
29
30
31
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

这里以unlinkFirst为例

addFirst(E e) & addLast(E e)

链表首尾插入节点。

1
2
3
4
5
6
7
public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

linkFirst和linkLast方法与add实现方法类似，不在介绍。

contains(Object o)

查询列表是否包含某个元素。

1
2
3
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

indexOf方法会从前往后遍历链表，查找指定元素的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

size()

返回链表长度。

1
2
3
public int size() {
    return size;
}

remove(Object o) & remove(int index)

删除一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

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

我们来看一下unlink方法，可以和前面的linkBefore做一些比较。

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

还是假设有3个节点，要删除中间节点。

clear()

删除链表所有节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

从头到尾删除，最后回到最初first和last都指向空的状态。

get(int index)

得到指定索引出的元素。

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

set(int index, E element)

设定指定索引处的值

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

push(E e) & pop()

链表头插入和删除。

1
2
3
4
5
6
7
public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

clone()

复制一份一样的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // Initialize clone with our elements
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

toArray()

转化为数组。

1
2
3
4
5
6
7
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

总结

  • LinkedList是基于链表实现的，而且是双向链表。
  • 插入元素不需要大量移动节点。
  • 链表在查询时一般使用从头到尾或者从尾到头遍历，效率不高。