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).

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".

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.

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".

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() {...}

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).

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.

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010