Linked Lists, Stacks and Queues

Table of Contents

1. Session 4 (lab): Stacks and Queues

1.1. Implementing stacks with linked lists
1.2. Implementing queues with linked lists

2. Homework

2.1. Work with double linked lists
2.2. Deque implementation based on a Double Linked List
2.3. Stack and Queue implementations with Deques

1. Session 4 (lab): Stacks and Queues

1.1. Implementing stacks with linked lists

Objective

The resolution of this exercise expects that the student learns to implement a stack using linked lists as data structure.

Section 1

Implement an stack using a linked list as data structure. The stack must allow to store any object type and you must implement at least the following methods:

- Insert an object in the stack (push).

- Retrieve an object from the stack (pop).

- Retrieve the object from the top of the stack, without extracting.

- Find out if there is any object in the stack.

- Return the number of objects in the stack.

Design the class deciding methods name, their parameters and return value. (Tip: Create a Node class which stores the stack values).

Solution

The solution is included in the following listing:

/*
 * LinkedStack.java
 *
 */

public class LinkedStack {

  class Node {
    Object elem;
    Node Next;

    public Node(Object o) {
      elem = o;
      Next = null;
    }
  }

  Node end;
  int size;

  public LinkedStack() {
    end = null;
    size = 0;
  }

  public void push(Object o) {
    Node new_node = new Node(o);
    if (end == null)
      end = new_node;
    else {
      new_node.Next = end;
      end = new_node;
    }
    size++;
  }; // inserts an object onto the stack

  public Object pop() {
    if (end == null)
      return null;
    ;
    Object o = end.elem;
    end = end.Next;
    size--;
    return o;
  }// Gets the object from the stack

  public boolean isEmpty() {

    return (size == 0);
  }

  public int size() {

    return size;
  }

  public Object end() {

    if (end == null)
      return null;
    else
      return end.elem;
  }

} // class LinkedStack

Section 2

Implement a test class so that it reads lines from a file and prints them to console in reverse order. For example, if the file has four lines "A", "B", "C" and "D", it should print lines "D", "C", "B", "A".

Solution

The solution is included in the following listing:

import java.io.*;

public class TestLinkedStack {

  public static void main(String args[]) {

    FileReader f = null; // to read files
    BufferedReader reader = null; // reading buffer
    String line = null; // read lines
    LinkedStack stack = new LinkedStack(); // initialization

    if (args.length < 1) {
      System.err.println("Please invoke the program like this:");
      System.err.println("\tLinkedStack file");
    }

    // opens the file
    try {
      f = new FileReader(args[0]);
      reader = new BufferedReader(f);
      while ((line = reader.readLine()) != null)
        stack.push(line);
    } catch (Exception e) {
      System.err.println("File not found " + args[0]);
      return;
    }

    // Gets the strings from the stack and prints them
    while ((line = (String) stack.pop()) != null) {
      System.out.println(line);
    }
  }

}

1.2. Implementing queues with linked lists

Objective

The resolution of this exercise expects that the student learns to implement a queue using linked lists as data structure.

Section 1

Implement a queue using a linked list as data structure. The queue must allow to store any object type and you must implement at least the following methods:

- Insert an object onto the queue (enqueue).

- Retrieve an object from the queue (dequeue).

- Retrieve the first object in the queue, without extracting it (first).

- Find out if there is any object in the queue (isEmpty).

- Return the number of objects in the queue (size).

Design the class defining the name of the methods, their parameters and return value.

Solution

The solution is included in the following listing:

	      /*
 * LinkedQueue.java
 *
 */

public class LinkedQueue {

  class Node {
    Object elem;
    Node Next;

    public Node(Object o) {
      elem = o;
      Next = null;
    }
  }

  Node first;
  Node end;
  int size;

  public LinkedQueue() {
    end = null;
    size = 0;
  }

  public void enqueue(Object o) {
    Node new_node = new Node(o);
    if (first == null) {
      first = new_node;
      end = new_node;
    } else {
      end.Next = new_node;
      end = new_node;
    }
    size++;
  }; // inserts an object onto the queue

