LinkedBlockingDeque分析

双向链表

一个双向链表有一个附加头结点，由链表的头指针first指示，它的data域或者不放数据，或者存放一个特殊要求的数据，
它的前驱指向链表的尾结点(即最后一个结点)，它的后继指向链表的首元结点(即第一个结点)

双向链表结点包含 前驱指针域，数据域，后继指针域 三个部分

LinkedBlockingDeque部分源码分析

public class LinkedBlockingDeque<E>
        extends AbstractQueue<E>
        implements BlockingDeque<E>, java.io.Serializable {
        
        //双向链表的节点 
        static final class Node<E>{
            
            E item ;
            Node<E> prev;
            Node<E> next;
            
            Node(E x){
                item = x;
            }           
        }
    
    
        //一个锁控制添加和消费线程
        /** Main lock guarding all access */
        final ReentrantLock lock = new ReentrantLock();

        /** Condition for waiting takes */
        private final Condition notEmpty = lock.newCondition();

        /** Condition for waiting puts */
        private final Condition notFull = lock.newCondition();
        
        //不指定大小，会默认Integer.MAX_VALUE
        public LinkedBlockingDeque() {
            this(Integer.MAX_VALUE);
        }
        
        //初始化 有数据是往链表尾加 
        public LinkedBlockingDeque(Collection<? extends E> c) {
            this(Integer.MAX_VALUE);
            final ReentrantLock lock = this.lock;
            lock.lock(); // Never contended, but necessary for visibility
            try {
                for (E e : c) {
                    if (e == null)
                        throw new NullPointerException();
                    if (!linkLast(new Node<E>(e)))
                        throw new IllegalStateException("Deque full");
                }
            } finally {
                lock.unlock();
            }
        }
        
        
        // Links node as first element
        private boolean linkFirst(Node<E> node) {
            if (count >= capacity)
                return false;
            Node<E> f = first;
            node.next = f;
            first = node;
            //如果last为空，node就是last，否则f也就有值了，则f.prev = node;
            if (last == null)
                last = node;
            else
                f.prev = node;
            ++count;
            notEmpty.signal();
            return true;
        }
        
        
        //Links node as last element, or returns false if full
        private boolean linkLast(Node<E> node) {
            // assert lock.isHeldByCurrentThread();
            if (count >= capacity)
                return false;
            Node<E> l = last;
            node.prev = l;
            last = node;
            //如果第一个为空，node就是第一个,否则表示l也有值  则l.nexr = node
            if (first == null)
                first = node;
            else
                l.next = node;
            ++count;
            notEmpty.signal();
            return true;
        }
        
        
          /**
         * Removes and returns first element, or null if empty.
         */
        private E unlinkFirst() {
            // assert lock.isHeldByCurrentThread();
            Node<E> f = first;
            if (f == null)
                return null;
            Node<E> n = f.next;
            E item = f.item;
            f.item = null;
            f.next = f; // help GC  后继节点指向了自身，没有别的节点引用，不会gc清楚
            first = n;
            if (n == null)//第一个节点的next是null，表示第一个节点也是尾节点，则last指向null; 否则修改前驱指向null
                last = null;
            else
                n.prev = null;
            --count;
            notFull.signal();
            return item;
        }
        
        private E unlinkLast() {
        // assert lock.isHeldByCurrentThread();
            Node<E> l = last;
            if (l == null)
                return null;
            Node<E> p = l.prev;
            E item = l.item;
            l.item = null;
            l.prev = l; // help GC
            last = p;
            if (p == null) //last的前驱是mull， 表示清除后就没有节点了， first设置为null
                first = null;
            else
                p.next = null;
            --count;
            notFull.signal();
            return item;
        }
        
        void unlink(Node<E> x) {
        // assert lock.isHeldByCurrentThread();
            Node<E> p = x.prev;
            Node<E> n = x.next;
            if (p == null) {
                unlinkFirst();
            } else if (n == null) {
                unlinkLast();
            } else {
                p.next = n;
                n.prev = p;
                x.item = null;
                // Don't mess with x's links.  They may still be in use by
                // an iterator.
                --count;
                notFull.signal();
            }
        }
        
    }