Stacks as Linked Lists

Linked-Based Implmentation

In this section we study a link list based implementation of the Stack ADT. After discussing the link-based approach we compare our two stack implementation approaches.

To support a linked list implementation we first define a LLObjectNode class as before.

The LLObjectNode class

Recall from Chapter 2 that in order to create a linked list of strings defined a self referential class, LLStringNode, to act as the nodes of the list.

Our stacks must hold elements of class Object, not of class String. Therefore, we define a class analogous to the LLStringNode class called LLObjectNode.

public class LLObjectNode 
{
  private LLObjectNode link;
  private Object info;
  
  public LLObjectNode(Object info)
  {
    this.info = info;
    link = null;
  }
 
  public void setInfo(Object info){
    this.info = info;
  }

  public Object getInfo(){
    return info;
  }
   public void setLink(LLObjectNode link){
    this.link = link;
  }
  public LLObjectNode getLink()  {
    return link;
  }
} 

The Linked Stack Class operations

public class LinkedStack implements UnboundedStackInterface
{
  protected LLObjectNode top; // reference to the top of this stack
  public LinkedStack()
  {
    top = null;
  }
  public void push(Object item)
  // Adds an element to the top of this stack
  { 
    LLObjectNode newNode = new LLObjectNode(item);
    newNode.setLink(top);
    top = newNode;
  }     
  public Object pop()
  // Removes an element from the top of this stack
  {                  
    if ( ! isEmpty())
    {
      Object x = top.getInfo();
      top = top.getLink();
      return x;
    } else
      throw new StackUnderflowException("Pop attempted on an empty stack.");
  }
  public Object top()
  // Returns the element on top of this stack
  {                 
    if ( ! isEmpty())
      return top.getInfo();
    else
      throw new StackUnderflowException("Top attempted on an empty stack.");
  }
  public boolean isEmpty()
  // Checks if this stack is empty
  {              
    return top == null; 
  }

  public boolean isFull()
  // Checks if this stack is full
  {              
      return false;
  }
}

Example LinkedStack push operation

UnboundedStackInterface myStack;
myStack = new LinkedStack();
myStack.push(A);
myStack.push(B);
myStack.push(C);

Linked List Stack Pop

top = top.getLink( );

Three cases to consider:

1. more than one element on the stack-- the old top element is now possibly garbage (consider the above graphics: the C node has nothing pointing to it)

2. there was only one element on the stack--top now contains null (see popping of the A node)

3. attempt to pop when top==null-- we need to throw the underflow exception

Comparing Stack Implementations

Storage Size

Operation efficiency

Which is better?

Stack UML

.