  public Object dequeue() {
    if (first == null)
      return null;
    ;
    Object o = first.elem;
    first = first.Next;
    size--;
    return o;
  } // gets the object from the queue

  public boolean isEmpty() {
    return (size == 0);
  }

  public int size() {
    return size;
  }

  public Object first() {
    if (first == null)
      return null;
    else
      return first.elem;
  }

} // class LinkedQueue

Section 2

Again, implement a test class so that it reads lines from two files and prints them all to console at once. For example, if the first file has two lines "A" and "B", and the second file has two lines "C" and "D", it should print lines "A", "B", "C" and "D".

Solution

The solution is included in the following listing:

	      import java.io.*;

public class TestLinkedQueue {

  public static void main(String args[]) {

    FileReader f = null; // to read files
    BufferedReader reader = null; // reading buffer
    String line = null; // read lines
    LinkedQueue queue = new LinkedQueue(); // initialization

    if (args.length < 1) {
      System.err.println("Please invoke the program like this:");
      System.err.println("\tLinkedQueue file1 file2");
    }

    // opens the first file
    try {
      f = new FileReader(args[0]);
      reader = new BufferedReader(f);
      while ((line = reader.readLine()) != null)
        queue.enqueue(line);
    } catch (Exception e) {
      System.err.println("File not found " + args[0]);
      return;
    }

    // opens the second file
    try {
      f = new FileReader(args[1]);
      reader = new BufferedReader(f);
      while ((line = reader.readLine()) != null)
        queue.enqueue(line);
    } catch (Exception e) {
      System.err.println("File not found " + args[1]);
      return;
    }

    // Gets the strings from the queue and prints them
    while ((line = (String) queue.dequeue()) != null) {
      System.out.println(line);
    }
  }

}

2. Homework

2.1. Work with double linked lists

Objective

To study in depth the use of linked list data structures.

Exercise

The List class represents a linear collection of data organized in a linked list. This list shows the peculiarity of storing a reference to a particular node in the list, which is pointed by the reference currentPosition and on which data insertion and extraction operations are performed.

The reference currentPosition must be able to move forwards and backwards through the list, position by position. It is therefore appropriate for the list to be double linked, i.e. each node store a reference not only to the following node in the list, but also to the node that precedes it. The following figure illustrates the structure of the list with an example:

The basic operations this list should allow are:

Move the reference position forwards: the reference is moving forwards as many positions as indicated. If the list is empty or the number of positions to move forwards is not greater than zero, nothing is done. If it is required to move it forwards more positions than number of nodes from the current position up until the end of the list, advance currentPosition only until the last node. If currentPosition points to null before proceeding, it is first placed pointing to the first node of the list, and then moved forwards the specified number of positions minus one (for example, if it is required to move 5 positions forwards and currentPosition points initially to null, then currentPosition is first placed pointing to the first node, and then moved 4 positions from this first one).
Move the currentPosition reference backwards: the reference currentPosition must go backwards as many positions as indicated. If the list is empty or the number of positions to move backwards is not greater than zero, nothing is done. If it is required to move backwards more positions than number of nodes from the current position up until the first node of the list, the reference will remain in this first node.
Insert new data in the list: a new node is inserted to save this data, immediately following currentPosition, i.e. the new node will follow the node currently referenced by currentPosition. When currentPosition is null, the new node is inserted into the top of the list. After the insertion, currentPosition must point to the new node inserted.
Extracting data from the list: return the data pointed by currentPosition, delete the node, and moves currentPosition to the next node (currentPosition will point to null if there is no next node). If currentPosition is pointing to null, nothing is extracted and null is returned.

Program the Node class, the List class and the following methods of the List class:

public void moveForwards(int numPositions) {...}
public void moveBackwards(int numPositions) {...}
public void insert(Object data) {...}
public Object extract() {...}

Solution

The solution is included in the following listing:

