LinkedList源码解析

男娘i 2021-09-25 06:24 571阅读 0赞

### LinkedList解析 ###

*  结构
 *   *  结构图
     *  类成员
     *   *  Node
     *  构造方法
     *  常用方法
     *  核心方法
     *   *  add\*\*\*
         *  addFirst
         *  addAll(\*\*\*)
         *  contains、indexOf
         *  remove(\*\*)
         *  set
         *  ArrayList 与 LinkedList

# 结构 #

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

## 结构图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MTYyMDkw_size_16_color_FFFFFF_t_70]  
相比对`ArrayList` 它多了 `Deque` 接口（双端队列接口），他是一个双端列表，可以从头遍历到尾，也可以从尾遍历到头，这取决于索引更靠近哪一端。(下面的方法是个很好的例子)

Node<E> node(int index)

*  Collection接口：所有集合类的根节点。
 *  List接口：Collection的子接口，它是一个元素有序、可重复、可以为null的集合
 *  AbstractCollection 类：Collection骨架实现类，实现了基本功能
 *  AbstractList类：List的骨架实现类，实现了List的基本功能。
 *  Cloneable接口：可克隆
 *  Serializable接口：序列化接口
 *  Deque：double ended queue 双端队列 接口。
 *  AbstractSequentialList类：提供了List接口的骨干实现，用于实现连续访问的存储结构（如链表）。对于随机访问的存储结构优先使用`AbstractList`

## 类成员 ##

// 长度
    transient int size = 0;
    
    /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) * 头结点指针(Node) */
    transient Node<E> first;
    
    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) * 尾节点指针(Node) */
    transient Node<E> last;

### Node ###

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

## 构造方法 ##

/** * Constructs an empty list. */
    public LinkedList() { 
    }
    
    /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */
    public LinkedList(Collection<? extends E> c) { 
        this();
        // addAll方法后续会介绍
        addAll(c);
    }

## 常用方法 ##

public int size() { 
        return size;
    }
    // 清空链表
    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
        // 将所有的值或属性设为 null 可以更好的被GC回收
        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++;
    }
    
    // 获取链表头结点 1
    public E peek() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    // 获取链表头结点 2
    public E element() { 
        return getFirst();
    }
    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;
    }
    // 移除头结点
    public E removeFirst() { 
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    // 移除头结点具体实现
    private E unlinkFirst(Node<E> f) { 
    	// assert 为断言
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        // 把节点内容和下个元素的引用 置为null
        f.item = null;
        f.next = null; // help GC 帮助GC更快的回收
        // 下个节点就变为 first节点
        first = next;
        // 如果头结点为null 意味着 这个链表都为null
        if (next == null)
            last = null;
        else
            // 下个节点的 上个元素引用设为null
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    // 移除尾节点
    public E removeLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    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;
    }
    
    //检索并删除这个列表的头(第一个元素)。
    public E poll() { 
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

## 核心方法 ##

> 由于LinkedList既实现了**List**接口，又实现了**Deque**接口，所以LinkedList既可以添加将元素添加到尾部，也可以将元素添加到指定索引位置，还可以添加添加整个集合；另外既可以在头部添加，又可以在尾部添加。

### add\*\*\* ###

/* * 末尾添加节点 */
    public boolean add(E e) { 
        // 在链表最后添加节点
        linkLast(e);
        return true;
    }
    
    // 在指定节点处添加节点
    public void add(int index, E element) { 
        // 判断是否越界
        checkPositionIndex(index);
        if (index == size)
            // 相等则在最后添加节点
            linkLast(element);
        else
            // 否则则在链表中间插入节点
            // node(index) 找到index所在的节点*
            linkBefore(element, node(index));
    }
    
    /** * Links e as last element. * 链表e作为最后一个元素 */
    void linkLast(E e) { 
        final Node<E> l = last;
        // 创建一个新节点
        // Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        // 如果原最后一个节点为null 也就是LinkedList为空
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        // 修改次数，在使用迭代器遍历时，会根据modCount==expectedModCount来判断是否在遍历过程中 其他线程产生了结构性修改，并抛出异常
        //https://www.jianshu.com/p/610c09274171 
        //https://segmentfault.com/q/1010000019216661
        modCount++;
    }
    
    /** * Inserts element e before non-null Node succ. * 在非空节点succ之前插入元素e */
    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++;
    }
    
    /** * Returns the (non-null) Node at the specified element index. * 返回指定元素索引处的(非空)节点 * 分成两部分 如果index 小于 size/2，从头结点开始遍历 * 否则，从尾节点开始遍历 * 这是为了提升性能。 */
    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;
        }
    }
    
    //下标检查
    private void checkPositionIndex(int index) { 
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) { 
        return index >= 0 && index <= size;
    }

