/*****************************************************************************/
/*                                                                           */
/*                    Singly-Linked List Manipulation                        */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                                                                           */
/*****************************************************************************/

// A SLNode is a node in a singly-linked list.
class SLNode {            // class for nodes in a singly-linked list
  SLNode next;            // next SLNode in a singly-linked list
  String key;             // key value for this node
  public Object data;     // data stored in this SLNode

  SLNode(String key, Object data) {   // constructor for a SLNode with data
    next = null;
    this.key = key;       // set argument key to instance variable key
    this.data = data;     // set argument data to instance variable data
  }
}

class SList {
  SLNode head;                          // head of singly-linked list

  public void insertTail(String key, Object data) {
    SLNode newNode = new SLNode(key, data);      // create new data node
    if (head == null) {                          // is list empty?
      head = newNode;                            // add single new data node
      return;
    }
    SLNode current = head;
    for ( ; current.next != null;) {             // find node at tail
      current = current.next;
    }
    current.next = newNode;                      // add new node at end
    System.out.println("Node with key = " + key + " inserted.");
  }

  public Object find(String key) {      // find SLNode containing key
    for (SLNode current = head; current != null; current = current.next) {
      if (current.key == key) {         // is key contained in current SLNode?
        System.out.println("Node containing " + key + " found.");
        return current.data;            // return data associated with key
      }
    }
    System.out.println("Data " + key + " not found");
    return null;
  }

  public void print() {                 // print content of list
    if (head == null) {                 // is list empty
      System.out.println("list empty");
      return;
    }
    System.out.print("List content: ");
    for (SLNode current = head; current != null; current = current.next) {
      System.out.print("  key = " + current.key + ", data = " + current.data);
    }
    System.out.println("");
  }

  public static void main(String[] args) {
    SList sList = new SList();                // create an empty sList
    sList.print();

    int i = 0;                                // counter
    sList.insertTail("A", new Integer(++i));
    sList.print();
    sList.insertTail("B", new Integer(++i));
    sList.print();
    sList.insertTail("C", new Integer(++i));
    sList.print();

    System.out.println("Data associated with key = \"C\": " + sList.find("C"));
    System.out.println("Data associated with key = \"E\": " + sList.find("E"));
    System.out.println("Data associated with key = \"A\": " + sList.find("A"));
  }
}