关于java:LinkedList源码简析

1 LinkedList 简介

LinkedList是一个实现了 <font color=”red”>List 接口 </font> 和 <font color=”red”>Deque 接口 </font> 的 <font color=”red”> 双端链表 </font>。

<img src=”https://img-blog.csdnimg.cn/20201108105348736.png” />

LinkedList继承于 AbstractSequentialList，实现了 List、Deque、Cloneable、java.io.Serializable 接口。

LinkedList 实现了 List 接口，表明其能进行链表的高效插入和删除操作。
LinkedList 实现了 Deque 接口，即能将LinkedList 当作双端队列应用。
LinkedList 实现了了 Cloneable 接口，即笼罩了函数 clone()，可能克隆。
LinkedList 实现了 java.io.Serializable 接口，这意味着 LinkedList 反对序列化，能通过序列化传输数据。

LinkedList 不是线程平安的，如果想使 LinkedList 变成线程平安的，能够调用动态类 Collections 类中的 synchronizedList 办法

List list=Collections.synchronizedList(new LinkedList(...));

2 成员属性

// 总节点数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

能够发现 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;
        }
    }

因而 LinkedList 的构造如下：

3 构造方法

// 空参的构造方法，只生成了对象
public LinkedList() {}

public LinkedList(Collection<? extends E> c) {
    // 先结构一个空链表
    this();
    // 增加 Collection 中的元素
    addAll(c);
}

4 罕用办法

4.1 增加元素

add(E e)：将元素增加到链表尾部

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

    /**
     * 链接使 e 作为最初一个元素。*/
    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++;
    }

add(int index,E e)：在指定地位增加元素

public void add(int index, E element) {checkPositionIndex(index);// 查看索引 index 是否处于 [0-size] 之间

        if (index == size)
            linkLast(element);// 增加在链表尾部
        else 
            linkBefore(element, node(index));// 插入到 index 所指地位的节点后面
    }
    
    /**
     * 将新节点插入到指定节点后面
     */
    void linkBefore(E e, Node<E> succ) {
        // 取出指定地位的前一个节点
        final Node<E> pred = succ.prev;
        // 构建新节点，pred 指定地位的前驱节点，succ 指定地位，e 是增加的元素
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 指定节点的前驱节点指向要插入的节点。succ.prev = newNode;
        // 如果指定地位的前驱节点为空，即指定地位 succ 是头节点，即 newNode 设为头节点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode; // 不为空，原地位的前驱节点的后置节点设置为新节点。size++;
        modCount++;
    }

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

    private boolean isPositionIndex(int index) {return index >= 0 && index <= size;// 查看索引 index 是否处于 [0-size] 之间
    }

addAll(Collection c)：将汇合元素插入到链表中

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

public boolean addAll(int index, Collection<? extends E> c) {
        // 1、查看 index 范畴是否在 size 之内
        checkPositionIndex(index);

        // 2、把汇合的数据存到对象数组中
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        // 3、失去插入地位的前驱节点和后继节点
        Node<E> pred, succ;
        // 如果插入地位为尾部，前驱节点为 last，后继节点为 null
        if (index == size) {
            succ = null;
            pred = last;
        }
        // 否则，调用 node()办法失去后继节点，再失去前驱节点
        else {succ = node(index);
            pred = succ.prev;
        }

        // 4、遍历数据将数据插入
        for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
            // 创立新节点
            Node<E> newNode = new Node<>(pred, e, null);
            // 如果插入地位在链表头部
            if (pred == null)
                // 把前一个节点向后指向 newNode
                first = newNode;
            else
                pred.next = newNode;
            // 在 if-else 之外，如果没有这语句，pred 节点就固定是那一个节点，所以须要在每一次循环内更换节点
            pred = newNode;
        }

        // 如果插入地位在尾部，重置 last 节点
        if (succ == null) {last = pred;}
        // 插入的链表与先前链表连接起来
        else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }    

addFirst(E e)： 将元素增加到链表头部

 public void addFirst(E e) {linkFirst(e);
    }

private void linkFirst(E e) {
        // 找到以后头节点
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);// 新建节点，以之前头节点为后继节点
        // 新节点为头节点
        first = newNode;
        // 如果链表为空，last 节点也指向新节点
        if (f == null)
            last = newNode;
        // 否则，将之前头节点的前驱指针指向新节点，也就是指向前一个元素
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

addLast(E e)： 将元素增加到链表尾部，与 add(E e) 办法一样

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

4.2 查找元素

get(int index)： 依据指定索引返回数据

public E get(int index) {
        // 查看 index 是否在非法地位
        checkElementIndex(index);
        // 调用 Node(index)去找到 index 对应的 node 而后返回它的值 item
        return node(index).item;
    }

获取头节点（index=0）数据办法:

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
public E element() {return getFirst();
    }
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

区别：
getFirst() 和element() 办法将会在链表为空时，抛出异样；

element()办法的外部就是应用 getFirst() 实现的。它们会在链表为空时，抛出 NoSuchElementException。

获取尾节点（index=-1）数据办法:

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

两者区别：
getLast() 办法在链表为空时，会抛出NoSuchElementException；而peekLast() 只是会返回 null。

4.3 删除元素

remove()、removeFirst()、pop(): 删除头节点

public E pop() {return removeFirst();
    }
public E remove() {return removeFirst();
    }
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

removeLast()、pollLast(): 删除尾节点

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

区别： removeLast()在链表为空时将抛出 NoSuchElementException；pollLast()办法返回 null。

remove(Object o): 删除指定元素

public boolean remove(Object o) {
        // 如果要删除对象为 null
        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;
    }

当删除指定对象时，只需调用 remove(Object o)即可，不过该办法一次只会删除一个匹配的对象，如果删除了匹配对象，返回 true，否则 false。

unlink(Node<E> x) 办法：删除指定节点

E unlink(Node<E> x) {
        final E element = x.item;
        // 失去 x 的后继节点
        final Node<E> next = x.next;
        // 失去 x 的前驱节点
        final Node<E> prev = x.prev;

        // x 是头节点
        if (prev == null) {
            // 如果删除的节点是头节点, 令头节点指向该节点的后继节点
            first = next;
        } else {
            // 将前驱节点的后继节点指向 x 的后继节点
            prev.next = next;
            // 删除 x 的前指向
            x.prev = null;
        }

        // x 是尾节点
        if (next == null) {last = prev;// 如果删除的节点是尾节点, 令尾节点指向该节点的前驱节点} else {
            next.prev = prev;
            x.next = null;
        }
        
        // 删除指定节点内容
        x.item = null;
        size--;
        modCount++;
        return element;
    }

remove(int index)：删除指定地位的元素

public E remove(int index) {
        // 查看 index 范畴
        checkElementIndex(index);
        // 将节点删除
        return unlink(node(index));
    }

4.4 批改元素

set(int index, E element)办法：批改指定节点元素

    public E set(int index, E element) {
        // 查看是否越界
        checkElementIndex(index);
        // 依据索引查找节点
        Node<E> x = node(index);
        // oldVal 寄存须要扭转的内容
        E oldVal = x.item;
        x.item = element;
        // 返回扭转前的值
        return oldVal;
    }

5 ArrayList 与 LinkedList 异同

参考

LinkedList 源码剖析（一）

LinkedList 源码剖析（二）