Java集合-LinkedList源码解析-JDK1.8

￡神魔★判官ぃ 2024-04-18 20:25 83阅读 0赞

◆

LinkedList简介

◆

它继承于AbstractList，实现了List、 RandomAccess、Cloneable、Serializable这些接口。

1.  AbstractSequentialList提供了可以被当作堆栈、队列或双端队列的机制
2.  List 接口提供了基本的增删改查
3.  Deque 接口提供了双端队列机制
4.  Cloneable提供了可以被克隆的功能
5.  Serializable提供了序列化的功能
6.  同ArrayList，LinkedList也不是线程安全的

◆

LinkedList的属性

◆

//List的大小	
        transient int size = 0;	
        /**	
         * 链表头部	
         */	
        transient Node<E> first;	
        /**	
         * 链表尾部	
         */	
        transient Node<E> last;	
        /**	
         *  特别注意这个是继承自AbstractList的属性，用来记录List被修改的次数	
         */	
        protected transient int modCount = 0;

相比较于ArrayList使用数组作为缓冲区，LinkedList使用的是一个内部的静态类Node来保存的，每个Node节点不光记录本身的数据，还保留了前一个节点和后一个节点的引用。所以本身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构造方法

◆

/**	
         * 默认构造方法	
         */	
        public LinkedList() {	
        }	
          /**	
         * 添加一个集合	
         */	
        public LinkedList(Collection<? extends E> c) {	
            this();	
            addAll(c);	
        }	
         /**	
         * 添加一个集合	
         */	
        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;	
            if (index == size) {	
                //从链表尾部添加	
                succ = null;	
                pred = last;	
            } else {	
                //从链表中间添加	
                succ = node(index);	
                pred = succ.prev;	
            }	
    
    	
            for (Object o : a) {	
                @SuppressWarnings("unchecked") E e = (E) o;	
                //创建Node节点，指定Node的前一个节点	
                Node<E> newNode = new Node<>(pred, e, null);	
                if (pred == null)	
                    //pred如果为空则代表整个链表为空，	
                    first = newNode;	
                else	
                    pred.next = newNode;	
                pred = newNode;	
            }	
    
    	
            if (succ == null) {	
                //将节点放到最后	
                last = pred;	
            } else {	
                //将节点插入	
                pred.next = succ;	
                succ.prev = pred;	
            }	
            //更新链表大小	
            size += numNew;	
            //更新修改次数	
            modCount++;	
            return true;	
        }

◆

LinkedList的基本方法

◆

addAll方法添加一个集合还是比较简单粗暴的，接下来我们来看一下普通的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	
                linkBefore(element, node(index));	
        }	
         /**	
         * 添加第一个节点	
         */	
        public void addFirst(E e) {	
            linkFirst(e);	
        }	
        /**	
         * 添加最后一个节点	
         */	
        public void addLast(E e) {	
            linkLast(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++;	
        }	
         /**	
         * 在succ节点之前插入一个节点	
         */	
        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++;	
        }

LinkedList不仅有普通的add方法，鉴于双向链表的特殊性，它还包含以下方法：

/**	
         * 往最后添加一个元素	
         */	
        public boolean offer(E e) {	
            return add(e);	
        }	
    
    	
        // Deque operations	
        /**	
         * 往第一个位置添加元素	
         */	
        public boolean offerFirst(E e) {	
            addFirst(e);	
            return true;	
        }	
    
    	
        /**	
         * 往最后一个位置添加元素	
         */	
        public boolean offerLast(E e) {	
            addLast(e);	
            return true;	
        }	
          /**	
         * 往List头部添加元素	
         */	
        public void push(E e) {	
            addFirst(e);	
        }

修改方法：

/**	
         * 将指定索引的元素替换	
         */	
        public E set(int index, E element) {	
            checkElementIndex(index);	
            Node<E> x = node(index);	
            E oldVal = x.item;	
            x.item = element;	
            return oldVal;	
        }

删除方法：

