Implementing Stacks: Linked List

The first implementation of a stack we will look at uses Linked Lists. The idea here is to keep a linked list which consists of a node with strings in them that keeps track of the next strings (singly linked list for stacks). A stack within this context would insert a new node at the beginning of the linked list when using a push operation and similarly would remove a node at the beginning of the linked list on a pop operation. This is achieved by maintaining a pointer to the head of the linked list as the target of our operation.

Inner class for linked data structures

An inner class is a way to describe that we will be manipulating node objects that each consist of a string and a reference to another node. Inner classes follow a Pascal case naming convention. Defining the encapsulation of an inner class will ensure its accessibility through out a program. As an example an inner class that is only meant to be used within the outer classes could be defined as private static.

Implementing Push and Pop

Assume the following inner class structure

private class Node{
  String item;
  Node next;
}

Pop

1. Save item to return

String item = first.item;

2. Delete first node

first = first.next;

3. Return saved item

return item;

Push

1. Save pointer to beginning of list

Node oldfirst = first;

2. Create a new node for the beginning

first = new Node();

3. Set the instance variables in the new node

first.item = "not";
first.next = oldfirst;

Full Code

public class LinkedStackOfStrings
{
  private Node first = null;

  private class Node
  {
    String item;
    Node next;
  }

  public boolean isEmpty()
  { return first == null; }

  public void push(String item)
  {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
  }

  public String pop()
  {
    String item = first.item;
    first = first.next;
    return item;
  }

}