/*
  SinglyLinkedList.java
  Created for Aoi.java
  Written by Tero Hasu.
  */

class Link
{
  public
  Link(Object d, Link n) { data = d; next = n; }

  public
  Object data;
  public
  Link next;
}

class SinglyLinkedList
{
  public
  boolean IsMore()
  {
    Link cursor = Cursor();
    return (cursor != null) && (cursor.next != null);
  }

  public
  // Inserts data before cursor, or appends if position is invalid.
  void Insert(Object data)
  {
    if(!posValid)
      Append(data);
    Link link = new Link(data,Cursor());
    if(preCursor==null)
    {
      if(head==null) tail=link;
      head=link;
    } else {
      preCursor.next=link;
      if(preCursor==tail) tail=link;
    }
    length++;
  }

  public
  void Append(Object data)
  {
    Link link = new Link(data,null);
    if(length==0)
    {
      head = tail = link;
    } else {
      tail.next = link;
      tail = link;
    }
    length++;
  }

  public
  // Returns the element under the cursor, or null if none.
  Object Remove()
  {
    if(!posValid) return null;
    Link cursor = Cursor();
    if(cursor==null) return null;
    if(tail==cursor) tail=preCursor;
    if(preCursor==null)
      head=cursor.next;
    else
      preCursor.next=cursor.next;
    length--;
    return cursor.data;
  }

  public
  // Returns true if there are elements on the list, false otherwise.
  boolean PositionHead()
  {
    preCursor = null;
    posValid = true;
    return (head==null)?false:true;
  }

  public
  // Returns true if the element positioned to is a valid element,
  // and false if we went past the end of the list.
  boolean PositionNext()
  {
    if(!posValid) return false;
    if(preCursor==null) preCursor=head; // head may be null
    else preCursor=preCursor.next; // next may be null
    if(preCursor==null) {
      posValid = false;
      return false;
    }
    return true;
  }

  public
  Object Current()
  {
    Link cursor = Cursor();
    if(cursor==null) return null;
    return cursor.data;
  }

  private
  // Returns the link on which cursor resides, or null if cursor
  // is not on a valid link.
  Link Cursor()
  {
    if(!posValid) return null;
    if(preCursor==null) return head;
    else return preCursor.next;
  }

  private
  Link head = null;
  private
  Link tail = null;
  private
  Link preCursor = null;   // predecessor of cursor
  private
  boolean posValid = true; // cursor position is valid
  public
  int length = 0;          // read only
}