So, i got it to print the list stack, but I am having trouble trying to remove t
ID: 3873640 • Letter: S
Question
So, i got it to print the list stack, but I am having trouble trying to remove the bottom half. This is java program
import javax.naming.LinkLoopException;
public class LinkedListStack {
private Node top; // the first node
// nest class to define linkedlist node
private class Node {
int value;
Node next;
public Object item;
}
public LinkedListStack() {
top = null;
}
// Remove value from the beginning of the list for demonstrating behaviour of stack
public int pop() throws LinkLoopException {
if (top == null) {
throw new LinkLoopException();
}
int value = top.value;
top=top.next;
Node first = null;
int size;
return value;
}
// Add value to the beginning of the list for demonstrating behaviour of stack
public void push(int value) {
Node oldHead = top;
top = new Node();
top.value = value;
top.next = oldHead;
}
public class removeBottomHalf
{
//for (Node x1 = top ; x1 != null ; x1 = x1.next)
// System.out.print(" " + x1.value);
}
public static void main(String args[]) throws LinkLoopException
{
LinkedListStack stack1=new LinkedListStack();
stack1.push(1);
stack1.push(7);
stack1.push(3);
stack1.push(4);
stack1.push(9);
stack1.push(2);
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
printList(stack1.top);
}
public static void printList(Node top) {
Node temp = top;
while (temp != null) {
System.out.print(" " + temp.value);
temp = temp.next;
}
System.out.println(" ");
}
}
Modify the LinkedStack class to include a new method called removeBottomHalf, which removes the half of elements sitting at the bottom of the stack Test the method using the Driver program. What is the time complexity of this method?Explanation / Answer
Please find my implementation.
import javax.naming.LinkLoopException;
public class LinkedListStack {
private Node top; // the first node
// nest class to define linkedlist node
private class Node {
int value;
Node next;
public Object item;
}
public LinkedListStack() {
top = null;
}
// Remove value from the beginning of the list for demonstrating behaviour of stack
public int pop() throws LinkLoopException {
if (top == null) {
throw new LinkLoopException();
}
int value = top.value;
top=top.next;
Node first = null;
int size;
return value;
}
// Add value to the beginning of the list for demonstrating behaviour of stack
public void push(int value) {
Node oldHead = top;
top = new Node();
top.value = value;
top.next = oldHead;
}
public void removeBottomHalf()
{
Node slow_ptr = top;
Node fast_ptr = top;
if (top != null)
{
Node prev = null;
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
prev = slow_ptr;
slow_ptr = slow_ptr.next;
}
System.out.println("The middle element is [" +
slow_ptr.value + "] ");
// setting next of prev node to null
prev.next = null;
}
}
public static void main(String args[]) throws LinkLoopException
{
LinkedListStack stack1=new LinkedListStack();
stack1.push(1);
stack1.push(7);
stack1.push(3);
stack1.push(4);
stack1.push(9);
stack1.push(2);
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
//stack1.pop();
printList(stack1.top);
stack1.removeBottomHalf();
printList(stack1.top);
}
public static void printList(Node top) {
Node temp = top;
while (temp != null) {
System.out.print(" " + temp.value);
temp = temp.next;
}
System.out.println(" ");
}
}
/*
Sample run:
2 9 4 3 7 1
The middle element is [3]
2 9 4
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.