LinkedList那点事儿

LinkedList那点事儿

薛定谔的汪 Lv5
  2018-07-07 18:01:54 2018-07-07 18:01:54 Created   2023-11-17 19:37:37 2023-11-17 19:37:37 Updated    

前面写了点 ArrayList 一些源码的分析，今天分析下 LinkedList 集合常用 API 的源码。

LinkedList 和 ArrayList 都是 List接口的实现类，都是线程不安全、允许元素为 null 的。这俩集合经常被拿来进行比较，面试问的也比较多。这里先给出这俩在一般情况下的区别:

ArrayList 底层是数组结构，增删慢（涉及数组的复制和元素移动），改查快（实现了RandomAccess）。

LinkedList 底层是双向链表，增删快（修改节点的前后指针即可），改查慢。

但凡事无绝对，这种说法还是要分情况的！文末会分析。

继承关系

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

看出 LinkedList 继承自 AbstractSequentialList 实现了 List， 说明是一个有序集合，实现了 Deque 说明可以作为

一个双端队列来用，没有实现 RandomAccess 接口，说明随机访问元素索引速度慢。

注：LinkedList 和 ArrayList 一样都重复实现了 List

属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 集合长度
 */
transient int size = 0;

/**
 * 链表首节点
 */
transient Node<E> first;

/**
 * 链表末节点
 */
transient Node<E> last;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 构造一个空集合
 */
public LinkedList() {
}

/**
 * 将 Collection 集合中的元素添加到 LinkedList 中 addAll 方法分析下面有
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList 的构造方法没什么可说的，嗯继续。

LinkedList 有一个静态内部类 Node，链表的每个位置上存的是 Node，Node 里存放的才是元素，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;
    }
}

常用 API

添加元素

addAll

描述：向索引 index尾部批量添加 Collection 中的元素。

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
32
33
34
35
36
37
38
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//检查 index 是否越界 index >= 0 && index <= size;
 
    Object[] a = c.toArray(); //Collection 转换为数组
    int numNew = a.length;  //获取数组长度
    if (numNew == 0)       //如果数组长度为0则直接返回false
        return false;

    Node<E> pred, succ;   //声明前节点，后节点
    if (index == size) {  //如果是向 LinkedList 末尾添加则后节点=null，前节点设置为原集合最后一个节点
        succ = null;
        pred = last;
    } else {             //获得index处节点作为后置节点，index节点的前节点作为前节点
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) { //遍历数组
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); //以前置节点和元素e创建节点
        if (pred == null) //如果前置节点是 null,说明是首结点，则将首节点设置为新创建的节点
            first = newNode;
        else             //不是首节点，就将前直接点的下一个节点设置为新创建的节点
            pred.next = newNode;
        pred = newNode;  //将前节点设置为刚新创建的节点，继续遍历添加...
    }

    if (succ == null) { //遍历完后，如果后节点是 null，说明是在末尾添加节点(index=size)
        last = pred; //设置尾节点
    } else {
        pred.next = succ; //更新前后节点指针
        succ.prev = pred; //更新前后节点指针
    }

    size += numNew; //更新链表长度
    modCount++;  //添加完整个Collection 后才更新修改次数。
    return true;
}

add(E element) 添加单个元素

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

默认向链表末尾添加元素

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) //判断 如果原来的 LinkeList 是空集合，则需要设置第一个节点也是新创建的节点
        first = newNode;
    else        //集合不是空结合的话设置原来末节点的下一个节点指向新节点即可
        l.next = newNode;
    size++;  
    modCount++;
}

add(int index, E element)在执行索引处添加元素

1
2
3
4
5
6
7
8
public void add(int index, E element) {
    checkPositionIndex(index); //检查索引是否越界 

    if (index == size) //index=size 说明是向集合末尾添加节点
        linkLast(element);
    else
        linkBefore(element, node(index)); //index < size 默认是在index节点前添加
}

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设置为新的节点。
        first = newNode;
    else              
        pred.next = newNode; //原前置节点的后置节点指向新节点
    size++;
    modCount++;
}

删除元素

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
    //因为要根据 equeals 方法来判断对象是否是同一个，所以要先判断 Object 是否为空
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item; //获得节点x存放的元素
    final Node<E> next = x.next; //获得x的后节点
    final Node<E> prev = x.prev; //获得x的前节点

    if (prev == null) { //如果前节点是空，表示x节点是头结点，移除x后要将 x的后节点设置为头结点
        first = next;
    } else {            
        prev.next = next; //x移除后，将 x 的前节点的后节点不再指向 x,而是指向x的后节点，x也和前节点断开
        x.prev = null;
    }

    if (next == null) { //如果后节点是空，表示要被移除的x是末节点，则需要额外将集合的末节点修改设置为 x 的前节点
        last = prev;
    } else {
        next.prev = prev; // x移除后，将 x 的后节点的前节点不再指向x，而是指向x的前节点，x也和后节点断开
        x.next = null;
    }

    x.item = null; //将 x 节点的元素设置为null，便于垃圾回收（GC）。
    modCount++;
    return element; 
}

删除的方法还有unlinkFirst、unlinkLast比较简单就不阐述了。

更改元素

set

将索引 index 位置上的元素修改

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);  //同样是检查index是否越界 index>=0 && index <= size
    Node<E> x = node(index);   //获取 index 节点
    E oldVal = x.item;        //获取原元素
    x.item = element;         //替换为新元素
    return oldVal;            //返回原元素
}

查询

获取目标索引的元素

1
2
3
4
public E get(int index) {
    checkElementIndex(index); //检查索引是否越界
    return node(index).item;  //获得 index 节点再获取元素并返回
}

获取 index 节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<E> node(int 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;
    }
}

疑问解答

上面说到 添加元素时，ArrayList 比 LinkedList 慢，其实这并非绝对。

在数据量小时，ArrayList 的速度可能比 LinkedList还要快，原因是此时的 ArrayList 的数组拷贝比 LinkedList 创建 Node 实例速度快。

参考地址：https://stackoverflow.com/questions/16808777/is-linkedlist-really-faster-than-arraylist-in-the-case-of-insertion-in-the-middl

总结

回顾完 ArrayList 和 LinkList 源码后知道这两个集合的底层实现，更深入地了解了这两个集合的区别，在以后开发

中应根据实际场景来选择合适的集合，提高性能。

  • Title: LinkedList那点事儿
  • Author: 薛定谔的汪
  • Created at : 2018-07-07 18:01:54
  • Updated at : 2023-11-17 19:37:37
  • Link: https://www.zhengyk.cn/2018/07/07/java/LinkedList/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
LinkedList那点事儿
  1. 继承关系
  2. 属性
  3. 构造方法
  4. 常用 API
    1. 添加元素
    2. 删除元素
    3. 更改元素
    4. 查询
  5. 疑问解答
  6. 总结