/**
 * <p>Universidad Carlos III de Madrid</p>
 *
 * @author Departamento de Ingenieria Telematica. UC3M.
 * @version 1.0
 */

/**
 * 
 * <p>
 * 'Playing' with double linked list
 * </p>
 * 
 * 
 * @author Departamento de Ingenieria Telematica. UC3M.
 * @version 1.0
 */

public class List {

  // nested class
  public class Node {
    Node next;
    Node previous;
    Object data;

    public Node(Node next, Object data) {
      this.next = next;
      this.data = data;
    }

    public Node(Object elem) {
      this(null, elem);
    }
  }

  private Node first;
  private Node currentPosition;

  /**
   * Increments current position -numPositions-
   */
  public void forward(int numPositions) {
    if (numPositions > 0 && first != null) {
      int positionsForward = numPositions;
      if (currentPosition == null) {
        currentPosition = first;
        positionsForward--;
      }
      while (currentPosition.next != null && positionsForward > 0) {
        currentPosition = currentPosition.next;
        positionsForward--;
      }
    }
  }

  /**
   * Inserts an object in --currentPosition-.
   */
  public void insert(Object data) {
    Node node = new Node(data);

    if (currentPosition == null) {
      // inserts in first node
      node.next = first;
      if (first != null) {
        first.previous = node;
      }
      first = node;
    } else {
      // the node isn't the first.
      node.next = currentPosition.next;
      node.previous = currentPosition;
      if (currentPosition.next != null) {
        currentPosition.next.previous = node;
      }
      currentPosition.next = node;
    }

    // updates current position
    currentPosition = node;
  }

  /**
   * Delete the node referenced by -currentPosition-.
   * 
   * @return The object to delete
   */
  public Object extract() {
    Object data = null;

    if (currentPosition != null) {
      data = currentPosition.data;

      // 'delete' the node
      if (first == currentPosition) {
        first = currentPosition.next;
      } else {
        currentPosition.previous.next = currentPosition.next;
      }

      if (currentPosition.next != null) {
        currentPosition.next.previous = currentPosition.previous;
      }

      // next position
      currentPosition = currentPosition.next;
    }
    return data;
  }

  /** testing program */
  public String toString() {
    Node aux = first;
    StringBuffer sb = new StringBuffer();
    while (aux != null) {
      sb.append(aux.data);
      aux = aux.next;
    }
    return sb.toString();
  }

  /**
   * Go back -numPositions-
   */
  public void back(int numPositions) {
    if (numPositions <= 0 || first == null || currentPosition == null)
      return;
    int positionsBack = numPositions;
    while (currentPosition != null && positionsBack > 0) {
      currentPosition = currentPosition.previous;
      positionsBack--;
    }
  }

  /** Test method */
  public static void main(String[] args) {
    List list = new List();
    list.insert("Node1");
    list.insert("Node2");
    System.out.println("Initial list: " + list.toString());
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("Add Node: ");
    list.insert("Node3");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.back(1);
    System.out.println("Go back one position");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.insert("Node4");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("delete... ");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    System.out.println("Go forward 7 ");
    list.forward(7);
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.back(1);
    list.extract();
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
    list.forward(1);
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
  }
}

2.2. Deque implementation based on a Double Linked List

Objective

To learn how to work with Deques.

Exercise

A Deque, is a linear data structure that permits to insert and to remove elements on both sides. To build it, we will be based on the use of a Double Linked List (DLL) on which we will implement the corresponding methods to achieve such behaviour.

A Deque's behaviour can be achieved by the implementation of the following interface that shows its main methods:

