COSC4301                                           Program-4                                             due10/11/2012

                                                 Linked List Manipulations.

 

Objectives:

1.       Gain some deeper familiarities with Linked List organization and  some common operations

such as recursive insertion and recursive search.

                2.    Declaration of an inner private class.

 

Tasks:

You are asked

                1. to define and include two more brand new methods:

                                public NodeList makeCopy()

                                public NodeList reverse()

                2. to redefine the existing method insert() recursively with a new name of insertRecursive()

                3. Redefine the public class Node by inserting the entire declaration of this class just inside (and at the front of)

                    the declaration of  the class of NodeList. You can make this inner class private.

Notes:     The method makecopy() will return an object of class NodeList (which is a linked list) that is a "deep" copy

 of the calling object.

                 For example, myList.makecopy() will return an identical linked list to myList except that all nodes of this new list

                 must copy different memory spaces.

                 The method reverse() will return a linked list of this class whose elements  (and hence nodes) are arranged

                 in exactly the reverse order of those of the calling object.

Requirements:

                Use the following input expressions:

                                A OR B AND C

                                A AND B OR C

                                A AND B AND C OR D

                                Y AND B OR C AND D

                                F OR G OR H AND M

                                (F OR G OR H) AND M

                                B OR C AND (F OR G OR T)

 

/* CS4301 Java Example: Linked list

This program shows how to

1. construct a linked list of nodes each of which contains three items:

an expression as a String object, reference pointing to the next node,

if one does exist and the length of the String.

2. how to insert a new node to an existing list (empty or not) in three different ways:

· alphabetically so as to facilitate searching process.

· to the front of an existing list so that the resulting list will show nodes in the exactly reverse order of their arrivals.

· to the end of an existing list so that the resulting list will show nodes in the same order as their arrivals.

3. how to print all nodes of a list.

4. how to search a list for a certain node reference.

5. two classes are used:

public class NodeList

class Node

 

**/

// import javax.swing.JOptionPane;

import java.util.Scanner;

///////////////////////////////

public class NodeList

{ private Node firstNode;

                                // The reference to first node of a list.

private Node lastNode;

                                // the reference to last node of a list.

private int count;

                                // count of existing nodes of a list.

public NodeList()

                // construct an empty list object, initially.

{ firstNode = lastNode = null;

count=0;

}

public NodeList (String firstItem)

{

                // construct a list object of just one node to contain                   

// given firstItem

 

firstNode = lastNode = new Node (firstItem, null);

count=1;

}

public NodeList (Node first, Node last, int countt)

{ firstNode=first;

lastNode=last;

count = countt;

}

/////////////////////////////////////////////////////

public void insertFront (Node newNode)

// just inserts the given newNode in front of the list

{

if (isEmpty()) // The list is empty and so

// newNode becomes firstNode and lastNode.

{

firstNode=lastNode=newNode;

newNode.next = null; // Just in case.

count = 1;

}

else // current firstNode becomes the immed successor of

// this new newNode.

{ newNode.next = firstNode;

firstNode = newNode;

count++;

}

} // end of insertFront()

///////////////////////////////////////////

public void insertBack (Node newNode)

// just inserts the given newNode at the rear of the list

{

if (isEmpty()) // The list is empty.

{ firstNode = lastNode = newNode;

count = 1;

}

else // current lastNode becomes the immed predeccessor of

// this new newNode

{ lastNode.next = newNode;

lastNode = newNode;

newNode.next = null; // just in case.

count++;

}

} // end of insertBack()

//////////////////////////////////////

public void insert (Node newNode)

// inserts given 'newNode' into current list alphabetically

{ Node prev;

if (isEmpty()) // The list is empty, and so

// newNode becomes firstNode and lastNode

{

firstNode = lastNode = newNode;

newNode.next=null; // Just in case.

count++;

}

else // the list not empty.

{

if (newNode.exp.compareTo(firstNode.exp) <= 0)

// this newNode becomes the new firstNode.

{

newNode.next = firstNode;

firstNode = newNode;

count++;

return;

}

else

{

Node current = firstNode;

prev=current;

                                 // Useless assignment just to avoid a syntax error.

while ((current != null) &&

(newNode.exp.compareTo(current.exp)>0))

// advance while newNode still larger and list not done yet

// The condition is initially true, so loop repeats                                           

                 // at least once

{ prev = current;

current = current.next;

}

// this newNode now can be inserted between prev node and

// current node as either it is not larger any more than                                  

                 // current node or current node is null.

newNode.next = current;

prev.next = newNode;

count++;

if (current == null)

                                                // then newNode is now lastNode

lastNode = newNode;

}

}

} // end of insert()

////////////////////////////////////

public int search (Node startNode, String wanted, int position)

// Recursively searches the current list for the wanted String       

//and returns its position in the list if found, else returns -1

{ ++position;

if (startNode == null) return -1;

else

{

if (wanted.equals(startNode.exp))

return position;

else

if (wanted.compareTo(startNode.exp)< 0)

return -1;

else // not done yet.

return search (startNode.next, wanted, position);

}

} // end of search()

///////////////////////////////////

public boolean isEmpty()

{ return firstNode==null;

}

//////////////////////////////////////////////

public void print()

{

if (count == 0)

System.out.println ("THE LIST IS EMPTY NOW, BYE!!!\n");

else

{ String output = count + " NODES.";

System.out.println (output);

Node current = firstNode;

for (int times=1; count>=times; times++)

{ System.out.println (" " + current.exp);

current = current.next;

}

}

} // end of print()

//////////////////////////////////////////////

 

public static void main (String args[])

{

Scanner inputStream = new Scanner(System.in);

NodeList linked1 = new NodeList();

NodeList linked2 = new NodeList();

NodeList linked3 = new NodeList();

// Three empty lists have been created whose                                                // firstNode=lastNode=null

// These lists are now ready to get new nodes to be inserted        // into it.

// linked1 will have nodes alphabetically sorted.

// linked2 will have nodes inserted simply at the front                  

// always.

// linked3 will have nodes inserted simply at the rear.

                 System.out.println ("\nPLEASE ENTER 8 LINES OF EXPRESSIONS:\n";

for (int times=1; times<=8; times++)

{ String expression = inputStream.nextLine();

                 Node inp1 = new Node(expression, null);

Node inp2 = new Node (inp1);

                                // Make a copy of inp1 for inp2 for inp3.

Node inp3 = new Node (inp1);

linked1.insert (inp1);

linked2.insertFront (inp2);

linked3.insertBack (inp3);

}

System.out.print (

"LINKED1 HAS FOLLOWING NODES ALPHABETICALLY ARRANGED:::");

linked1.print();

System.out.print ("\nLINKED2 HAS FOLLOWING NODES IN REVERSE" + " ORDER OF THEIR ARRIVALS::: ");

linked2.print();

System.out.print ("\nLINKED3 HAS FOLLOWING NODES IN ORDER"

                                + " OF THEIR ARRIVALS::: ");

linked3.print();

String wanted = "A AND B OR C";

int where = linked1.search (linked1.firstNode, wanted, 0);

String output = "\nIN THE LIST1, THE POSITION OF \"" + wanted + "\" IS " + where;

System.out.println (output);

System.exit(0);

} // end of main()

} // end class NodeList