雙向鏈表

一個(gè)雙向鏈表有一個(gè)附加頭結(jié)點(diǎn)，由鏈表的頭指針first指示，它的data域或者不放數(shù)據(jù)，或者存放一個(gè)特殊要求的數(shù)據(jù)，
它的前驅(qū)指向鏈表的尾結(jié)點(diǎn)(即最后一個(gè)結(jié)點(diǎn))，它的后繼指向鏈表的首元結(jié)點(diǎn)(即第一個(gè)結(jié)點(diǎn))

雙向鏈表結(jié)點(diǎn)包含 前驅(qū)指針域，數(shù)據(jù)域，后繼指針域 三個(gè)部分

LinkedBlockingDeque部分源碼分析

public class LinkedBlockingDeque<E>
        extends AbstractQueue<E>
        implements BlockingDeque<E>, java.io.Serializable {
        
        //雙向鏈表的節(jié)點(diǎn) 
        static final class Node<E>{
            
            E item ;
            Node<E> prev;
            Node<E> next;
            
            Node(E x){
                item = x;
            }           
        }
    
    
        //一個(gè)鎖控制添加和消費(fèi)線程
        /** 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();
        
        //不指定大小，會(huì)默認(rèn)Integer.MAX_VALUE
        public LinkedBlockingDeque() {
            this(Integer.MAX_VALUE);
        }
        
        //初始化 有數(shù)據(jù)是往鏈表尾加 
        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;
            //如果第一個(gè)為空，node就是第一個(gè),否則表示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  后繼節(jié)點(diǎn)指向了自身，沒有別的節(jié)點(diǎn)引用，不會(huì)gc清楚
            first = n;
            if (n == null)//第一個(gè)節(jié)點(diǎn)的next是null，表示第一個(gè)節(jié)點(diǎn)也是尾節(jié)點(diǎn)，則last指向null; 否則修改前驅(qū)指向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的前驅(qū)是mull， 表示清除后就沒有節(jié)點(diǎn)了， first設(shè)置為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();
            }
        }
        
    }