LinkedList源码解析（JDK8）

偏执的太偏执、 2023-09-25 12:38 96阅读 0赞

#### 文章目录 ####

*  一、LinkedList继承体系
 *  二、LinkedList属性
 *  三、Node内部类
 *  四、构造方法
 *  五、添加元素
 *   *  1、头部添加
     *  2、尾部添加
     *  3、指定位置添加
 *  六、删除元素
 *   *  1、头部删除
     *  2、尾部删除
     *  3、指定位置删除
 *  七、修改元素

--------------------

加油，不要过度焦虑(\#^.^\#)

--------------------

## 一、LinkedList继承体系 ##

**LinkedList**：LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用。在分析源码之前，前提是我们应该掌握链表这一块的知识。

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

从源码可以看出，LinkedList实现了Cloneable和Serializable接口，说明其可以被克隆，也可以被序列化！同样的，LinkedList被克隆的时候，和ArrayList一样二者均是浅拷贝。实现了Deque接口，说明支持两端的元素插入和移除；继承了AbstractSequentialList类，说明支持按次序访问！

来看看LinkedList的继承体系图：

![在这里插入图片描述][971770cea716496e910c80223e24f8e7.png]

--------------------

## 二、LinkedList属性 ##

//链表的元素个数
     	transient int size = 0;
        /**
         * 指向第一个节点，即头节点
         * Pointer to first node.
         */
        transient Node<E> first;
        /**
         * 指向第二个节点，即尾结点
         * Pointer to last node.
         */
        transient Node<E> last;

前提是一定学习过双向链表的知识！

--------------------

## 三、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;
            }
        }

--------------------

## 四、构造方法 ##

**空参构造：**

/**
         * 构造一个空的list
         * Constructs an empty list.
         */
        public LinkedList() {
        
        }

**参数是一个Collection的有参构造：**

/**
         * 构造一个包含指定collection的list，这些元素按collection的迭代顺序依次返回
         * 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(c);
        }
        /**
         * 添加指定集合中的所有元素到list的末尾
         * Appends all of the elements in the specified collection to the end of
         * this list, in the order that they are returned by the specified
         * collection's iterator.  The behavior of this operation is undefined if
         * the specified collection is modified while the operation is in
         * progress.  (Note that this will occur if the specified collection is
         * this list, and it's nonempty.)
         *
         * @param c collection containing elements to be added to this list
         * @return {@code true} if this list changed as a result of the call
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(Collection<? extends E> c) {
        
            return addAll(size, c);
        }
        /**
         * 从指定位置开始，插入指定collection的所有元素到list
         * Inserts all of the elements in the specified collection into this
         * list, starting at the specified position.  Shifts the element
         * currently at that position (if any) and any subsequent elements to
         * the right (increases their indices).  The new elements will appear
         * in the list in the order that they are returned by the
         * specified collection's iterator.
         *
         * @param index index at which to insert the first element
         *              from the specified collection
         * @param c collection containing elements to be added to this list
         * @return {@code true} if this list changed as a result of the call
         * @throws IndexOutOfBoundsException {@inheritDoc}
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(int index, Collection<? extends E> c) {
        
        	//首先检查index下标是否越界
            checkPositionIndex(index);
            //把c转换为数组
            Object[] a = c.toArray();
            int numNew = a.length;
            //当c无元素时，则不用插入
            if (numNew == 0)
                return false;
            Node<E> pred, succ;
            //如果要插入的索引index在list的末尾
            if (index == size) {
        
                succ = null;//则让succ节点置为null
                pred = last;//则让predict节点指向list的最后一个位置
            } else {
        
                succ = node(index);//让succ节点指向索引为index位置的节点
                pred = succ.prev;//succ的前驱指向pred
            }
            for (Object o : a) {
        
                @SuppressWarnings("unchecked") E e = (E) o;
                Node<E> newNode = new Node<>(pred, e, null);//创建新节点，前驱指向pred，后驱为null
                if (pred == null)// 如果前驱为null说明当前节点位于该链表的头节点
                    first = newNode;// 使头节点指向新创建的节点
                else
                    pred.next = newNode;// 让pred的后继指向新节点
                pred = newNode;// 让pred指向新节点
            }
            if (succ == null) {
        // 这种情况说明index索引位于原始链表的最后
                last = pred;// 尾节点直接指向拼接完成后链表的最后，因为前面已经执行过pred = newNode;
            } else {
        
                pred.next = succ;// pred的后继节点指向succ
                succ.prev = pred;// succ的前驱节点指向pred
            }
            size += numNew;
            modCount++;
            return true;
        }
        /**
         * 寻找index位置的节点并返回
         * Returns the (non-null) Node at the specified element index.
         */
    	Node<E> node(int index) {
        
    	    if (index < (size >> 1)) {
        // 如果该索引位于链表元素的前一半（太牛了）
    	        Node<E> x = first;// 从头节点开始遍历定位index的位置
    	        for (int i = 0; i < index; i++)
    	            x = x.next;// 指针移动到index位置
    	        return x;// 将该节点内容返回
    	    } else {
        // 如果该索引位于链表元素的后一半
    	        Node<E> x = last;// 从尾节点开始倒序遍历定位index的位置
    	        for (int i = size - 1; i > index; i--)
    	            x = x.prev;// 指针移动到index位置
    	        return x;// 将该节点内容返回
    	    }
    	}
        private void checkPositionIndex(int index) {
        
        	//下标越界则抛出异常
           if (!isPositionIndex(index))
               throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
       }
        /**
         * Tells if the argument is the index of a valid position for an
         * iterator or an add operation.
         */
        private boolean isPositionIndex(int index) {
        
        	//index在[0,size]内则不越界
            return index >= 0 && index <= size;
        }

