LinkedList源码了解一下

发表于 | 分类于 ， | 评论数：   |   字数统计: 2,755   |   阅读时长: 12min | 热度： ℃

前言

LinkedList是我们比较常用的数据类型之一，也是面试中比较容易问到的集合之一。本篇文章主要通过分析LinkedList的源码。

本文基于jdk1.8

LinkedList简介

LinkedList是基于双向循环链表实现的，它的头结点不存放数据。

LinkedList类结构

LinkedList类结构图

可以从上图看出，LinkedList继承AbstractSequentialList抽象类，实现了List，Deque，Cloneable，Serializable接口。

LinkedList特点

  1. LinkedList非线程安全。
  2. LinkedList允许插入null。
  3. LinkedList中的数据存储是有序的。
  4. LinkedList中的数据可以重复。

LinkedList提供的API

方法名 方法解释
add(E e) 将指定的元素添加到LinkedList的末尾。
add(int index, E element) 将指定的元素插入到LinkedList中的指定位置。
addAll(Collection<? extends E> c) 将指定的集合中的所有元素添加到LinkedList的末尾。
addAll(int index, Collection<? extends E> c) 将指定的集合中的所有元素添加到LinkedList中的指定位置。
addFirst(E e)
addLast(E e)
clear() 删除LinkedList中的所有元素。
clone() LinkedList浅拷贝。
contains(Object o) 判断LinkedList中是否包含指定元素。
descendingIterator()
element()
get(int index) 获取LinkedList中指定位置的元素。
getFirst()
getLast()
indexOf(Object o) 返回LinkedList中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
lastIndexOf(Object o) 返回LinkedList中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
listIterator(int index) 从LinkedList中指定的位置开始，返回LinkedList中元素的列表迭代器。
offer(E e)
offerFirst(E e)
offerLast(E e)
peek()
peekFirst()
peekLast()
poll()
pollFirst()
pollLast()
pop()
push(E e)
remove()
remove(int index) 删除LinkedList中指定位置的元素。
remove(Object o) 从LinkedList中删除第一次出现的指定元素（如果存在）。
removeFirst()
removeFirstOccurrence(Object o)
removeLast()
removeLastOccurrence(Object o)
set(int index, E element) 用指定的元素替换LinkedList中指定位置的元素。
size() 获取LinkedList大小。
spliterator()
toArray() 将LinkedList转换为数组。
toArray(T[] a) 将LinkedList转换为指定类型的数组。

LinkedList源码

LinkedList成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * LinkedList大小
 */
transient int size = 0;

/**
 * LinkedList链表的头节点
 */
transient Node<E> first;

/**
 * LinkedList链表的尾节点
 */
transient Node<E> last;

LinkedList内部类

Node

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

LinkedList构造函数

LinkedList一共有两个构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 无参构造函数。
 */
public LinkedList() {
}

/**
 * 通过Collection创建LinkedList。
 */
public LinkedList(Collection<? extends E> c) {
    this();
    // 调用addAll方法，将集合添加到LinkedList中
    addAll(c);
}

LinkedList重要方法解析

add(E e)

1
2
3
4
5
6
public boolean add(E e) {
    // 将节点链接到LinkedList最后
    linkLast(e);
    // 返回添加成功的结果
    return true;
}

  • linkLast(E e)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void linkLast(E e) {
        // 获取之前的尾节点
        final Node<E> l = last;
        // 根据e创建新的节点，该节点的前一个节点为之前的尾节点，后一个节点为null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将新的节点设置为尾节点
        last = newNode;
        // 如果之前的尾节点为null，则新增的节点也是头节点
        if (l == null)
            first = newNode;
        // 如果之前的尾节点不为null，将之前的尾节点的下一个节点设置为新的节点
        else
            l.next = newNode;
        // LinkedList大小加1
        size++;
        // 操作次数加1
        modCount++;
    }

    add(E e)流程：

  1. 保存原来的尾节点
  2. 将需要插入的元素包装成新的节点，该节点的前一个节点为原来的尾节点，后一个节点为null
  3. 将新的节点设置为尾节点
  4. 如果原来的尾节点为null，则设置新的节点为头节点
  5. 如果原来的尾节点不为null，将原来节点的下一个节点设置为新的节点
  6. LinkedList大小加1，操作次数加1，并返回成功

add(int index, E element)

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

    // 如果定位是最后一个节点，就将节点链接到最后
    if (index == size)
        linkLast(element);
    // 
    else
        linkBefore(element, node(index));
}

  • checkPositionIndex(int index)

    1
    2
    3
    4
    5
    private void checkPositionIndex(int index) {
        // 如果定位越界，抛出越界异常
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

  • isPositionIndex(int index)

    1
    2
    3
    4
    private boolean isPositionIndex(int index) {
        // 返回定位是否越界
        return index >= 0 && index <= size;
    }

  • node(int index)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    Node<E> node(int index) {
        // assert isElementIndex(index);

        // 判断定位是否小于LinkedList大小的一半，是的话，从头节点开始遍历，不是话从尾节点开始遍历
        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;
        }
    }

  • linkBefore(E e, Node succ)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // 记录定位到的节点的前一个节点
        final Node<E> pred = succ.prev;
        // 根据e创建新的节点，新节点的前一个节点为定位到的节点的前一个节点，后一个节点为定位到的节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 设置定位到的节点前一个节点为新的节点
        succ.prev = newNode;
        // 如果定位到的节点的前一个节点为null，则新的节点为头节点
        if (pred == null)
            first = newNode;
        // 如果定位到的节点的前一个节点不为null，将前一个节点的下一个节点设置为新的节点
        else
            pred.next = newNode;
        // LinkedList大小加1
        size++;
        // 操作次数加1
        modCount++;
    }

