class Item   // items for a linked list
{
    int  value;
    Item next;

    // constructors
    Item (int x) // construct item with value x
    {
        value = x;
    }

    Item (int x, Item p) // construct item with value x and next p
    {
        value = x;
        next  = p;
    }

    void print() // print the information about the item, must exist
    {
        System.out.print(this);
        System.out.print(":  value: " + value);
        System.out.print("  next: " + next);
        System.out.println();
    }
}

class List   // List class, singly linked list, test with   java List  
{
    Item start = null;  // start of the list

    Item find(int x)
        // find value x in the list, return item containing it
        // if not present, return null
    {
        Item p = start;
        while (p != null && p.value != x)
            p = p.next;
        return p;
    }

    void insert(Item after, int x)
        // insert a new element after the item  after
        // if  after==null, insert at front of list
    {
        if (after == null)
            start = new Item(x, start);
        else
            after.next = new Item(x, after.next);
    }

    void dele (Item after)
        // del a new element after the item  after
        // if  after==null, delete first element of list
        // list item must exist, and list must not be empty
    {
        if (after == null)
            start = start.next;
        else
            after.next = after.next.next;
    } 

    void finddel (int x)
        // find an element in the list and delete it
        // do nothing if not found
    {
        Item previous = null;
        for (Item p = start; p!= null; p = p.next)
            if (p.value == x)
            {
                dele (previous);
                break;
            }
            else
                previous = p; 
    } 

    void print()
        // print the list
    {
        for (Item p = start; p!= null; p = p.next)
            p.print();
        System.out.println("----------");
    }

    public static void main (String[] args)
    {
        List L = new List();
        L.insert(null, 4);
        L.insert(null, 5);
        L.insert(null, 7);
        L.insert(null, 9);
        L.print(); 

        Item p = L.find(7);
        p.print();
        System.out.println("----------");

        L.dele(p);
        L.print(); 

        L.insert(p, 15);
        L.print(); 

        L.finddel(7);
        L.print(); 

        L.finddel(7);
        L.print(); 

    } 
}
/* output generated:

Item@824dbac:  value: 9  next: Item@824de64
Item@824de64:  value: 7  next: Item@8249624
Item@8249624:  value: 5  next: Item@8184da4
Item@8184da4:  value: 4  next: null
----------
Item@824de64:  value: 7  next: Item@8249624
----------
Item@824dbac:  value: 9  next: Item@824de64
Item@824de64:  value: 7  next: Item@8184da4
Item@8184da4:  value: 4  next: null
----------
Item@824dbac:  value: 9  next: Item@824de64
Item@824de64:  value: 7  next: Item@829b69c
Item@829b69c:  value: 15  next: Item@8184da4
Item@8184da4:  value: 4  next: null
----------
Item@824dbac:  value: 9  next: Item@829b69c
Item@829b69c:  value: 15  next: Item@8184da4
Item@8184da4:  value: 4  next: null
----------
Item@824dbac:  value: 9  next: Item@829b69c
Item@829b69c:  value: 15  next: Item@8184da4
Item@8184da4:  value: 4  next: null
----------

*/