/**
 * Interface for a Deque.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Dqueue {

  void insertFirst(Object obj);

  void insertLast(Object obj);

  Object removeFirst();

  Object removeLast();

  int size();
}

To implement a Deque by using a DLL, perform the following tasks:

Program the DNode class which represents the node of a Double Linked List (DLL). Such node will contain both prev and next references to the previous and next node of the current one, as well as an Object reference to the data to be stored.
Declare the DLDqueue class that will implement a Deque based on a DLL. In order to do this, it must implement the Dqueue interface that has been previously mentioned.
Add the head and tail attributes that represents the nodes at both ends of the DLL and the integer attribute size that permits to store the size of it.
Program the constructor of the DLDqueue class that initializes the head and tail references to an emtpy DLL node and set the size to 0.
Program the following methods of the Dqueue's interface:
- public void insertFirst(Object obj)
  
  This method inserts an object at the beginnig of the DLL.
- public void insertLast(Object obj)
  
  This method inserts an object at the end of the DLL.
- public Object removeFirst()
  
  This method extracts an object from the beginning of the DLL and removes it from the list. If such object does not exist, the method returns null.
- public Object removeLast()
  
  This method extracts an object from the end of the DLL and removes it from the list. If such object does not exist, the method returns null.
- public int size()
  
  This method returns the size of the DLL list.
Finally, implement the public String toString() method that permits to print the content of the Deque on console according the next format (the shown values are examples):

head [ 1-2-3-4-5 ] tail

IMPORTANT NOTE!!

In this exercise, we have practice with the design and implementation of a Deque. However, in the Java API there are also several classes that implement such data structures. A Deque is defined by the following interface: Interface Deque. There are also two possible class implemntations of it, one that is based on arrays (ArrayDeque) and another one based on linked lists (LinkedList).

Solution

Solutions are included in the following listings:

/**
 * An Implementation of a Double Linked List Node
 * 
 * @author DIT-UC3M
 * 
 */
public class DNode {

  DNode next, prev;
  Object val;

  public DNode() {

    this.next = null;
    this.prev = null;
    this.val = null;
  }

  public DNode(Object val, DNode first, DNode last) {

    this.next = first;
    this.prev = last;
    this.val = val;
  }

  public DNode getNext() {
    return next;
  }

  public void setNext(DNode next) {
    this.next = next;
  }

  public DNode getPrev() {
    return prev;
  }

  public void setPrev(DNode prev) {
    this.prev = prev;
  }

  public Object getVal() {
    return val;
  }

  public void setVal(Object val) {
    this.val = val;
  }

}

/**
 * Class that implements a Deque with a Double Linked List.
 * 
 * @author DIT-UC3M
 * 
 */
public class DLDqueue implements Dqueue {
  DNode head, tail;
  int size;

  public DLDqueue() {
    head = new DNode();
    tail = new DNode();
    head.setNext(tail);
    tail.setPrev(head);
    size = 0;
  }

  public void insertFirst(Object obj) {
    DNode h = head;
    DNode node = new DNode();
    node.setVal(obj);
    node.setNext(h);
    h.setPrev(node);
    head = node;
    if (size == 0)
      tail = node;
    size++;

  }

  public void insertLast(Object obj) {
    DNode t = tail;
    DNode node = new DNode();
    node.setVal(obj);
    node.setPrev(t);
    t.setNext(node);
    tail = node;
    if (size == 0)
      head = node;
    size++;
  }

  public Object removeFirst() {
    if (head == null)
      return null;
    Object val = head.getVal();
    head = head.getNext();
    size--;
    return val;
  }

  public Object removeLast() {
    if (tail == null)
      return null;
    Object val = tail.getVal();
    tail = tail.getPrev();
    size--;
    return val;
  }

  public int size() {
    return size;
  }

  public String toString() {
    String s = "head [";
    DNode aux = head;
    for (int i = 0; i < size; i++) {
      s += aux.getVal();
      if (aux == tail) {
        break;
      }
      s += "-";
      aux = aux.getNext();
    }
    return s + "] tail";
  }

}

2.3. Stack and Queue implementations with Deques

Objective

To learn how to make a Deque to behave as a Stack or a Queue.

Exercise

In this exercise, we will take advantage of the flexiblity of a Deque to make it behave as if it was a Stack or a Queue. For this, we will force the class using the Deque to implement the corresponding interface that is shown next:

Stack interface:

