linkedlist.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 959 行 · 第 1/2 页

        prev = e;
      }

    // Link the new chain of entries into the list.
    modCount++;
    size += csize;
    prev.next = after;
    if (after != null)
      after.previous = e;
    else
      last = e;

    if (before != null)
      before.next = firstNew;
    else
      first = firstNew;
    return true;
  }

  /**
   * Remove all elements from this list.
   */
  public void clear()
  {
    if (size > 0)
      {
        modCount++;
        first = null;
        last = null;
        size = 0;
      }
  }

  /**
   * Return the element at index.
   *
   * @param index the place to look
   * @return the element at index
   * @throws IndexOutOfBoundsException if index < 0 || index >= size()
   */
  public Object get(int index)
  {
    checkBoundsExclusive(index);
    return getEntry(index).data;
  }

  /**
   * Replace the element at the given location in the list.
   *
   * @param index which index to change
   * @param o the new element
   * @return the prior element
   * @throws IndexOutOfBoundsException if index < 0 || index >= size()
   */
  public Object set(int index, Object o)
  {
    checkBoundsExclusive(index);
    Entry e = getEntry(index);
    Object old = e.data;
    e.data = o;
    return old;
  }

  /**
   * Inserts an element in the given position in the list.
   *
   * @param index where to insert the element
   * @param o the element to insert
   * @throws IndexOutOfBoundsException if index < 0 || index > size()
   */
  public void add(int index, Object o)
  {
    checkBoundsInclusive(index);
    Entry e = new Entry(o);

    if (index < size)
      {
        modCount++;
        Entry after = getEntry(index);
        e.next = after;
        e.previous = after.previous;
        if (after.previous == null)
          first = e;
        else
          after.previous.next = e;
        after.previous = e;
        size++;
      }
    else
      addLastEntry(e);
  }

  /**
   * Removes the element at the given position from the list.
   *
   * @param index the location of the element to remove
   * @return the removed element
   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
   */
  public Object remove(int index)
  {
    checkBoundsExclusive(index);
    Entry e = getEntry(index);
    removeEntry(e);
    return e.data;
  }

  /**
   * Returns the first index where the element is located in the list, or -1.
   *
   * @param o the element to look for
   * @return its position, or -1 if not found
   */
  public int indexOf(Object o)
  {
    int index = 0;
    Entry e = first;
    while (e != null)
      {
        if (equals(o, e.data))
          return index;
        index++;
        e = e.next;
      }
    return -1;
  }

  /**
   * Returns the last index where the element is located in the list, or -1.
   *
   * @param o the element to look for
   * @return its position, or -1 if not found
   */
  public int lastIndexOf(Object o)
  {
    int index = size - 1;
    Entry e = last;
    while (e != null)
      {
        if (equals(o, e.data))
          return index;
        index--;
        e = e.previous;
      }
    return -1;
  }

  /**
   * Obtain a ListIterator over this list, starting at a given index. The
   * ListIterator returned by this method supports the add, remove and set
   * methods.
   *
   * @param index the index of the element to be returned by the first call to
   *        next(), or size() to be initially positioned at the end of the list
   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
   */
  public ListIterator listIterator(int index)
  {
    checkBoundsInclusive(index);
    return new LinkedListItr(index);
  }

  /**
   * Create a shallow copy of this LinkedList (the elements are not cloned).
   *
   * @return an object of the same class as this object, containing the
   *         same elements in the same order
   */
  public Object clone()
  {
    LinkedList copy = null;
    try
      {
        copy = (LinkedList) super.clone();
      }
    catch (CloneNotSupportedException ex)
      {
      }
    copy.clear();
    copy.addAll(this);
    return copy;
  }

  /**
   * Returns an array which contains the elements of the list in order.
   *
   * @return an array containing the list elements
   */
  public Object[] toArray()
  {
    Object[] array = new Object[size];
    Entry e = first;
    for (int i = 0; i < size; i++)
      {
        array[i] = e.data;
        e = e.next;
      }
    return array;
  }

  /**
   * Returns an Array whose component type is the runtime component type of
   * the passed-in Array.  The returned Array is populated with all of the
   * elements in this LinkedList.  If the passed-in Array is not large enough
   * to store all of the elements in this List, a new Array will be created 
   * and returned; if the passed-in Array is <i>larger</i> than the size
   * of this List, then size() index will be set to null.
   *
   * @param a the passed-in Array
   * @return an array representation of this list
   * @throws ArrayStoreException if the runtime type of a does not allow
   *         an element in this list
   * @throws NullPointerException if a is null
   */
  public Object[] toArray(Object[] a)
  {
    if (a.length < size)
      a = (Object[]) Array.newInstance(a.getClass().getComponentType(), size);
    else if (a.length > size)
      a[size] = null;
    Entry e = first;
    for (int i = 0; i < size; i++)
      {
        a[i] = e.data;
        e = e.next;
      }
    return a;
  }

  /**
   * Serializes this object to the given stream.
   *
   * @param s the stream to write to
   * @throws IOException if the underlying stream fails
   * @serialData the size of the list (int), followed by all the elements
   *             (Object) in proper order
   */
  private void writeObject(ObjectOutputStream s) throws IOException
  {
    s.defaultWriteObject();
    s.writeInt(size);
    Entry e = first;
    while (e != null)
      {
        s.writeObject(e.data);
        e = e.next;
      }
  }

  /**
   * Deserializes this object from the given stream.
   *
   * @param s the stream to read from
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @serialData the size of the list (int), followed by all the elements
   *             (Object) in proper order
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    s.defaultReadObject();
    int i = s.readInt();
    while (--i >= 0)
      addLastEntry(new Entry(s.readObject()));
  }

  /**
   * A ListIterator over the list. This class keeps track of its
   * position in the list and the two list entries it is between.
   *
   * @author Original author unknown
   * @author Eric Blake <[e-mail]>
   */
  private final class LinkedListItr implements ListIterator
  {
    /** Number of modifications we know about. */
    private int knownMod = modCount;

    /** Entry that will be returned by next(). */
    private Entry next;

    /** Entry that will be returned by previous(). */
    private Entry previous;

    /** Entry that will be affected by remove() or set(). */
    private Entry lastReturned;

    /** Index of `next'. */
    private int position;

    /**
     * Initialize the iterator.
     *
     * @param index the initial index
     */
    LinkedListItr(int index)
    {
      if (index == size)
        {
          next = null;
          previous = last;
        }
      else
        {
          next = getEntry(index);
          previous = next.previous;
        }
      position = index;
    }

    /**
     * Checks for iterator consistency.
     *
     * @throws ConcurrentModificationException if the list was modified
     */
    private void checkMod()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
    }

    /**
     * Returns the index of the next element.
     *
     * @return the next index
     * @throws ConcurrentModificationException if the list was modified
     */
    public int nextIndex()
    {
      checkMod();
      return position;
    }

    /**
     * Returns the index of the previous element.
     *
     * @return the previous index
     * @throws ConcurrentModificationException if the list was modified
     */
    public int previousIndex()
    {
      checkMod();
      return position - 1;
    }

    /**
     * Returns true if more elements exist via next.
     *
     * @return true if next will succeed
     * @throws ConcurrentModificationException if the list was modified
     */
    public boolean hasNext()
    {
      checkMod();
      return (next != null);
    }

    /**
     * Returns true if more elements exist via previous.
     *
     * @return true if previous will succeed
     * @throws ConcurrentModificationException if the list was modified
     */
    public boolean hasPrevious()
    {
      checkMod();
      return (previous != null);
    }

    /**
     * Returns the next element.
     *
     * @return the next element
     * @throws ConcurrentModificationException if the list was modified
     * @throws NoSuchElementException if there is no next
     */
    public Object next()
    {
      checkMod();
      if (next == null)
        throw new NoSuchElementException();
      position++;
      lastReturned = previous = next;
      next = lastReturned.next;
      return lastReturned.data;
    }

    /**
     * Returns the previous element.
     *
     * @return the previous element
     * @throws ConcurrentModificationException if the list was modified
     * @throws NoSuchElementException if there is no previous
     */
    public Object previous()
    {
      checkMod();
      if (previous == null)
        throw new NoSuchElementException();
      position--;
      lastReturned = next = previous;
      previous = lastReturned.previous;
      return lastReturned.data;
    }

    /**
     * Remove the most recently returned element from the list.
     *
     * @throws ConcurrentModificationException if the list was modified
     * @throws IllegalStateException if there was no last element
     */
    public void remove()
    {
      checkMod();
      if (lastReturned == null)
        throw new IllegalStateException();

      // Adjust the position to before the removed element, if the element
      // being removed is behind the cursor.
      if (lastReturned == previous)
        position--;

      next = lastReturned.next;
      previous = lastReturned.previous;
      removeEntry(lastReturned);
      knownMod++;

      lastReturned = null;
    }

    /**
     * Adds an element between the previous and next, and advance to the next.
     *
     * @param o the element to add
     * @throws ConcurrentModificationException if the list was modified
     */
    public void add(Object o)
    {
      checkMod();
      modCount++;
      knownMod++;
      size++;
      position++;
      Entry e = new Entry(o);
      e.previous = previous;
      e.next = next;

      if (previous != null)
        previous.next = e;
      else
        first = e;

      if (next != null)
        next.previous = e;
      else
        last = e;

      previous = e;
      lastReturned = null;
    }

    /**
     * Changes the contents of the element most recently returned.
     *
     * @param o the new element
     * @throws ConcurrentModificationException if the list was modified
     * @throws IllegalStateException if there was no last element
     */
    public void set(Object o)
    {
      checkMod();
      if (lastReturned == null)
        throw new IllegalStateException();
      lastReturned.data = o;
    }
  } // class LinkedListItr
}