`
hougechuanqi
  • 浏览: 73167 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

LinkedList实现原理分析

 
阅读更多

package org.jgroups.util;


import org.jgroups.logging.Log;
import org.jgroups.logging.LogFactory;
import org.jgroups.TimeoutException;

import java.util.*;


/**
 * 这个东西是jgroups开发团队写的一个LinkedList实现，基本原理就是对象之间参考引用实现队列。
 */
public class Queue {

    /*head and the tail of the list so that we can easily add and remove objects*/
/**
* 队列头部和尾部的元素，我们可以很容易的来添加和移除对象
*/
    private Element head=null, tail=null;

    /*flag to determine the state of the queue
     * 队列的状态，查看队列是否被关闭
     * */
    private volatile boolean closed=false;

    /*current size of the queue*/
    /**
     * 队列的长度
     */
    private volatile int size=0;

    /* Lock object for synchronization. Is notified when element is added */
    /**
     * 同步锁对象，当新增对象到队列里面会触发通知事件,声明为final表示该对象是线程安全的
     */
    private final Object  mutex=new Object();

    /** Lock object for syncing on removes. It is notified when an object is removed */
    // Object  remove_mutex=new Object();

    /*the number of end markers that have been added*/
    
    /**
     * 结束标记
     */
    private int     num_markers=0;

    /**
     * if the queue closes during the runtime
     * an endMarker object is added to the end of the queue to indicate that
     * the queue will close automatically when the end marker is encountered
     * This allows for a "soft" close.
     * @see Queue#close
     */
    private static final Object endMarker=new Object();

    protected static final Log log=LogFactory.getLog(Queue.class);


    /**
     * the class Element indicates an object in the queue.
     * This element allows for the linked list algorithm by always holding a
     * reference to the next element in the list.
     * if Element.next is null, then this element is the tail of the list.
     * 队列里面的元素，其中一个元素会持有下一个元素参考，如果下一个为空，说明这个元素就是最后一个。
     */
    static class Element {
        /*the actual value stored in the queue
         * 该元素对象的属性
         * */
        Object  obj=null;
        /*pointer to the next item in the (queue) linked list
         * 引用的下一个元素
         * */
        Element next=null;

        /**
         * creates an Element object holding its value
         * 初始化函数，初始化元素构造器
         * @param o - the object to be stored in the queue position
         */
        Element(Object o) {
            obj=o;
        }

        /**
         * prints out the value of the object
         * toString()函数
         * 
         */
        public String toString() {
            return obj != null? obj.toString() : "null";
        }
    }


    /**
     * creates an empty queue
     */
    public Queue() {
    }


    /**
     * Returns the first element. Returns null if no elements are available.
     * 返回队列里面的第一个元素
     */
    public Object getFirst() {
        synchronized(mutex) {//加一个同步锁机制
            return head != null? head.obj : null;
        }
    }

    /**
     * Returns the last element. Returns null if no elements are available.
     * 返回队列的最后一个元素
     */
    public Object getLast() {
        synchronized(mutex) {//返回最后一个元素
            return tail != null? tail.obj : null;
        }
    }


    /**
     * returns true if the Queue has been closed
     * however, this method will return false if the queue has been closed
     * using the close(true) method and the last element has yet not been received.
     * 检查队列是否被关闭，如果关闭返回true
     * @return true if the queue has been closed
     */
    public boolean closed() {
        synchronized(mutex) {
            return closed;
        }
    }

    /**
     * adds an object to the tail of this queue
     * If the queue has been closed with close(true) no exception will be
     * thrown if the queue has not been flushed yet.
     * 向队列尾部加入一个元素
     * @param obj - the object to be added to the queue
     * @exception QueueClosedException exception if closed() returns true
     */
    public void add(Object obj) throws QueueClosedException {
        if(obj == null) {
            if(log.isErrorEnabled()) log.error("argument must not be null");
            return;
        }

        /*lock the queue from other threads*/
        synchronized(mutex) {
           if(closed)
              throw new QueueClosedException();
           if(this.num_markers > 0)
              throw new QueueClosedException("queue has been closed. You can not add more elements. " +
                                             "Waiting for removal of remaining elements.");
            addInternal(obj);

            /*wake up all the threads that are waiting for the lock to be released
             * 提示所有的线程，同步锁被释放了，可以争夺资源了。
             * */
            mutex.notifyAll();
        }
    }

    /**
     * 向尾部加入一个集合
     * @param c
     * @throws QueueClosedException
     */
    public void addAll(Collection c) throws QueueClosedException {
        if(c == null) {
            if(log.isErrorEnabled()) log.error("argument must not be null");
            return;
        }

        /*lock the queue from other threads*/
        synchronized(mutex) {
           if(closed)
              throw new QueueClosedException();
           if(this.num_markers > 0)
              throw new QueueClosedException("queue has been closed. You can not add more elements. " +
                                             "Waiting for removal of remaining elements.");

            Object obj;
            for(Iterator it=c.iterator(); it.hasNext();) {//循环向队列尾部添加元素
                obj=it.next();
                if(obj != null)
                    addInternal(obj);
            }

            /*wake up all the threads that are waiting for the lock to be released*/
            /**
             * 唤醒其他线程，可以争夺资源了同步锁已经被释放了
             */
            mutex.notifyAll();
        }
    }


    /**
     * 添加一个List集合
     * @param list
     * @throws QueueClosedException
     */
    public void addAll(List<Object> list) throws QueueClosedException {
        if(list == null) {
            if(log.isErrorEnabled()) log.error("argument must not be null");
            return;
        }

        /*lock the queue from other threads*/
        synchronized(mutex) {
           if(closed)
              throw new QueueClosedException();
           if(this.num_markers > 0)
              throw new QueueClosedException("queue has been closed. You can not add more elements. " +
                                             "Waiting for removal of remaining elements.");

            for(Object obj: list) {
                if(obj != null)
                    addInternal(obj);
            }

            /*wake up all the threads that are waiting for the lock to be released*/
            mutex.notifyAll();
        }
    }




    /**
     * 从队列里面移除首元素
     * Removes 1 element from head or <B>blocks</B>
     * until next element has been added or until queue has been closed
     * @return the first element to be taken of the queue
     */
    public Object remove() throws QueueClosedException {
        Object retval;
        synchronized(mutex) {
            /*wait as long as the queue is empty. return when an element is present or queue is closed*/
            while(size == 0) {
                if(closed)
                    throw new QueueClosedException();
                try {
                    mutex.wait();
                }
                catch(InterruptedException ex) {
                }
            }

            if(closed)
                throw new QueueClosedException();

            /*remove the head from the queue, if we make it to this point, retval should not be null !*/
            retval=removeInternal();
            if(retval == null)
                if(log.isErrorEnabled()) log.error("element was null, should never be the case");
        }

        /*
         * we ran into an Endmarker, which means that the queue was closed before
         * through close(true)
         */
//        if(retval == endMarker) {
//            close(false); // mark queue as closed
//            throw new QueueClosedException();
//        }
        return retval;
    }


    /**
     * 带超时时间的移除首元素操作
     * Removes 1 element from the head.
     * If the queue is empty the operation will wait for timeout ms.
     * if no object is added during the timeout time, a Timout exception is thrown
     * (bela Aug 2009) Note that the semantics of remove(long timeout) are weird - the method waits until an element has
     * been added, but doesn't do so in a loop ! So if we have 10 threads waiting on an empty queue, and 1 thread
     * adds an element, all 10 threads will return (but only 1 will have the element), therefore 9 will throw
     * a TimeoutException ! If I change this to the 'correct' semantics, however (e.g. the method removeWait() below),
     * GMS.ViewHandler doesn't work correctly anymore. I won't change this now, as Queue will get removed anyway in 3.0.
     * @param timeout - the number of milli seconds this operation will wait before it times out
     * @return the first object in the queue
     */
    public Object remove(long timeout) throws QueueClosedException, TimeoutException {
        Object retval;

        synchronized(mutex) {
            if(closed)
                throw new QueueClosedException();

            /*if the queue size is zero, we want to wait until a new object is added*/
            if(size == 0) {
                try {
                    /*release the mutex lock and wait no more than timeout ms*/
                    mutex.wait(timeout);
                }
                catch(InterruptedException ex) {
                }
            }
            /*we either timed out, or got notified by the mutex lock object*/
            if(closed)
                throw new QueueClosedException();

            /*get the next value*/
            retval=removeInternal();
            /*null result means we timed out*/
            if(retval == null) throw new TimeoutException("timeout=" + timeout + "ms");

            /*if we reached an end marker we are going to close the queue*/
//            if(retval == endMarker) {
//                close(false);
//                throw new QueueClosedException();
//            }
            /*at this point we actually did receive a value from the queue, return it*/
            return retval;
        }
    }


    /**
     * 带超时时间的移除对象
     * @param timeout
     * @return
     * @throws QueueClosedException
     * @throws TimeoutException
     */
    public Object removeWait(long timeout) throws QueueClosedException, TimeoutException {
        synchronized(mutex) {
            if(closed)
                throw new QueueClosedException();

            final long end_time=System.currentTimeMillis() + timeout;
            long wait_time, current_time;

            /*if the queue size is zero, we want to wait until a new object is added*/
            while(size == 0 && (current_time=System.currentTimeMillis()) < end_time) {//用一个死循环来等待
                if(closed)
                    throw new QueueClosedException();
                try {
                    /*release the mutex lock and wait no more than timeout ms*/
                    wait_time=end_time - current_time;  // guarnteed to be > 0
                    mutex.wait(wait_time);
                }
                catch(InterruptedException ex) {
                }
            }
            /*we either timed out, or got notified by the mutex lock object*/
            if(closed)
                throw new QueueClosedException();

            /*get the next value*/
            Object retval=removeInternal();
            /*null result means we timed out*/
            if(retval == null) throw new TimeoutException("timeout=" + timeout + "ms");

            return retval;
        }
    }


    /**
     * 移除具体某一个对象
     * removes a specific object from the queue.
     * the object is matched up using the Object.equals method.
     * @param   obj the actual object to be removed from the queue
     */
    public void removeElement(Object obj) throws QueueClosedException {
        Element el, tmp_el;

        if(obj == null) {
            if(log.isErrorEnabled()) log.error("argument must not be null");
            return;
        }

        synchronized(mutex) {
            if(closed) /*check to see if the queue is closed*/
                throw new QueueClosedException();

            el=head;

            /*the queue is empty*/
            if(el == null) return;

            /*check to see if the head element is the one to be removed*/
            if(el.obj.equals(obj)) {//检查是不是首元素
                /*the head element matched we will remove it*/
                head=el.next;
                el.next=null;
                el.obj=null;
                /*check if we only had one object left
                 *at this time the queue becomes empty
                 *this will set the tail=head=null
                 */
                if(size == 1)
                    tail=head;  // null
                decrementSize();
                return;
            }

            /*look through the other elements*/
            while(el.next != null) {//循环查找那一个元素
                if(el.next.obj.equals(obj)) {
                    tmp_el=el.next;
                    if(tmp_el == tail) // if it is the last element, move tail one to the left (bela Sept 20 2002)看看是不是最后一个元素
                        tail=el;
                    el.next.obj=null;
                    el.next=el.next.next;  // point to the el past the next one. can be null.
                    tmp_el.next=null;//设置为null，代表JVM垃圾回收期可以回收了
                    tmp_el.obj=null;
                    decrementSize();//减少队列的长度
                    break;
                }
                el=el.next;
            }
        }
    }


    /**
     * 拿出第一个元素，但是不删除,拿不到一直等待，直到有首元素为止
     * returns the first object on the queue, without removing it.
     * If the queue is empty this object blocks until the first queue object has
     * been added
     * @return the first object on the queue
     */
    public Object peek() throws QueueClosedException {
        Object retval;

        synchronized(mutex) {
            while(size == 0) {//检查队列长度是不是0，如果为空则等待
                if(closed)
                    throw new QueueClosedException();
                try {
                    mutex.wait();
                }
                catch(InterruptedException ex) {
                }
            }

            if(closed)
                throw new QueueClosedException();

            retval=(head != null)? head.obj : null;
        }

        if(retval == endMarker) {
            close(false); // mark queue as closed
            throw new QueueClosedException();
        }

        return retval;
    }


    /**
     * 带超时时间的的取得首元素
     * returns the first object on the queue, without removing it.
     * If the queue is empty this object blocks until the first queue object has
     * been added or the operation times out
     * @param timeout how long in milli seconds will this operation wait for an object to be added to the queue
     *        before it times out
     * @return the first object on the queue
     */
    public Object peek(long timeout) throws QueueClosedException, TimeoutException {
        Object retval;

        synchronized(mutex) {
            if(size == 0) {
                if(closed)
                    throw new QueueClosedException();
                try {
                    mutex.wait(timeout);
                }
                catch(InterruptedException ex) {
                }
            }
            if(closed)
                throw new QueueClosedException();

            retval=head != null? head.obj : null;

            if(retval == null) throw new TimeoutException("timeout=" + timeout + "ms");

            if(retval == endMarker) {
                close(false);
                throw new QueueClosedException();
            }
            return retval;
        }
    }

    /** Removes all elements from the queue. This method can succeed even when the queue is closed 
     * 
     * 清空队列，只需要设置首元素和尾元素为null空就好，回收期会链式回收元素 
     * */
    public void clear() {
        synchronized(mutex) {
            head=tail=null;
            size=0;
            num_markers=0;
            mutex.notifyAll();
        }
    }


    /**
     Marks the queues as closed. When an <code>add</code> or <code>remove</code> operation is
     attempted on a closed queue, an exception is thrown.
     @param flush_entries When true, a end-of-entries marker is added to the end of the queue.
     Entries may be added and removed, but when the end-of-entries marker
     is encountered, the queue is marked as closed. This allows to flush
     pending messages before closing the queue.
     */
    public void close(boolean flush_entries) {
        synchronized(mutex) {
            if(flush_entries && size > 0) {
                try {
                    add(endMarker); // add an end-of-entries marker to the end of the queue
                    num_markers++;
                }
                catch(QueueClosedException closed_ex) {
                }
                return;
            }
            closed=true;
            mutex.notifyAll();
        }
    }

    /** 
     * 一直等待，直到队列被关闭为止
     * Waits until the queue has been closed. Returns immediately if already closed
     * @param timeout Number of milliseconds to wait. A value <= 0 means to wait forever
     */
    public void waitUntilClosed(long timeout) {
        synchronized(mutex) {
            if(closed)
                return;
            try {
                mutex.wait(timeout);
            }
            catch(InterruptedException e) {
            }
        }
    }


    /**
     * 队列进行重置操作
     * resets the queue.
     * This operation removes all the objects in the queue and marks the queue open
     */
    public void reset() {
        synchronized(mutex) {
           num_markers=0;
           if(!closed)
              close(false);
            size=0;
            head=null;
            tail=null;
            closed=false;
            mutex.notifyAll();
        }
    }

    /**
     * 返回队列的所有元素
     * 
     * Returns all the elements of the queue
     * @return A copy of the queue
     */
    public LinkedList values() {
        LinkedList retval=new LinkedList();
        synchronized(mutex) {
            Element el=head;
            while(el != null) {
                retval.add(el.obj);
                el=el.next;
            }
        }
        return retval;
    }


    /**
     * 返回队列的大小
     * returns the number of objects that are currently in the queue
     */
    public int size() {
        synchronized(mutex) {
            return size - num_markers;
        }
    }

    /**
     * 队列toString函数
     * prints the size of the queue
     */
    public String toString() {
        return "Queue (" + size() + ") elements";
    }




    /* ------------------------------------- Private Methods ----------------------------------- */


    /**
     * 向队列尾部添加一个对象
     * @param obj
     */
    private final void addInternal(Object obj) {
        /*create a new linked list element*/
        Element el=new Element(obj);
        /*check the first element*/
        if(head == null) {//检查是不是首元素
            /*the object added is the first element*/
            /*set the head to be this object*/
            head=el;
            /*set the tail to be this object*/
            tail=head;
            /*set the size to be one, since the queue was empty*/
            size=1;
        }
        else {//不是首元素
            /*add the object to the end of the linked list*/
            tail.next=el;
            /*set the tail to point to the last element*/
            tail=el;
            /*increase the size*/
            size++;
        }
    }

    /**
     * 从队列里面移除首元素
     * Removes the first element. Returns null if no elements in queue.
     * Always called with mutex locked (we don't have to lock mutex ourselves)
     */
    private Object removeInternal() {
        Element retval;
        Object obj;

        /*if the head is null, the queue is empty*/
        if(head == null)
            return null;

        retval=head;       // head must be non-null now

        head=head.next;//设置第二个元素为头部元素
        if(head == null)//如果第二个元素为null，则设置尾部元素为空。
            tail=null;

        decrementSize();//减少队列的长度
        if(head != null && head.obj == endMarker) {//如果首元素是结束标志，代表队列已经关闭。
            closed=true;
            mutex.notifyAll();
        }

        retval.next=null;//提出对象参考
        obj=retval.obj;
        retval.obj=null;
        return obj;
    }


    /** 
     * 减少队列的长度
     * Doesn't need to be synchronized; is always called from synchronized methods */
    final private void decrementSize() {
        size--;
        if(size < 0)
            size=0;
    }


    /* ---------------------------------- End of Private Methods -------------------------------- */

}
分享到：
| 搜狐面试经历
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    源码解析jdk7.0集合：LinkedList的底层实现原理.pdf

    在深入分析JDK 7.0中LinkedList集合的底层实现原理前，我们首先需要了解LinkedList的基本概念。LinkedList，即双向链表，是一种通过双向指针相互连接的数据结构，每个节点包含数据域以及指向前驱和后继节点的指针。...

    用LinkedList实现队列和栈

    本篇文章将探讨如何利用`LinkedList`来实现队列和栈这两种数据结构，以及其背后的原理和源码分析。 ### 1. 队列（Queue） 队列是一种先进先出（FIFO, First In First Out）的数据结构。在Java中，可以使用`...

    LinkedList源码学习分析

    以下是一个简单的自定义LinkedList实现： ```java public class ExtLinkedList&lt;E&gt; { private int size = 0; private Node first; // 标记查询开始位置 private Node last; // 标记添加时从最后一个节点开始添加 ...

    JAVA利用LinkedList构造栈与队列

    在Java编程语言中，LinkedList是一个常用的集合类，它实现了List接口，同时也提供了双向链表的实现...在阅读和分析给定的Queue.java和Stack.java文件时，可以从实现原理、方法调用、线程安全等方面进行深入学习和理解。

    比较ArrayList、LinkedList、Vector1

    - **实现原理**：LinkedList是一个双向链表，每个节点包含元素和指向前后节点的引用。 - **添加和删除**：在LinkedList中，添加和删除元素（尤其是头尾操作）非常高效，因为只需要修改相邻节点的引用即可。 - **...

    Java 中Linkedlist类的源代码

    LinkedList类的源代码分析对于理解其工作原理非常重要，特别是对于学习数据结构和算法的开发者来说。它展示了如何使用链表数据结构来实现动态列表，以及如何通过内部类和指针操作实现高效的插入、删除和遍历操作。...

    LinkedList代码.rar

    LinkedList是一种在Java编程语言中广泛...总之，LinkedList是一种重要的数据结构，理解其工作原理和特性对于提升Java编程能力至关重要。通过学习和实践，开发者能够更有效地利用LinkedList解决各种数据存储和操作问题。

    Map+List+ArrayList+LinkedList Java源码

    例如，`HashMap`的哈希函数如何计算元素的桶位置，`ArrayList`如何调整其容量，以及`LinkedList`如何通过链表结构实现添加和删除。源码阅读可以揭示类的内部结构，包括数据成员、构造函数、方法实现等，从而帮助我们...

    ArrayList-LinkedList-源码.rar

    接下来，我们将详细分析ArrayList和LinkedList的源码，以理解它们的工作原理。 1. ArrayList的源码解析： - `add(E e)`：在末尾添加元素，如果容量不足，会调用`ensureCapacityInternal()`进行扩容。 - `add(int ...

    Java遍历集合方法分析(实现原理、算法性能、适用场合)_.docx

    Java中的集合遍历是编程实践中常见的操作，不同的遍历方式有着不同的实现原理、性能特点以及适用场景。本文将深入分析Java中三种主要的遍历集合方法：传统的for循环遍历、迭代器遍历以及foreach循环遍历。 1. **...

    linkedlist_binaryTree.rar_Creating_linkedlist_vb.net list

    在这个“linkedlist_binaryTree.rar”压缩包中，包含了创建链表（包括单向链表和双向链表）以及二叉树的源代码，虽然源码注释为西班牙语，但我们可以从中学习到基本的结构和原理。 链表是一种线性数据结构，与数组...

    Java中的ArrayList的底层源码解读、LinkedList、Vector的区别介绍

    自动扩容和自动缩容的源码分析，相关参数的深度解析，从是什么，为什么，怎么做三个角度进行讲解，用通俗易懂的白话进行介绍，LinkedList和Vector以及ArrayList的区别以及使用场景，时间复杂度的介绍，相关数据结构...

    java 中ArrayList与LinkedList性能比较

    首先，让我们来了解ArrayList和LinkedList的实现原理。ArrayList是基于数组结构实现的，而LinkedList是基于链表结构实现的。数组结构的优点是可以快速地通过索引访问元素，而链表结构的优点是可以快速地插入和删除...

    LinkedList:一种类似于 LinkedList 中构建的数据结构

    通过阅读和分析这些文件，你可以更深入地理解LinkedList的实现原理和用法，以及如何在实际项目中应用它。同时，也可以学习到如何编写单元测试来确保代码的正确性。总之，理解并熟练掌握LinkedList对于任何Java开发者...

    LinkedList_example:LinkedList Javascript

    以下是一个简单的LinkedList实现： ```javascript class LinkedList { constructor() { this.head = null; this.size = 0; } // 添加元素到链表尾部 append(data) { let newNode = new Node(data); if (!...

    编译原理 C、Java语言词法分析器（java实现）

    总结来说，这个项目提供了实际应用编译原理的机会，涵盖了词法分析器的设计与实现，以及GUI的开发，对于学习和掌握编译技术有着重要的实践意义。通过这样的实践，开发者不仅能深入理解编程语言的底层机制，也能提升...

    LinkedList

    LinkedList是计算机科学中一种常见的...通过阅读和分析这些文件，你可以深入理解LinkedList的内部工作原理，学习如何在实际编程中有效使用和操作LinkedList。同时，这也可以帮助你提升对C++内存管理和指针操作的理解。

    Java集合框架常用集合源代码及其实现

    Java集合框架是Java编程语言中的一个核心部分，它为数据结构和对象的存储、管理和操作提供了统一...通过学习和分析`chapter3.html`这样的文档，我们可以深入了解每个集合类的内部工作原理，进一步提升我们的编程技能。

    Java 实例 - 栈的实现源代码-详细教程.zip

    在LinkedList实现中，我们利用了其addFirst()和pollFirst()方法来模拟栈的行为。 栈在实际编程中的应用非常广泛，例如在表达式求值（如后缀表达式）、括号匹配、函数调用栈、深度优先搜索（DFS）以及网页浏览历史...

Magicbox
Global site tag (gtag.js) - Google Analytics