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