美文网首页
LinkedList源码分析

LinkedList源码分析

作者: 陈道乐 | 来源:发表于2020-01-16 22:28 被阅读0次

    LinkedList 是一个链式的数据存储结构, 不是线程安全的 , 不支持随机访问,可序列化,

    实现的接口

    从接口上看,并不支持随机访问的功能,实际上也没有插入的功能

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

    构造函数

        //链式存储的好处就在于,不用在构造时,初始化容量,
        public LinkedList() {
        }
    
        //构造时,初始化数据
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    

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

    数据链的操作

        //这是一个插入元素的操作,相比ArrayList的拷贝操作,性能高很多
        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++;
        }
        
        //这种查找优化方式,在链式存储结构中很常见,先判断节点的大概位置,再决定遍历方向
        Node<E> node(int index) {
            // assert isElementIndex(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;
            }
        }
        
        //释放节点
        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;
        }
    

    add

        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<E> newNode = new Node<>(pred, e, null);
                if (pred == null)
                    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;
        }
    

    remove

        //这两种方式,通过下标移除元素的方式是性能比较高。通过元素引用移除,是直接暴力的便利搞定的
        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));
        }
    

    clear

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

    set

        //链式结构在替换上性能没有顺序存储的性能高
        public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
    

    insert

        //这是一个插入方法,在性能上会比顺序存储高很多,毕竟没有扩容复制的问题
        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    

    Iterator

        //迭代器的便捷使用的类, 看起来很简单, 队列接口中使用的
        private class DescendingIterator implements Iterator<E> {
            private final ListItr itr = new ListItr(size());
            public boolean hasNext() {
                return itr.hasPrevious();
            }
            public E next() {
                return itr.previous();
            }
            public void remove() {
                itr.remove();
            }
        }
    
        //迭代器的操作其实,差不多,通过看构造函数,就能大概知道是如何实现的了
        private class ListItr implements ListIterator<E> {
            //最后一个被遍历到的节点元素,只有先被迭代器访问到的元素,才能修改
            private Node<E> lastReturned;
            private Node<E> next;
            private int nextIndex;
            
            //同样,也是不支持并发处理数据,这里已经做了修改记录
            private int expectedModCount = modCount;
    
            ListItr(int index) {
                // assert isPositionIndex(index);
                next = (index == size) ? null : node(index);
                nextIndex = index;
            }
    
            public boolean hasNext() {
                return nextIndex < size;
            }
    
            public E next() {
                checkForComodification();
                if (!hasNext())
                    throw new NoSuchElementException();
    
                lastReturned = next;
                next = next.next;
                nextIndex++;
                return lastReturned.item;
            }
    
            public boolean hasPrevious() {
                return nextIndex > 0;
            }
    
            public E previous() {
                checkForComodification();
                if (!hasPrevious())
                    throw new NoSuchElementException();
    
                lastReturned = next = (next == null) ? last : next.prev;
                nextIndex--;
                return lastReturned.item;
            }
    
            public int nextIndex() {
                return nextIndex;
            }
    
            public int previousIndex() {
                return nextIndex - 1;
            }
    
            public void remove() {
                checkForComodification();
                if (lastReturned == null)
                    throw new IllegalStateException();
    
                Node<E> lastNext = lastReturned.next;
                unlink(lastReturned);
                if (next == lastReturned)
                    next = lastNext;
                else
                    nextIndex--;
                lastReturned = null;
                expectedModCount++;
            }
    
            //看这个代码,只有之前被访问到,才能修改
            public void set(E e) {
                if (lastReturned == null)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.item = e;
            }
    
            public void add(E e) {
                checkForComodification();
                lastReturned = null;
                if (next == null)
                    linkLast(e);
                else
                    linkBefore(e, next);
                nextIndex++;
                expectedModCount++;
            }
    
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                while (modCount == expectedModCount && nextIndex < size) {
                    action.accept(next.item);
                    lastReturned = next;
                    next = next.next;
                    nextIndex++;
                }
                checkForComodification();
            }
    
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    

    相关文章

      网友评论

          本文标题:LinkedList源码分析

          本文链接:https://www.haomeiwen.com/subject/dipqzctx.html