addAll(Collection<? extends E> c)

1
2
3
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

addAll(int index, Collection<? extends E> c)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public boolean addAll(int index, Collection<? extends E> c) {
    // 判断定位是否越界
    checkPositionIndex(index);

    // 将c转换为数组
    Object[] a = c.toArray();
    // 获取数组长度
    int numNew = a.length;
    // 如果数组为0，返回false
    if (numNew == 0)
        return false;

    
    Node<E> pred, succ;
    // 如果插入的位置为尾部，succ为null，前一个节点为之前的尾节点
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        //　如果插入的位置不是尾部，succ为定位的节点，前一个节点为定位到的节点的前一个节点
        succ = node(index);
        pred = succ.prev;
    }

    // 遍历数组进行添加
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 根据e创建新的节点，新节点的前一个节点为前面获取的pred节点，后一个节点为null
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果前一个节点null，则新节点为头节点
        if (pred == null)
            first = newNode;
        // 如果前一个节点不为null，设置前一个节点的后一个节点为新节点
        else
            pred.next = newNode;
        // 将新节点设置为pred节点
        pred = newNode;
    }

    // 如果succ节点为null，前面循环添加的最后一个节点为尾节点
    if (succ == null) {
        last = pred;
    } else {
        // 如果succ节点不为null，设置前面循环添加的最后一个节点的后一个节点为succ节点，succ节点的前一个节点为pred节点
        pred.next = succ;
        succ.prev = pred;
    }

    // 增加LinkedList的大小
    size += numNew;
    // 操作次数加1
    modCount++;
    // 返回true
    return true;
}

contains(Object o)

1
2
3
4
public boolean contains(Object o) {
    // 根据匹配方法返回的元素下标判断是否存在该对象
    return indexOf(o) != -1;
}

  • indexOf(Object o)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public int indexOf(Object o) {
        int index = 0;
        // 如果匹配对象为null，遍历LinkedList，使用==进行匹配，并返回位置；如果匹配对象不为null，遍历LinkedList，使用equals进行匹配，并返回位置
        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++;
            }
        }
        // 匹配不到，返回-1
        return -1;
    }

get(int index)

1
2
3
4
5
6
public E get(int index) {
    // 判断定位是否越界
    checkElementIndex(index);
    // 获取节点中的内容
    return node(index).item;
}

get(int index)流程：

  1. 判断定位是否越界
  2. 调用node方法，获取节点
  3. 返回节点的内容

remove(int index)

1
2
3
4
5
6
public E remove(int index) {
    // 判断定位是否越界
    checkElementIndex(index);
    // 删除节点
    return unlink(node(index));
}

  • unlink(Node x)

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

        // 如果前一个节点为null，将头节点设置为后一个节点
        if (prev == null) {
            first = next;
        } else {
            //　如果前一个节点不为null，将前一个节点的下一个节点设置为定位到的节点的下一个节点
            prev.next = next;
            // 将定位到的节点的前一个节点设置为null
            x.prev = null;
        }

        // 如果后一个节点为null，将尾节点设置为前一个节点
        if (next == null) {
            last = prev;
        } else {
            //　如果后一个节点不为null，将后一个节点的前一个节点设置为定位到的节点的前一个节点
            next.prev = prev;
            // 将定位到的节点的后一个节点设置为null
            x.next = null;
        }

        // 将定位到的节点的内容设置null
        x.item = null;
        // LinkedList大小减1
        size--;
        // 操作次数加1
        modCount++;
        // 返回定位到的节点的原内容
        return element;
    }

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
    // 如果匹配对象为null，遍历LinkedList，使用==进行匹配，调用unlink进行删除节点；如果匹配对象不为null，遍历LinkedList，使用equals进行匹配，调用unlink进行删除节点
    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;
}

set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
public E set(int index, E element) {
    // 判断定位是否越界
    checkElementIndex(index);
    // 获取定位的节点
    Node<E> x = node(index);
    // 获取该节点的内容
    E oldVal = x.item;
    // 将新的值设置为该节点的内容
    x.item = element;
    // 返回原来的内容
    return oldVal;
}

队列相关方法

TODO

总结

通过这篇文章，我们对LinkedList进行了更深入的了解，在以后使用过程中，可以避免一些坑。

ps：关于队列的一些方法后续有空会进行添加。

欢迎关注博主其他的文章。

感谢您的支持！

本文标题:LinkedList源码了解一下

文章作者:yoga

发布时间:2017年01月20日 - 19:01

原始链接:https://yoga0521.github.io/2017/01/20/LinkedList源码了解一下/

版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。 转载请注明出处！