/**
 * Interface for a Stack.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Stack {

  void push(Object obj);

  Object pop();

  int size();
}

Queue interface:

/**
 * Interface for a Queue.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Queue {

  public void enqueue(Object obj);

  public Object dequeue();

  int size();
}

Next, let's use a Deque to implement both a Stack or a Queue. In order to do this, perform the following tasks:

To implement a Stack by a Deque:
1. Declare the DQStack class that should behave like a Stack. In order to do this, it should implement the Stack interface that has been previously mentioned.
2. Add a data attribute of DLDqueue type which constitutes the list where stack's data will be stored.
3. Program the DQStack class constructor that should initialize the data attribute creating an instance of a DLDqueue class.
4. Program the following methods of the Stack's inteface:
  - public void push(Object obj)
    
    This method inserts an object at the beginning of the DLDqueue.
  - public Object pop()
    
    This method extracts an object from the beginning of the DLDqueue and it removes it from the list. If such object does not exist, the method returns null.
  - public int size()
    
    This method returns the size of the DLDqueue.
5. Implemet the main method to test the Stack. It must instantiate a DQStack object, pushing and popping several data while it prints on console the content and the size of the stack.
To implement a Queue by a DLDqueue:
1. Declare the DQQueue class that should behave like a Queue. In order to do this, it should implement the Queue interface that has been previously mentioned.
2. Add a data attribute of DLDqueue type which constitutes the list where queue's data will be stored.
3. Program the DQQueue class constructor that should initialize the data attribute creating an instance of a DLDqueue class.
4. Program the following methods of the Queue's inteface:
  - public void enqueue(Object obj)
    
    This method inserts an object at the beginning of the DLDqueue.
  - public Object dequeue()
    
    This method extracts an object from the end of the DLDqueue and it removes it from the list. If such object does not exist, the method returns null.
  - public int size()
    
    This method returns the size of the DLDqueue.
5. Finally, implement the main method to test the Queue. It must instantiate a DQQueue object, queueing and enqueueing several data while it prints on console the content and the size of the queue.

Solution

Solutions are included in the following listings:

/**
 * Interface for a Stack.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Stack {

  void push(Object obj);

  Object pop();

  int size();
}

/**
 * Interface for a Queue.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Queue {

  public void enqueue(Object obj);

  public Object dequeue();

  int size();
}

/*
 * Class that implements a Stack with a Deque
 *  
 * @author DIT-UC3M 
 *
 */
public class DQStack implements Stack {

  private Dqueue data;

  public DQStack() {
    data = new DLDqueue();
  }

  public void push(Object obj) {
    data.insertFirst(obj);
  }

  public Object pop() {
    return data.removeFirst();
  }

  public int size() {
    return data.size();
  }

  public String toString() {
    return data.toString();
  }

  public static void main(String[] args) {
    DQStack stack = new DQStack();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    System.out.println("Printing stack: " + stack);

    int s = stack.size();
    System.out.println("Printing size: " + stack.size());

    Object o = stack.pop();
    System.out.println("Pop element = " + o);

    System.out.println("Printing stack: " + stack);

  }
}

/*
 * Class that implements a Queue with a Deque
 *  
 * @author DIT-UC3M 
 *
 */
public class DQQueue implements Queue {

  private Dqueue data;

  public DQQueue() {
    data = new DLDqueue();
  }

  public void enqueue(Object obj) {
    data.insertFirst(obj);
  }

  public Object dequeue() {
    return data.removeLast();
  }

  public int size() {
    return data.size();
  }

  public String toString() {
    return data.toString();
  }

  public static void main(String[] args) {
    DQQueue queue = new DQQueue();
    for (int i = 0; i < 5; i++) {
      queue.enqueue(i);
    }
    System.out.println("Printing queue: " + queue);

    int s = queue.size();
    System.out.println("Printing size: " + queue.size());

    Object o = queue.dequeue();
    System.out.println("Deque element = " + o);

    System.out.println("Printing queue: " + queue);

  }
}

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010