Homework SourseWrite a Java Class to Implement a Generic Linked List Your l
Write a Java Class to Implement a Generic Linked List
Your list must be implemented as a singly-linked list of generic nodes, where each Node object has two instance variables: an object of the “type variable” class, and a pointer to the next node on the list.
Your class will contain separate methods to handle each of the operations read from a data file (see II., below)
Your class will also override toString() to return the objects on the list in the order in which they occur.
Write a Test Class for Your LinkedList Class
Your main method will read list operation instructions from a data file, until end-of-file and call the appropriate LinkedList method to execute each one.
After each operation is executed, print out the operation and the updated list.
The data file to be used is on the class web site and the operations are:
APPEND X - Append object X to the end of the list
ADD N X - Insert object X as the new Nth element in the list, increasing the size of the list by 1
E.g. Suppose the list is:
head -> 1 -> 2 -> 3 -> 4 -> null
After ADD 3 7 it would be:
head -> 1 -> 2 -> 7 -> 3 -> 4 -> null
DELETE N – Remove the Nth object from the list
SWAP M N - Interchange the positions of the Mth and Nth
objects on the list
For credit, the two nodes must actually \"trade places\" in the list, and not merely swap their data values
REVERSE - Reverse the order of the objects on the list
This must be done by reversing the order of the nodes themselves, rather than by swapping the data stored
To get credit for your reverse() method, it must use either one of these 2 algorithms:
For each node on the list except the current “head”
node, delete the node and insert it as the new head
Use your swap() method
6. CLEAR – Clear the list (make it empty)
No credit will be given for programs that use any additional data structures – either from the Java API or programmer defined -, other than your own LinkedList class
txt file:
Solution
//Java Program to Implement Singly Linked List
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
/* Class Node */
class Nodes
{
protected Object data;
protected Nodes next;
/* Constructor */
public Nodes()
{
next = null;
data = null;
}
/* Constructor */
public Nodes(Object d,Nodes n)
{
data = d;
next = n;
}
/* Function to set link to next Node */
public void setLink(Nodes n)
{
next = n;
}
/* Function to set data to current Node */
public void setData(Object d)
{
data = d;
}
/* Function to get link to next node */
public Nodes getLink()
{
return next;
}
/* Function to get data from current Node */
public Object getData()
{
return data;
}
}
/* Class linkedList */
class linkList
{
protected Nodes start;
protected Nodes end ;
public int size ;
/* Constructor */
public linkList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Nodes nptr = new Nodes(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Nodes nptr = new Nodes(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Nodes nptr = new Nodes(val, null);
Nodes ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Nodes tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Nodes s = start;
Nodes t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Nodes ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Nodes tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print(\"\ Singly Linked List = \");
if (size == 0)
{
System.out.print(\"empty\ \");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Nodes ptr = start;
System.out.print(start.getData()+ \"->\");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ \"->\");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ \"\ \");
}
public void reverse()
{
// For first node, previousNode will be null
Nodes previousNode=null;
Nodes nextNode;
while(start!=null)
{
nextNode=start.next;
// reversing the link
start.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=start;
start=nextNode;
}
start=previousNode;
}
public void swapNodesP(int x,int y ){
if(start==null) return;
else{
Nodes n1=start,n2=start,n3=null;
for(int i=1;i<x-1;i++)
n1=n1.next;
for(int i=1;i<y;i++)
n2=n2.next;
n3=n1.next;
n1.next.next=n2.next;
n1.next=n2;
n2.next=n3;
}
}
public void swapNodes(Object x, Object y)
{
// Nothing to do if x and y are same
if (x == y) return;
// Search for x (keep track of prevX and CurrX)
Nodes prevX = null, currX = start;
while (currX != null && currX.data != x)
{
prevX = currX;
currX = currX.next;
}
// Search for y (keep track of prevY and currY)
Nodes prevY = null, currY = start;
while (currY != null && currY.data != y)
{
prevY = currY;
currY = currY.next;
}
// If either x or y is not present, nothing to do
if (currX == null || currY == null)
return;
// If x is not head of linked list
if (prevX != null)
prevX.next = currY;
else //make y the new head
start = currY;
// If y is not head of linked list
if (prevY != null)
prevY.next = currX;
else // make x the new head
start = currX;
// Swap next pointers
Nodes temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}
public void clear(){
start=null;
System.out.print(\"null->\");
}
}
/* Class SinglyLinkedList */
public class TestClass {
public static void main(String[] args)
{
String line=null;
/* Creating object of class linkedList */
linkList list = new linkList();
System.out.println(\"Singly Linked List Test\ \");
String s,fileName=\"c:/eclipse/operations.txt\";
int i,j;
try{
BufferedReader br = new BufferedReader(new FileReader(fileName));
while((line = br.readLine()) != null) {
s=line.toString();
if(s.contains(\"APPEND\"))
{
i=(int)Integer.parseInt(line.substring(7).toString().trim());
list.insertAtEnd(i );
list.display();
}
else if(s.contains(\"ADD\")) {
i=(int)Integer.parseInt(line.substring(4,7).toString().trim());
j=(int)Integer.parseInt(line.substring(6,8).toString().trim());
list.insertAtPos(i,j);
list.display();
}
if(s.contains(\"DELETE\")){
i=(int)Integer.parseInt(line.substring(7).toString().trim());
list.deleteAtPos(i);
list.display();
}
else if(s.contains(\"REVERSE\")) {
list.reverse();
list.display();
}
else if(s.contains(\"SWAP\")){
i=0;j=0;
i=(int)Integer.parseInt(line.substring(5,6).toString().trim());
j=(int)Integer.parseInt(line.substring(7,8).toString().trim());
list.swapNodesP(i,j);
list.display();
}
else if(s.contains(\"CLEAR\")){
list.clear();
}
}
// Always close files.
br.close();
}
catch(FileNotFoundException ex) {
System.out.println(
\"Unable to open file \'\" +
fileName + \"\'\");
}
catch(IOException ex) {
System.out.println(
\"Error reading file \'\"
+ fileName + \"\'\");
}
}
}
