Perform the Big O analysis for each method in the LinkedStack<T> class. The Link

Question

Perform the Big O analysis for each method in the LinkedStack<T> class.

The LinkedStack<T> class code is written below:

package jsjf;

import jsjf.exceptions.*;

/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;

/**
* Creates an empty stack.
*/
public LinkedStack()
{
count = 0;
top = null;
}

/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed on stack
*/
public void push(T element)
{
LinearNode<T> temp = new LinearNode<T>(element);

temp.setNext(top);
top = temp;
count++;
}

/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element from top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
   throw new EmptyCollectionException("stack");

T result = top.getElement();
top = top.getNext();
count--;

return result;
}

/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T peek() throws EmptyCollectionException
{

   if(isEmpty())
   {
       throw new EmptyCollectionException("stack");
   }

   return top.getElement();

}

/**
* Returns true if this stack is empty and false otherwise.
* @return true if stack is empty
*/
public boolean isEmpty()
{
   if(isEmpty())
   {
   return true;
   }
else
{
    return false;
}

}

/**
* Returns the number of elements in this stack.
* @return number of elements in the stack
*/
public int size()
{
return count;
/**
*keeping the track of the number
*of elements in the stack.
*/
}

/**
* Returns a string representation of this stack.
* @return string representation of the stack
*/
public String toString()
{
String result = "";       // initialize it to empty string
LinearNode current = top;   // start from top
while (current != null)   // iterate until it reaches the end of the list (end of list is when current == null)
{
result = result + (current.getElement()).toString() + " ";   // append it's value to result string
current = current.getNext();    // make current points to next element
}
return result;   // return result string
}
}

Explanation / Answer

Please find my analysis.

Please let me know in case of any issue:

public void push(T element):

   THis method adding new Node at front of top Node
   It takes O(1) time

public T pop():
   We are removing front element from linked list:
   It takes O(1) time

public T peek():
   We are returning the value of front Node from linked list:
   It takes O(1) time

public boolean isEmpty():
   We are returning true/false base on count value
   It takes O(1) time

public int size():
   returning count value
   It takes O(1) time

public String toString():
   We are traversing whole node to get info of all nodes in linked list
   It takes O(n) time

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.