--------------------

## 五、添加元素 ##

### 1、头部添加 ###

自己画图尝试一下就明白了：

/**
         * e作为第一个元素
         * Links e as first element.
         */
        private void linkFirst(E e) {
        
            final Node<E> f = first; //让f指向首节点
            final Node<E> newNode = new Node<>(null, e, f);//创建新节点，新节点的next指向首节点，前驱为null
            first = newNode;//让新的节点作为首节点
            if (f == null)//判断list中是否有元素
                last = newNode;//是，则把last也设置为新节点（即此时list中只有一个节点，首节点、尾结点都是它）
            else
                f.prev = newNode;//不是则把元首节点的前驱置位新节点
            size++;//元素个数加1
            modCount++;//修改次数加1
        }

### 2、尾部添加 ###

/**
         * e作为最后一个元素
         * Links e as last element.
         */
        void linkLast(E e) {
        
            final Node<E> l = last;//让l指向最后的节点
            final Node<E> newNode = new Node<>(l, e, null);//添加一个新节点，前驱指向list的最后一个节点
            last = newNode;//让新节点成为最后一个节点
            if (l == null)//判断list时候有元素
                first = newNode;//没有则让新节点也为首节点
            else
                l.next = newNode;//有则让l的next指向新节点
            size++;
            modCount++;
        }

### 3、指定位置添加 ###

/**
         * Inserts the specified element at the specified position in this list.
         * Shifts the element currently at that position (if any) and any
         * subsequent elements to the right (adds one to their indices).
         *
         * @param index index at which the specified element is to be inserted
         * @param element element to be inserted
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public void add(int index, E element) {
        
        	//检查下标index是否越界
            checkPositionIndex(index);
            //如果在末尾插入
            if (index == size)
                linkLast(element);//是则按尾部添加
            else
                linkBefore(element, node(index));//不是则
        }
        // 寻找index位置的节点并返回
    	Node<E> node(int index) {
        
    	    if (index < (size >> 1)) {
        // 如果该索引位于链表元素的前一半（太牛了）
    	        Node<E> x = first;// 从头节点开始遍历定位index的位置
    	        for (int i = 0; i < index; i++)
    	            x = x.next;// 指针移动到index位置
    	        return x;// 将该节点内容返回
    	    } else {
        // 如果该索引位于链表元素的后一半
    	        Node<E> x = last;// 从尾节点开始倒序遍历定位index的位置
    	        for (int i = size - 1; i > index; i--)
    	            x = x.prev;// 指针移动到index位置
    	        return x;// 将该节点内容返回
    	    }
    	}
         /**
         * 在非null的succ节点之前添加元素e
         * Inserts element e before non-null Node succ.
         */
        void linkBefore(E e, Node<E> succ) {
        
            final Node<E> pred = succ.prev;//pred指向succ的前驱
            final Node<E> newNode = new Node<>(pred, e, succ);//创建新的节点，前驱是pred，后继是succ
            succ.prev = newNode;//让succ的前驱指向新节点
            if (pred == null)//判断succ前面节点是否存在元素
                first = newNode;//不存在则让新节点成为头节点
            else
                pred.next = newNode;//存在则让pred的后继指向新节点，就实现了插入成功
            size++;
            modCount++;
        }

