tlinkedlist.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////


package gnu.trove;

import java.io.Serializable;
import java.util.AbstractSequentialList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * A LinkedList implementation which holds instances of type
 * <tt>TLinkable</tt>.
 *
 * <p>Using this implementation allows you to get java.util.LinkedList
 * behavior (a doubly linked list, with Iterators that support insert
 * and delete operations) without incurring the overhead of creating
 * <tt>Node</tt> wrapper objects for every element in your list.</p>
 *
 * <p>The requirement to achieve this time/space gain is that the
 * Objects stored in the List implement the <tt>TLinkable</tt>
 * interface.</p>
 *
 * <p>The limitations are that you cannot put the same object into
 * more than one list or more than once in the same list.  You must
 * also ensure that you only remove objects that are actually in the
 * list.  That is, if you have an object A and lists l1 and l2, you
 * must ensure that you invoke List.remove(A) on the correct list.  It
 * is also forbidden to invoke List.remove() with an unaffiliated
 * TLinkable (one that belongs to no list): this will destroy the list
 * you invoke it on.</p>
 *
 * <p>
 * Created: Sat Nov 10 15:25:10 2001
 * </p>
 *
 * @author Eric D. Friedman
 * @version $Id: TLinkedList.java,v 1.1.1.1 2003/07/14 19:36:04 mccallum Exp $
 * @see gnu.trove.TLinkable
 */

public class TLinkedList extends AbstractSequentialList
    implements Serializable {

    /** the head of the list */
    protected TLinkable _head;
    /** the tail of the list */
    protected TLinkable _tail;
    /** the number of elements in the list */
    protected int _size = 0;
    
    /**
     * Creates a new <code>TLinkedList</code> instance.
     *
     */
    public TLinkedList() {
        super();
    }

    /**
     * Returns an iterator positioned at <tt>index</tt>.  Assuming
     * that the list has a value at that index, calling next() will
     * retrieve and advance the iterator.  Assuming that there is a
     * value before <tt>index</tt> in the list, calling previous()
     * will retrieve it (the value at index - 1) and move the iterator
     * to that position.  So, iterating from front to back starts at
     * 0; iterating from back to front starts at <tt>size()</tt>.
     *
     * @param index an <code>int</code> value
     * @return a <code>ListIterator</code> value
     */
    public ListIterator listIterator(int index) {
        return new IteratorImpl(index);
    }

    /**
     * Returns the number of elements in the list.
     *
     * @return an <code>int</code> value
     */
    public int size() {
        return _size;
    }

    /**
     * Inserts <tt>linkable</tt> at index <tt>index</tt> in the list.
     * All values > index are shifted over one position to accomodate
     * the new addition.
     *
     * @param index an <code>int</code> value
     * @param linkable an object of type TLinkable
     */
    public void add(int index, Object linkable) {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("index:" + index);
        }
        insert(index,linkable);
    }

    /**
     * Appends <tt>linkable</tt> to the end of the list.
     *
     * @param linkable an object of type TLinkable
     * @return always true
     */
    public boolean add(Object linkable) {
        insert(_size, linkable);
        return true;
    }

    /**
     * Inserts <tt>linkable</tt> at the head of the list.
     *
     * @param linkable an object of type TLinkable
     */
    public void addFirst(Object linkable) {
        insert(0, linkable);
    }

    /**
     * Adds <tt>linkable</tt> to the end of the list.
     *
     * @param linkable an object of type TLinkable
     */
    public void addLast(Object linkable) {
        insert(size(), linkable);
    }

    /**
     * Empties the list.
     *
     */
    public void clear() {
        if (null != _head) {
            for (TLinkable link = _head.getNext();
                 link != null;
                 link = link.getNext()) {
                TLinkable prev = link.getPrevious();
                prev.setNext(null);
                link.setPrevious(null);
            }
            _head = _tail = null;
        }
        _size = 0;
    }

    /**
     * Copies the list's contents into a native array.  This will be a
     * shallow copy: the Tlinkable instances in the Object[] array
     * have links to one another: changing those will put this list
     * into an unpredictable state.  Holding a reference to one
     * element in the list will prevent the others from being garbage
     * collected unless you clear the next/previous links.  <b>Caveat
     * programmer!</b>
     *
     * @return an <code>Object[]</code> value
     */
    public Object[] toArray() {
        Object[] o = new Object[_size];
        int i = 0;
        for (TLinkable link = _head; link != null; link = link.getNext()) {
            o[i++] = link;
        }
        return o;
    }

    /**
     * Copies the list to a native array, destroying the next/previous
     * links as the copy is made.  This list will be emptied after the
     * copy (as if clear() had been invoked).  The Object[] array
     * returned will contain TLinkables that do <b>not</b> hold
     * references to one another and so are less likely to be the
     * cause of memory leaks.
     *
     * @return an <code>Object[]</code> value
     */
    public Object[] toUnlinkedArray() {
        Object[] o = new Object[_size];
        int i = 0;
        for (TLinkable link = _head, tmp = null; link != null; i++) {
            o[i] = link;
            tmp = link;
            link = link.getNext();
            tmp.setNext(null); // clear the links
            tmp.setPrevious(null);
        }
        _size = 0;              // clear the list
        _head = _tail = null;
        return o;
    }

    /**
     * A linear search for <tt>o</tt> in the list.
     *
     * @param o an <code>Object</code> value
     * @return a <code>boolean</code> value
     */
    public boolean contains(Object o) {
        for (TLinkable link = _head; link != null; link = link.getNext()) {
            if (o.equals(link)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns the head of the list
     *
     * @return an <code>Object</code> value
     */
    public Object getFirst() {
        return _head;
    }

    /**
     * Returns the tail of the list.
     *
     * @return an <code>Object</code> value
     */
    public Object getLast() {
        return _tail;
    }

    /**
     * Remove and return the first element in the list.
     *
     * @return an <code>Object</code> value
     */
    public Object removeFirst() {
        TLinkable o = _head;
        TLinkable n = o.getNext();
        o.setNext(null);

        if (null != n) {
            n.setPrevious(null);
        }

        _head = n;
        if (--_size == 0) {
            _tail = null;
        }
        return o;
    }

    /**
     * Remove and return the last element in the list.
     *
     * @return an <code>Object</code> value
     */
    public Object removeLast() {
        TLinkable o = _tail;
        TLinkable prev = o.getPrevious();
        o.setPrevious(null);

        if (null != prev) {
            prev.setNext(null);
        }
        _tail = prev;
        if (--_size == 0) {
            _head = null;
        }
        return o;
    }

    /**
     * Implementation of index-based list insertions.
     *
     * @param index an <code>int</code> value
     * @param linkable an object of type TLinkable
     */
    protected void insert(int index, Object linkable) {
        TLinkable newLink = (TLinkable)linkable;

        if (_size == 0) {
            _head = _tail = newLink; // first insertion
        } else if (index == 0) {
            newLink.setNext(_head); // insert at front
            _head.setPrevious(newLink);
            _head = newLink;
        } else if (index == _size) { // insert at back
            _tail.setNext(newLink);
            newLink.setPrevious(_tail);
            _tail = newLink;