Class LinkedList has 5 incomplete methods, designated by the comment “Your part
ID: 3716661 • Letter: C
Question
Class LinkedList has 5 incomplete methods, designated by the comment “Your part to
complete”. Complete one method at a time and test it in class myTest where
indicated. Notice that you must test each method in class myTest and display its output with
proper label. For example, the output of testing method addFirst() with value 25 would be
like this:
Testing method addFirstNode()
Adding value 25 as first node.
List content before adding 25 is: 1 2 3 4 5
List content after adding 25 is: 25 1 2 3 4 5
public class LinkedList
{
private Node head, tail;
private int size;
//constructor to create a list object with head, tail, and size.
public LinkedList()
{
head = null;
tail = null;
size = 0;
}
//method add node to end of list
public void addLastNode(int data)
{
if (tail == null)
head = tail = new Node(data);//empty list
else
{
tail.next = new Node(data); //link new node as last node
tail = tail.next; //make tail pointer points to last node
}
size++; //increase list size by one
}
//================= your part to complete ==============
//method add first node
public void addFirstNode(int data)
{
//complete this method
}
//method add node at index
public void addAtIndex(int index, int data)
{
//complete this method
}
//method remove first node
public void removeFirstNode()
{
//complete this method
}
//method remove last node
public void removeLastNode()
{
//complete this method
}
//method remove node at index
public void removeAtIndex(int index)
{
//complete this method
}
//================= end of your part ==============
//method to print out the list
public void printList()
{
Node temp;
temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
//class to create nodes as objects
private class Node
{
private int data; //data field
private Node next; //link field
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
}
import java.util.Scanner;
public class myTest
{
public static void main (String[] args)
{
LinkedList myList = new LinkedList(); //create a list object
for (int i=1; i <= 5; i++) //add 5 nodes to the list
{
myList.addLastNode(i);
}
Scanner scan = new Scanner (System.in);
String s="";
System.out.print("Enter a string: ");
s = scan.nextLine();
System.out.println();
System.out.println("Input String: This is a test string");
System.out.print("Reversed String: string test is a This");
//print out the list content
// System.out.print("My test list values are: ");
// myList.printList();
//Write code to tast each completed method in class LinkedList
}
}
PART 2:
The goal is part to implement Stack ADT using linked-list implementation from Part 1 above.
Then, write a program to use an object of the developed Stack class to solve a practical
problem.
1. Reusing the code in class LinkedList.java you completed for part 1 above, develop a
new class, called Stack.java, to implement stack operations [push(e), pop(),
top(), size(), isEmpty()]we discussed in the slides (Stacks part).
2. Next, develop a simple test program called TestStack.java, similar to that in part 1
above, to test each stack operation in class Stack.
3. Using class Stack.java, implement another program, called ReverseString.java,
which prompts the user to enter a string of any length. Using class Stack, the program
LinkedList.java myTest.java
creates a stack object (see part 1 above) and uses the object to reverse the input string and
display both the original input string and the revered string.
For example, if the user enters This is a test string
The program output, including the prompt and input string, would be as follows:
----jGRASP exec: java -ea ReverseString
Enter a string: This is a test string
Input String: This is a test string
Reversed String: string test a is This
----jGRASP: operation complete.
Explanation / Answer
LinkedList.java
******************************
public class LinkedList
{
private Node head, tail;
private int size;
//constructor to create a list object with head, tail, and size.
public LinkedList()
{
head = null;
tail = null;
size = 0;
}
int getSize() {
return size;
}
//method add node to tail of list
public void addLastNode(int data)
{
if (tail == null)
head = tail = new Node(data);//empty list
else
{
tail.next = new Node(data); //link new node as last node
tail = tail.next; //make tail pointer points to last node
}
size++; //increase list size by one
}
//================= your part to complete ==============
//method add first node
public void addFirstNode(int data)
{
Node nptr = new Node(data);
size++ ;
if(head == null)
{
head = nptr;
tail = head;
}
else
{
nptr.next = head;
head = nptr;
}
}
//method add node at index
public void addAtIndex(int index, int data)
{
Node nptr = new Node(data);
Node ptr = head;
for (int i = 1; i < size; i++)
{
if (i == index)
{
Node tmp = ptr.next;
ptr.next = nptr;
nptr.next = tmp;
break;
}
ptr = ptr.next;
}
size++ ;
}
//method remove first node
public void removeFirstNode()
{
if(head != null) {
head = head.next;
size --;
}
}
//method remove last node
public void removeLastNode()
{
Node ptr = head;
while(ptr.next.next != null) {
ptr = ptr.next;
}
ptr.next = null;
size --;
}
//method remove node at index
public void removeAtIndex(int index)
{
if (index == 0)
{
head = head.next;
size--;
return ;
}
if (index == size-1)
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.next;
}
tail = t;
tail.next = null;
size --;
return;
}
Node ptr = head;
for (int i = 1; i < size - 1; i++)
{
if (i == index)
{
Node tmp = ptr.next;
tmp = tmp.next;
ptr.next = tmp;
break;
}
ptr = ptr.next;
}
size-- ;
}
//================= tail of your part ==============
//method to print out the list
public void printList()
{
Node temp;
temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
//class to create nodes as objects
private class Node
{
private int data; //data field
private Node next; //link field
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
}
MyTest.java
************************
import java.util.Scanner;
/* Class SinglyLinkedList */
public class MyTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
LinkedList list = new LinkedList();
System.out.println("Singly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Singly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.addFirstNode( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.addLastNode( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int index = scan.nextInt() ;
if (index <= 1 || index > list.getSize())
System.out.println("Invalid position ");
else
list.addAtIndex(index, num);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.removeAtIndex(p);
break;
case 5 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
list.printList();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Stack.java
*************************
import java.util.NoSuchElementException;
/* Class Stack */
class Stack
{
class Node {
private int data; //data field
private Node next; //link field
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
protected Node top ;
protected int size ;
/* Constructor */
public Stack()
{
top = null;
size = 0;
}
/* Function to check if stack is empty */
public boolean isEmpty()
{
return top == null;
}
/* Function to get the size of the stack */
public int getSize()
{
return size;
}
/* Function to push an element to the stack */
public void push(int data)
{
Node nptr = new Node(data);
nptr.next = null;
if (top == null)
top = nptr;
else
{
nptr.next = null;
top = nptr;
}
size++ ;
}
/* Function to pop an element from the stack */
public int pop()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
Node ptr = top;
top = ptr.next;
size-- ;
return ptr.data;
}
/* Function to check the top element of the stack */
public int peek()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
return top.data;
}
/* Function to display the status of the stack */
public void display()
{
System.out.print(" Stack = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = top;
while (ptr != null)
{
System.out.print(ptr.data + " ");
ptr = ptr.next;
}
System.out.println();
}
}
TestStack.java
*******************************
import java.util.NoSuchElementException;
/* Class Stack */
class Stack
{
class Node {
private int data; //data field
private Node next; //link field
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
public Node top ;
public int size ;
/* Constructor */
public Stack()
{
top = null;
size = 0;
}
/* Function to check if stack is empty */
public boolean isEmpty()
{
return top == null;
}
/* Function to get the size of the stack */
public int getSize()
{
return size;
}
/* Function to push an element to the stack */
public void push(int data)
{
Node nptr = new Node(data);
nptr.next = null;
if (top == null)
top = nptr;
else
{
nptr.next = top;
top = nptr;
}
size++ ;
}
/* Function to pop an element from the stack */
public int pop()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
Node ptr = top;
top = ptr.next;
size-- ;
return ptr.data;
}
/* Function to check the top element of the stack */
public int peek()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
return top.data;
}
/* Function to display the status of the stack */
public void display()
{
System.out.print(" Stack = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = top;
while (ptr != null)
{
System.out.print(ptr.data + " ");
ptr = ptr.next;
}
System.out.println();
}
}
ReverseString.java
*****************************
import java.util.Scanner;
public class ReverseString {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
Stack st = new Stack();
System.out.print("Enter a string: " );
String s = sc.nextLine();
System.out.println("The original string is: " + s);
for(char ch : s.toCharArray()) {
st.push(ch);
}
System.out.print("The reversed string is: ");
while(!st.isEmpty()) {
int data = st.pop();
System.out.print((char)(data));
}
}
}