有点迷惑的一定要画画图呀，画画图就弄懂了~

## 六、删除元素 ##

### 1、头部删除 ###

/**
         * 从这个list中移除并返回第一个元素
         * Removes and returns the first element from this list.
         *
         * @return the first element from this list
         * @throws NoSuchElementException if this list is empty
         */
        public E removeFirst() {
        
            final Node<E> f = first;//让f节点指向first
            if (f == null)//判断list中是否存在元素
                throw new NoSuchElementException();//没有元素则抛出异常
            return unlinkFirst(f);
        }
        /**
         * Unlinks non-null first node f.
         */
        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;//让首节点的item是null（前面已经用element存放它的数值了）
            f.next = null; //让首节点的后继为null，这些操作都是为了帮助jvm实现垃圾回收
            first = next;//让list的首节点指向next（即原本list的第二个节点）
            if (next == null)//判断原本list是否有第二个节点
                last = null;//没有则list置为null，list此时无元素
            else
                next.prev = null;//有则让原本list的第二个节点的前驱为null，这样就变成了头节点
            size--;
            modCount++;
            return element;//返回删除的元素
        }

### 2、尾部删除 ###

这些分析其实跟首部删除差不多

/**
         * 移除此list的最后一个元素并返回
         * Removes and returns the last element from this list.
         *
         * @return the last element from this list
         * @throws NoSuchElementException if this list is empty
         */
        public E removeLast() {
        
            final Node<E> l = last;//用l记录list的最后一个元素
            if (l == null)
                throw new NoSuchElementException();//list此时没有元素则抛出异常
            return unlinkLast(l);
        }
         /**
         * Unlinks non-null last node l.
         */
        private E unlinkLast(Node<E> l) {
        
            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null; // 帮助垃圾回收
            last = prev;//让prev成为最后的节点
            if (prev == null)//判断list此时是否还有元素
                first = null;//没有则让first置为null，此时首尾节点都是null
            else
                prev.next = null;//有则让prev（原本list的倒数第二个节点）的后继为null
            size--;
            modCount++;
            return element;
        }

### 3、指定位置删除 ###

/**
         * 移除list指定位置的元素
         * Removes the element at the specified position in this list.  Shifts any
         * subsequent elements to the left (subtracts one from their indices).
         * Returns the element that was removed from the list.
         *
         * @param index the index of the element to be removed
         * @return the element previously at the specified position
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E remove(int index) {
        
        	//检查数组下标是否越界
            checkElementIndex(index);
            //node()方法就不再次解释了
            return unlink(node(index));
        }
        /**
         * Unlinks non-null node x.
         */
        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;//并把当前节点的前驱节点置为null，方便垃圾回收
            }
            if (next == null) {
        //此时为尾结点
                last = prev;//则让尾结点指向当前节点的前驱节点
            } else {
        
                next.prev = prev;//不为尾结点，则让当前节点的后继节点的前驱节点指向当前节点的前驱节点，最后实现了删除当前节点
                x.next = null;//方便垃圾回收
            }
            x.item = null;//方便垃圾回收
            size--;
            modCount++;
            return element;//返回element
        }

## 七、修改元素 ##

看完了前面的所有操作，修改元素就变得很简单了

/**
         * 用执行元素替换list中指定位置的元素（好多定语从句，哈哈~）
         * Replaces the element at the specified position in this list with the
         * specified element.
         *
         * @param index index of the element to replace
         * @param element element to be stored at the specified position
         * @return the element previously at the specified position
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E set(int index, E element) {
        
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }

--------------------

到此结束，感谢阅读(～￣▽￣)～

--------------------

[971770cea716496e910c80223e24f8e7.png]: https://img-blog.csdnimg.cn/971770cea716496e910c80223e24f8e7.png