/**	
         * 删除第一个节点	
         */	
        public E removeFirst() {	
            final Node<E> f = first;	
            if (f == null)	
                throw new NoSuchElementException();	
            return unlinkFirst(f);	
        }	
    
    	
        /**	
         * 删除最后一个节点	
         */	
        public E removeLast() {	
            final Node<E> l = last;	
            if (l == null)	
                throw new NoSuchElementException();	
            return unlinkLast(l);	
        }	
         /**	
         * 删除元素	
         */	
        public boolean remove(Object o) {	
            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;	
        }	
        /**	
         * 删除节点	
         */	
        public E remove(int index) {	
            checkElementIndex(index);	
            return unlink(node(index));	
        }	
          /**	
         * 删除第一个元素	
         */	
        public E remove() {	
            return removeFirst();	
        }	
         /**	
         * 删除顺序遍历到的第一个存在的元素	
         */	
        public boolean removeFirstOccurrence(Object o) {	
            return remove(o);	
        }	
    
    	
        /**	
         * 删除逆序遍历到的最后一个存在的元素	
         */	
        public boolean removeLastOccurrence(Object o) {	
            if (o == null) {	
                for (Node<E> x = last; x != null; x = x.prev) {	
                    if (x.item == null) {	
                        unlink(x);	
                        return true;	
                    }	
                }	
            } else {	
                for (Node<E> x = last; x != null; x = x.prev) {	
                    if (o.equals(x.item)) {	
                        unlink(x);	
                        return true;	
                    }	
                }	
            }	
            return false;	
        }	
    
    	
       /**	
         * 删除第一个节点	
         */	
        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;	
            f.next = null; // help GC	
            first = next;	
            if (next == null)	
                last = null;	
            else	
                next.prev = null;	
            size--;	
            modCount++;	
            return element;	
        }	
    
    	
        /**	
         * 删除最后一个节点	
         */	
        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;	
        }	
    
    	
        /**	
         * 删除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;	
            }	
    
    	
            if (next == null) {	
                last = prev;	
            } else {	
                next.prev = prev;	
                x.next = null;	
            }	
    
    	
            x.item = null;	
            size--;	
            modCount++;	
            return element;	
        }

查询方法：

/**	
         * 获取第一个节点	
         */	
        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 get(int index) {	
            //判断是否越界	
            checkElementIndex(index);	
            return node(index).item;	
        }	
    
    	
       /**	
         * 获取第一个元素	
         */	
        public E peek() {	
            final Node<E> f = first;	
            return (f == null) ? null : f.item;	
        }	
    
    	
       /**	
         * 获取第一个元素	
         */	
        public E element() {	
            return getFirst();	
        }	
    
    	
        /**	
         * 弹出第一个元素（删除并获取）	
         */	
        public E poll() {	
            final Node<E> f = first;	
            return (f == null) ? null : unlinkFirst(f);	
        }	
    
    	
      /**	
         * 获取第一个元素	
         */	
        public E peekFirst() {	
            final Node<E> f = first;	
            return (f == null) ? null : f.item;	
        }	
        /**	
         * 获取最后一个元素	
         */	
        public E peekLast() {	
            final Node<E> l = last;	
            return (l == null) ? null : l.item;	
        }	
     	
      /**	
         * 弹出第一个元素（删除并获取）	
         */	
        public E pollFirst() {	
            final Node<E> f = first;	
            return (f == null) ? null : unlinkFirst(f);	
        }	
    
    	
      /**	
         * 弹出最后一个元素（删除并获取）	
         */	
        public E pollLast() {	
            final Node<E> l = last;	
            return (l == null) ? null : unlinkLast(l);	
        }	
    
    	
     /**	
         *	
         * 弹出第一个元素（删除并获取）	
         */	
        public E pop() {	
            return removeFirst();	
        }

**看了LinkedList的增删改查方法相信你已经明白了为什么一直有人告诉你LinkedList添加和删除效率高而随机查询修改效率低了。**

序列化

/**	
         * 将List写入s，注意先写容量，然后在写数据	
         */	
        private void writeObject(java.io.ObjectOutputStream s)	
                throws java.io.IOException {	
            // Write out any hidden serialization magic	
            s.defaultWriteObject();	
    
    	
            // Write out size	
            s.writeInt(size);	
    
    	
            // Write out all elements in the proper order.	
            for (Node<E> x = first; x != null; x = x.next)	
                s.writeObject(x.item);	
        }	
    
    	
        /**	
         * 从s读取，先读容量，再读数据	
         */	
        @SuppressWarnings("unchecked")	
        private void readObject(java.io.ObjectInputStream s)	
                throws java.io.IOException, ClassNotFoundException {	
            // Read in any hidden serialization magic	
            s.defaultReadObject();	
    
    	
            // Read in size	
            int size = s.readInt();	
    
    	
            // Read in all elements in the proper order.	
            for (int i = 0; i < size; i++)	
                linkLast((E)s.readObject());	
        }

鉴于篇幅有限，本篇文章仅列出上方部分代码，LinkedList完整源码解析请点击下方“阅读原文”查看！！！

![640?wx\_fmt=gif][640_wx_fmt_gif]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

收藏转发好看再走呗!

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/eccf3d31474a47d68a84969818c61698.gif
[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c9797c5977314025aaea17c718e3e17e.png
[640_wx_fmt_gif 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5c5d57c626d145ef91b07764e9f7178d.gif