Java数据结构源码分析-LinkedList

冷不防 2022-08-23 03:43 261阅读 0赞

## 1.LinkedList ##

LinkedList是通过双向链表来维护链表的顺序性。  
首先，我们看下类的构成，LinkedList通过两个iterator来顺序和倒序的访问数据。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ 
    
        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;
            }
        }
        //通过ListIterator来根据数据插入顺序访问元素
        private class ListItr implements ListIterator<E> { ...}
        //通过ListIterator来根据数据插入顺序的倒序访问元素
        private class DescendingIterator implements Iterator<E> { ...}
    }

## 2.LinkedList操作 ##

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ 
        transient Node<E> first;
        transient Node<E> last;
        //插入过程,通过不断的调用linkLast来构建双循环链表
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        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++;
       }
       //链表的删除过程，必须把每个节点的prev和next设置为空。
       public void clear() {
            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++;
      }
      //可以看到其本质的是clone了两份链表，只不过链表的item元素是引用复制，因此在后续clone的链表中加入新的item并不会影响clone前链表结构
      public Object clone() {
            LinkedList<E> clone = superClone();
    
            // Put clone into "virgin" state
            clone.first = clone.last = null;
            clone.size = 0;
            clone.modCount = 0;
    
            // Initialize clone with our elements
            for (Node<E> x = first; x != null; x = x.next)
                clone.add(x.item);
    
            return clone;
      }
      //Linked的支持化只需要持久化Linked的元素即可
      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);
      }
      //read同样只需要将每个持久化的元素取出来，重新构造链表即可
      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());
      }
      //Link的特点是可以快速的在first元素前插入元素
      public void push(E e) {
            addFirst(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;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
      }
      //Link的特点是可以快速的删除first元素
      public E pop() {
            return removeFirst();
      }
      public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(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;
      }
    
    }

同时LinkedList还继承了Queue的特性，其实现了要构造一个Queue的基本方法，其余的方法不再此赘述。