JDK1.8源码分析：LinkedList

￡神魔★判官ぃ 2022-03-20 05:50 335阅读 0赞

### 接口和数据结构 ###

*  LinkedList，实现了List和Deque接口，其中Deque是双向队列，即可以在队列头部和尾部进行插入或删除数据节点。LinkedList也不是线程安全的。
    
        public class LinkedList<E>
            extends AbstractSequentialList<E>
            implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 *  LinkedList为了实现以上功能，在内部使用了双向链表这种数据结构。数据结构定义如下：
    
        // 链表长度
        transient int size = 0;
            /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
        transient Node<E> first;
        
        /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
        transient Node<E> last;
        
        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;
            }
        }
    
    Node为链表节点，item为进行数据存放，类型为泛型E；pref和next分别为当前链表节点的前后节点。

### 链表指定位置操作 ###

*  对链表指定位置操作，是通过指定某个索引，类似于数组下标，来获取指定位置的数据。核心实现为提供了一个node(index)的方法来查找index对应的链表节点，如get，set为例：
    
        public E get(int index) { 
            checkElementIndex(index);
            return node(index).item;
        }
        /** * 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;
        }
        
        
        /** * Returns the (non-null) Node at the specified element index. */
        Node<E> node(int index) { 
            // assert isElementIndex(index);
        
            // index在前半部分，则从头开始查找
            if (index < (size >> 1)) { 
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            // index在后半部分，则从尾部开始查找
            } else { 
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    node方法主要利用了头部，尾部指针和链表长度size，对于给定的index，如果在链表前半部分，则直接头部开始查找，如果在链表后半部分，则从尾部指针往前查找，从而可以减少遍历次数，提高性能。

### 链表头部操作 ###

*  链表头部操作是指相对于内部的双向链表的头结点进行操作，具体为增删查改。
    
        public E getFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
        
        public E removeFirst() { 
            final Node<E> f = first;
            if (f == null)
                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;
            f.next = null; // help GC
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
        
        public void addFirst(E e) { 
            linkFirst(e);
        }   
        
        // 在链表头部插入节点
        /** * Links e as first element. */
        private void linkFirst(E e) { 
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
        
        // 获取头部节点
        public E peek() { 
            final Node<E> f = first;
            return (f == null) ? null : f.item;
        }
        // poll和remove都是获取并删除头部节点
        // 还有pollFirst，pollLast版本的方法
        public E poll() { 
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
        public E remove() { 
            return removeFirst();
        }
        
        public void push(E e) { 
            addFirst(e);
        }
        public E pop() { 
            return removeFirst();
        }

### 链表尾部操作 ###

*  链表尾部操作是指相对于内部的双向链表的尾部结点进行操作，具体为增删查改。
    
        public E getLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
        
        public E removeLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
          
        // add和addLast都是在链表尾部添加元素 
        public void addLast(E e) { 
            linkLast(e);
        } 
        public boolean add(E e) { 
            linkLast(e);
            return true;
        }
        
        // 在链表尾插入节点
        /** * Links e as last element. */
        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++;
        }
        
        // 在尾部添加节点
        // 还有offerFirst，offerLast版本的方法
        public boolean offer(E e) { 
            return add(e);
        }

### 链表长度size ###

*  在LinkedList中也使用了一个size来维护当前链表的长度，在添加或删除链表节点时，同步更新该size的值，从而可以直接返回该size变量来获取该链表当前存在多少元素。
    
        public int size() { 
            return size;
        }

### 清空链表 ###

*  将链表内所有节点置null，头部和尾部节点置null，从而可以让GC回收。
    
        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
            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++;
        }