/**

 * Creation and testing of a generic linked list, ListNode.

 *

 * @author T. Andrew Yang

 */

public class ListNode {

       private int data;

       private ListNode next;

        private ListNode first=this;

        private ListNode last=this;

        private int numberOfNodes = 0;

        public ListNode(){

            this.data = -1;

            this.next = null;

            return;

        }

        // Remove all occurrences of nodes with data equal to key.

        // Return 0 if no such nodes are found; otherwise return the number of nodes found

        public static ListNode findAndRemove (ListNode list, int key) {

            int foundNodes = 0;

            ListNode tempNode = list;

            ListNode previous = list;

            for (int i=0; tempNode != null; tempNode = tempNode.next, i++){

                //System.out.println ("in findAndRemove(): Node " + i + ": " + tempNode.data);

                //System.out.println("previous node: " + previous.data);

                if (tempNode.data == key) { // found

                    foundNodes++; // one such node is found

                    if (tempNode == previous) { // first node

                        list = tempNode.next; // discard the original first

                    }

                    else if (tempNode == list.last) { //last node

                        list.last = previous; //discard the original last

                        list.last.next = null;

                    }

                    else { // somewhere in the middle

                        previous.next = tempNode.next; //bypass the current node

                    }

                    list.numberOfNodes--;

                }

                else { // not found in this node

                  previous=tempNode; //previous advances only when no node was found and deleted

                }

            } //for

            System.out.println("Found " + foundNodes + " nodes with " + key);

            return list;

        }

        public void initialize(){

            ListNode tempNode = new ListNode();

            // create a new linked lisst

            first.data = 0;

            first.next = null;

            numberOfNodes++;

            last = this.first;

            for (int i=1; i<5; i++, numberOfNodes++){

                tempNode = new ListNode();

                tempNode.data = i;

                tempNode.next = null;

                last.next = tempNode;

                last = tempNode;

            }

        }

        // Add value as a new ListNode and insert it into the right spot so the data are at ascending order

        public void addSorted (int value){

        } // addSorted()

        public void displayAllNodes (){

            ListNode tempNode = this;

            for (int i=0; tempNode != null; tempNode = tempNode.next, i++){

                System.out.println ("Node " + i + ": " + tempNode.data);

            }

            //System.out.println("Leaving displayAllNodes\n");

        }

        public static void main(String args[]) {

            ListNode list = new ListNode();

            //create a linked list

            list.initialize();

            System.out.println("A new linked list was initialized: " + list.numberOfNodes + " nodes.");

            list.displayAllNodes();

            list.next.data = 3; //set redundant nodes

            //list.displayAllNodes();

            list = findAndRemove(list, 3);

            System.out.println("After deleing 3");

            list.displayAllNodes();

            list = findAndRemove(list, 0);

            System.out.println("After deleing 0");

            list.displayAllNodes();

            list = findAndRemove(list, 5);

            System.out.println("After deleing 5");

            list.displayAllNodes();

            list = findAndRemove(list, 4);

            System.out.println("After deleing 4");

            list.displayAllNodes();

        } //main

} // class: ListNode