Linked Lists, Stacks and Queues

Table of Contents

1. Session 2 (lab): Linked lists

1.1. Simple linked lists
1.2. More about simple linked lists

2. Homework

2.1. Simple linked lists
2.2. Circular linked lists

1. Session 2 (lab): Linked lists

1.1. Simple linked lists

Objective

Practice with some basic exercises about simple linked lists.

A review of the theory

A simple linked list is a data structure in which each element has a link to the next one in the list. Thus, a reference to the first element is enough to access to all the elements in the list. Figure 1 shows a schema of the data structure.

Figure 1. Graphical representation of a simple linked list

A linked list consists of nodes (objects of the Node class). Each of these nodes has to do two things: store the information of the position i and offer a link to the position i+1.

Exercise

Implement a class that models a simple linked list. Follow these steps:

Read carefully the functional requirements of the class.
Think about the design of the data structure. Will it extend any class? Will it implement any interface? Will it use objects of a different class? A sheet of paper and a pencil will help you.
In parallel to code development, implement a test class that simply instantiates an object and test its methods.

The class you're going to implement should be called MySimpleLinkedList. Use a Node as internal structure. You'll have to implement the Node class. The public methods that the MySimpleLinkedList class should offer are:

public boolean isEmpty(): Returns TRUE or FALSE, depending whether the list is empty or not.
public void insert(Object o): Inserts an object at the beginning of the list (the beginning is the element pointed by first in Figure 1.
public Object extract(): Removes the first element of the list. Returns the object that was stored in the removed element. Be careful when the list is empty.
public void print(int n): Prints to the standard output the value of the object stored at position n (the first element is the 0 element). If the list is smaller that n-1, then the method prints nothing. This method must not modify the content of the list.
public void print(): Prints the list from the beginning to the end. This method must not modify the content of the list.

Remember that you should create a MySimpleLinkedListTest class, that will let you check the behaviour of your developed code.

1.2. More about simple linked lists

Objective

Practice with some basic exercises about simple linked lists.

A review of the theory

If you already have the code of a simple linked list, you can reuse such code by simply extending it. You'll get part of the functionality with very few effort.

Exercise

Develop a class that models a linked list. You can reuse MySimpleLinkedList. Follow these steps:

Read carefully the functional requisites of the class. Be sure that you have understood what to do.
Think about the design of the data structure. Will it extend any class? Will it implement any interface? Will it use objects of a different class? A sheet of paper and a pencil will help you.
In parallel to code development, implement a test class that simply instantiates an object and test its methods.

The class you're going to develop should be called MyAdvancedLinkedList. The class should contain the following methods:

public void insert(Object o, int n): Inserts o at the position n of the list. If n is bigger than the list size, the element will be added to the last position. If the list was empty, the element will be inserted as the first and only element.
public Object extract(int n): Removes from the list the element at the position n, and returns the value that was stored in the removed element. After the execution of the method, the element at position n-1 must have a link to the position n+1. If the list is too short, the last element is extracted.
public String toString(int n): Returns a String, which is the textual representation of the object stored at the nth position of the list. If the list is smaller than n-1, the method returns null. This method must not modify the content of the list.
public String toString(): Returns a String, which is the result of the concatenation of the textual representation of every object in the list. Insert an space character between every two elements. This method must not modify the content of the list.

Remember that you should create a MyAdvancedLinkedListTest class, that will let you check the behaviour of your developed code.

2. Homework

2.1. Simple linked lists

Objective

Practice with some basic exercises about simple linked lists.

Exercise

If you hadn't time to do it, finish the exercises started in the laboratory. If you already finished them, take some minutes to review their code.

Develop the following methods in the MyAdvancedLinkedList:
In the MySimpleLinkedList class you had to create a method that removes the element at the beginning of the list and another method to add an object to the beginning of the list.

Is it possible to add an object to the end of the list? If you think so, create such method in MyAdvancedLinkedList.

Is it possible to remove an object from the end of the list? If you think so, create such method in MyAdvancedLinkedList.
Think of how to reuse toString() and toString(int n) to produce new versions of the the print() and print(int n) methods. Implement these new versions. Remember that you can overwrite extended methods.

2.2. Circular linked lists

Objective

View possible data structures that result from modifications of a linked list, and understand the similarities and differences with simple linked lists.

A review of the theory

Figure 2. Graphical representation of a simple linked list

A circular linked list is just a linked list in which the last element links to the first one, creating a loop. The structure is shown in Figure 3.

Figure 3. Graphical representation of a circular linked list

Exercise

CircularLinkedList is, as you can immagine, a circular linked list. Part of this class has already been implemented. First, download it and look at its source code.

CircularLinkedList.java

The method public static CircularLinkedList getExample() returns a list with a random number of elements from 0 to 9. Those elements belong to the Integer class, whose values range from -25 to 25. You can use this method to get a list and use it in your tests.

Create, in the CircularLinkedList class, the following methods:

public int size(): Returns the number of elements of the list.

After creating the method, consider to create a class attribute that stores the size. What is the benefit of such attribute? What is the cost of such attribute? In which situations is this attribute a better alternative?
public String toString(): Returns a String, which is the result of concatenating the textual representation of the objects in the list (a complete loop over the list). The first elelment will be the element linked from position. This method must not modify the content of the list. You must neither modify position.
public Object[] toArray(): Returns an Object array, whose positions will reference to the objects in the circular list. Obviously, the array does not contain a loop. The first element in the array (position 0) will be the object linked by position.
public MySimpleLinkedList toSimpleLinkedList(): Returns a simple linked list, whose values are references to the objects of the circular list. The first element of the returned list will be the element linked by position.

Remember that you should create a CircularLinkedListTest class, that will let you check the behaviour of your developed code. In that class you will have to use the public static CircularLinkedList getExample() method.

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010