### addFirst ###

// 头部添加节点
    public void addFirst(E e) { 
        linkFirst(e);
    }
    
    private void linkFirst(E e) { 
        final Node<E> f = first;
        // new Node<>(Node<E> prev, E element, Node<E> next)
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

### addAll(\*\*\*) ###

public boolean addAll(Collection<? extends E> c) { 
        return addAll(size, c);
    }
    
    // 在指定索引处插入集合
    public boolean addAll(int index, Collection<? extends E> c) { 
        // 判断是否越界
        checkPositionIndex(index);
    	// 把集合转成数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
    
        Node<E> pred, succ;
        // 如果index == size 就意味着 在链表尾部添加元素
        if (index == size) { 
            succ = null;
            pred = last;
        } else { 
            // node(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);
            // 如果前节点为null，那么newNode就为头节点
            if (pred == null)
                first = newNode;
            else
                // 否则添加到index对应的节点的next节点
                pred.next = newNode;
            // 赋值，下个循环从newNode开始
            pred = newNode;
        }
    
        if (succ == null) { 
            last = pred;
        } else { 
            // 双向绑定节点
            pred.next = succ;
            succ.prev = pred;
        }
    
        size += numNew;
        modCount++;
        return true;
    }
    
    // 根据index下标获取节点 
    // 这里运用了小技巧 减少遍历次数
    // 可以从头遍历到尾，也可以从尾遍历到头；这取决于看索引更靠近哪一端
    Node<E> node(int index) { 
        // assert isElementIndex(index);
        // size>>1 带符号右移 相当于除以2
        // 如果index < size/2 就从左边开始遍历
        if (index < (size >> 1)) { 
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        // 如果index > size/2 就从右边开始遍历
        } else { 
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

### contains、indexOf ###

// 是否包含某一项
    public boolean contains(Object o) { 
        return indexOf(o) != -1;
    }
    
    // 顺序查找
    public int indexOf(Object o) { 
        int index = 0;
        if (o == null) { 
        	// 遍历寻找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) { 
                // 注意是equals
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
    
    // 逆序查找
    public int lastIndexOf(Object o) { 
        int index = size;
        if (o == null) { 
            for (Node<E> x = last; x != null; x = x.prev) { 
                index--;
                if (x.item == null)
                    return index;
            }
        } else { 
            for (Node<E> x = last; x != null; x = x.prev) { 
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

### remove(\*\*) ###

public boolean remove(Object o) { 
        // 如果o为null
        if (o == null) { 
            // 循环链表
            for (Node<E> x = first; x != null; x = x.next) { 
                if (x.item == null) { 
                    // 移除这个元素,去除链表关系
                    unlink(x);
                    return true;
                }
            }
        } else { 
            // 如果o不为null
            for (Node<E> x = first; x != null; x = x.next) { 
                // 通过 equals 去比较
                if (o.equals(x.item)) { 
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    
    // 从链表中移除此节点（***）
    // 画个图更好理解
    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，则把上个节点的 next 指针指向 此节点的 下一个节点
            prev.next = next;
            // 此节点的 prev 置为null
            x.prev = null;
        }
    	
        // 如果此节点的 下一个节点为null （此节点为尾节点）
        if (next == null) { 
            // 此节点的上一节点为 链表的last节点
            last = prev;
        } else { 
            // 如果此节点的 下一个节点不为null
            // 那么此节点的下一个节点的prev指针指向 此节点的上节点
            next.prev = prev;
            // 此节点的next置为null
            x.next = null;
        }
    	// 此节点置为null
        x.item = null;
        // size 减一
        size--;
        modCount++;
        return element;
    }

### set ###

public E set(int index, E element) { 
        // 检查下标
        checkElementIndex(index);
        // 根据下标获取节点
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        // 返回被替换的旧值
        return oldVal;
    }

### ArrayList 与 LinkedList ###

ArrayList:

*  ArrayList实现了`RandomAccess`接口，使用**For循环**效率更高
 *  底层是**数组**实现，所以**查询**效率会更快

LinkedList:

*  没有实现`RandomAccess`接口，使用**迭代器**循环效率更高
 *  底层是**双向链表**，所以**新增与删除**更为方便
 *  所消耗的内存也更多
 *  可以作为**栈**、和**队列**使用。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MTYyMDkw_size_16_color_FFFFFF_t_70]: /images/20210923/ba86df3eef5049b7909e12213be7d521.png