The List Abstract Data Type - Data Structures in Java

The majority of real-world lists can be represented as 3 types: unsorted, sorted, and indexed. We will use list interfaces that support the similarities and differences between the 3 mentioned list types. We will also use both arrays and references (reference as in linked list, for example) to implement our Abstract Data Type (ADT). The differences between list types mostly involve the types of values stored in them. A significant structural difference between the list types is how the values are ordered.

Table of Contents

Prerequisite Knowledge: Comparing Objects

Stacks and queues only allow us to access the ends of our structure; pushing or popping the top elements of a stack, or enqueuing elements to the tail of the queue and dequeuing elements from the head of the queue.

On the other hand, lists gives us access to elements within the structure. Whether it be checking, inserting, or deleting elements from a list; list operations require us to compare the values of objects.

For comparisons, the comparison operator (==) can be used. But (==) actually compares the contents of two reference variables that point to the objects, not between the contents of the objects themselves. That means == checks if 2 different reference variable are pointing to the same object or not. == does not check if the contents of two different objects are the same. Figure 1 illustrates how the == operator works.

primitive_vs_nonprimitive_variables2 — Figure 1: Comparing primitive and non-primitive variables. Note that intA and intB refer to integers A & B; therefor comparing int A and int B evaluates to true.

The Equals Method

The comparison operator doesn’t compare the contents of objects. So one option is to use the equals method. This method can be used with Java objects of any class, because the equals method is exported from the Object class, which is the root of Java’s inheritance tree. For example, if c1 and c2 are objects of the class Circle, then we can compare them using c1.equals(c2).

The equals method works similarly to the comparison operator mentioned earlier. The equals method return equals only if the two variables reference the same object. But if we want to compare the contents of two difference objects, we need to redefine the equals method to fit our own needs.

Suppose we have a Circle class that features a radius attribute of type int. A good definition for equality of Circle objects is that they are equal if they have the same radii value. To implement this definition, lets add this method in the Circle class:

public boolean equals(Circle circle)
// A precondition is that circle != null
//
// Return true if the circle has the same radius;
// Otherwise return false.
{
	if (this.radius == circle.radius)
		return true;
	else
		return false;
}

So when a statement such as c1.equals(c2) is processed, the Circle class’s customized equals method is used, rather than the equals method of the Object class.

The take away is that we can define our own equals method in the way we see fit for comparing the objects of a class.

The Comparable Interface

We can use the equals method when checking whether a particular element is on a list. But to support a sorted list, we need to be able to tell when one object is less than, equal to, or greater than another object. The Java library provides the Comparable interface that ensure a class provides the aforementioned comparing functionality. The Comparable interface has only one abstract method:

public int compareTo(T o):
// Returns a negative integer, zero, or a positive integer if this object
// is less than, equal to, or greater than the specified object.
// T refers to type, o refers to object

The compareTo method returns an integer indicating the “size” relationship between the object invoking the compareTo method and the object passed as an argument of the compareTo method.

We will use the compareTo method to sort the elements of our sorted lists. In order to insure that the objects support the compareTo function, the objects or elements must be instantiated from a class that implements the Comparable interface.

Each class that implements the comparable interface is required to define its own custom compareTo method that matches the signature of the abstract compareTo method defined in the interface.

Since Java 5.0 was released, Java’s comparable interface can handle generics. Use of generic types with the compareTo method helps ensure that comparison takes place only between compatible objects.

Returning to the circle example, the Circle objects can be compared using the size of their radii. Here’s an example of a Circle class providing its own equals method while also implementing the Comparable interface:

public class Circle implements Comparable<circle>
{
	protected float radius;
	protected static final float PI = 3.14f;
	
	public Circle(float radius)
	{
		this.radius = radius;
	}
	
	public boolean equals(Circle circle)
	// preconditon: circle != null
	//
	// Returns true if the circles has the same radius;
	// Otherwise, return false.
	{
		if (this.radius == circle.radius)
			return true;
		else
			return false;
	}
	
	public int compareTo(Circle circle)
	// precondition: o != null
	//
	// Returns a negative integer, zero, or a positive integer according
	// to whether the Circle object is less than, equal to, or greater  
	// than the Circle Object in the parameters.
	{
		if (this.radius < circle.radius)
			return -1;
		else
			if (this.radius == circle.radius)
				return 0;
			else
				return 1;
	}
	
	public float perimeter()
	// Returns perimeter of this figure. 2Πr
	{
		return (2 * PI * radius);
	}
	
	public float area()
	// Returns area of circle Πr^2
	{
		return(PI * radius * radius);
	}
}

Both the compareTo and the equals methods only accepts arguments of class Circle, since we want to stick with comparisons between circle, and not other shapes.

It is good programming practice to keep methods consistent to each other. For example, between the equals and the compareTo methods, the equals method returns true for comparing two circles only if the compareTo method returns 0 for comparing the same two circles.

Attributes that are used to decide an order for a collection of objects, or a list of elements, can be dubbed the key of the collection. In the Circle class example, the circle radius is the key. So you can use the size of the radius to define the order of a list.

Lists

We all know intuitively what a list is. In our everyday lives, we use lists all the time- grocery lists, lists of assignments, playlists of songs, lists of e-mail addresses, and so on.

In computer programs, lists are extremely versatile ADTs that provide storage for information without imposing any limitations on how that information is added, accessed, or removed.

A programming would describe a list to you as a collection of elements that have a linear relationship with each other. A linear relationship means that, except for the first one, each element on the list has a unique successor. Also lists have a property intuitively called size, which is simply the number of elements on the list. Know that every list has a size.

Types of Lists

Lists can be unsorted or sorted. Unsorted simply indicate that the elements don’t have any particular order, whereas sorted intuitively mean that the elements are placed in a specific order, ie. numerically, alphabetically, size of an attribute, etc.

Another type of list is an indexed list, where elements can be accessed via position or index.

To figure out if an element is in a list or not, you can use the equals method.

To sort a list into a sorted list, you can use the compareTo method.

Preconditions for Our Lists

Given that we can design many different types of lists, lets keep things simple by assuming that our lists all:

Our lists are unbounded, meaning that if an element is added to a so called “full” list, then the array capacity automatically increases to accommodate the added element.
On our lists, we allow duplicate elements. So that when an operation may “find” any one of the duplicates, and there is no difference between duplicates, except position for indexed lists.
No supporting null elements, and null elements cannot be used as arguments.
Use minimal preconditions for our operations, and instead let the operation give you the feedback that you need.
- For example, a remove operation can returns a boolean value indicating whether operation succeeded. (this improves flexibility for the programs)
Our sorted lists are sorted in increasing order, staying consistent with how the compareTo operation works with objects in the list.
You must use the same criteria in both the equals and compareTo methods to determine equality.
- For instance, in a class called Circle in which you store the coordinates of the center (h, k) and the radius, r, you have to define the equality of two circles the same way in the equals() method and in the compareTo() method. You could not define circle1 to be equal to circle2 in equals() by seeing if they have the same center (h1 = h2 and k1 = k2), but then use the radii for equality in compareTo(), that is, if r1 == r2, then return 0.
The indexed lists will have contiguous set range, starting at 0.
- So for example, if we have a set range of 0-4, and the list method passes on a 6, then an exception will be raised.

List Interfaces: Understanding the Design

Know that the Java library’s List interface specifies 25 different operations/methods. We don’t need that many, so instead we will outline just the handful that we need.

The ListInterface

The design of the List Abstract Data Type (ADT) can be outlined with a Java interface. The methods that define the List ADT include:

size returns the number of elements on a list
toString returns a string representation of the list
add adds an object/element to the list through the argument of the add method.
- The add method must be customized for each variety of list. For example, the list might be ordered, unordered, singly-linked, doubly-linked, or even circular. So the add() method will be slightly different depending on each variety.
contains returns a boolean value that indicates if the list contains an equivalent to the object passed through the argument of the contains method. Note that the contains method uses the equals method for making the indication.
remove removes one instance of an element equivalent to the object passed through this method’s arguments, if it exists in the list. This method will also return a boolean that tells the programmer if an object was actually removed or not.
get returns an element equivalent to the object passed through this method’s arguments. If the object/element does not exist, null is returned. Know that object equivalency does not mean that they are identical.

A list has a linear relationship among its elements, meaning that to traversing the entire list requires going through first element to the last element iteratively. So the reset and getNext methods help us to do that.

reset Sets the current position to the first element on the list.
getNext Returns the next element and updates the current position to the next element’s position.

Know that there always exists a “current position” within the list. So getNext advances the current position to point to the next position. Finally, when the last element is returned by the getNext method, the current position pointer is automatically reset to the beginning of the list. This process is called iteration, because you can process the elements of a data structure (the List ADT in this example) one at a time sequentially when combined with a Loop. Additionally, the getNext method is also known as a iterator method because this method returns an element of a data structure and advances the current position to the next element.

You can use a code like this, let’s call it an iteration loop, to traverse through the whole list:

listSize = myList.size();
myList.reset();
for (int i = 0; i < listSize; i++)
{
	myElement = myList.getNext();
	// add statements here if you want to do something
	// with myElement as you traverse each element
}

Note that adding or deleting elements changes the size of the list, invalidating the iteration loop’s counting correctness. You might end up with repeated or skipped elements. To handle this situation, you could throw an exception, reset the current position with every insertion or deletion while using the iteration loop, or simply not allow transformation during the use of the iteration loop.

ListInterface.java

// The list is unbound, allows duplicate elements, does not allow null elements.
// So the precondition is that you do not pass null elements as arguments for any of methods.

public interface ListInterface<T>
{
	itn size();
	// return the number of elements on the list.
	
	void add(T element);
	// Adds an element to the list.
	
	boolean contains (T element);
	// Return true if the list contains an element e such that e.equals(element);
	// Otherwise, return false.
	
	boolean remove (T element);
	// Remove an element e from the list such that e.equals (element) and returns true;
	// If no such element exists, return false.
	
	T get(T element);
	// Returns an element e from this list such that e.equals(element);
	// If no such element exists, return null.
	
	String toString();
	// Returns a string representation of the list. 
	
	void reset();
	// Initializes current position to the first element of the list.
	
	T getnext();
	// Preconditions: The list is not empty, is reset, and not modified since the most recent reset
	//
	// Returns the element after the current position on the list.
	// If the current position is on the last element,
	// then it advances the current position to the first element
	// Otherwise, the current position advances to the next element.
}

The Indexed List Interface

The IndexedListInterface extends the ListInterface, so that IndexListInterface can do all what the ListInterface interface can do, but also all of the operations required for working with indexed lists.

Know that the elements inside an indexed list are indexed sequentially, from zero to one less the size of the list. For example, if a list has 3 elements, they are indexed 0,1,2. Also know that there are no “holes” in index lists, meaning that an index is not skipped.

So the IndexedListInterface below defines methods for adding, returning, transforming, and removing elements at the specified index position within the method’s parameters. A method for determining the index of an element is also included in this interface. Read the comments inside the code to learn more about each operation.

IndexedListInterface.java

// The IndexedListInterface extends the ListInterface,
// while adding methods needed for using indexed lists.

public interface IndexedListInterface<T> extends ListInterface<T>
{
	void add(int index, T element);
	// Throws IndexOutOfBoundsException if index argument is index < 0 or index >= size().
	// Otherwise, adds an element at the index position index specified in the arguments. Also, all current
	// elements at that specified index position and higher have 1 added to their index.
	
	T set(int index, T element);
	// Throws IndexOutOfBoundsException if index argument is index < 0 or index >= size().
	// Otherwise, first replace the element on the index position specified in the arguments.
	// Second, return the element that was replaced.
	
	T get(int index);
	// Throws IndexOutOfBoundsException if index argument is index < 0 or index >= size().
	// Otherwise, return the element at the index position specified in the arguments.
	
	int indexOf(T element);
	// First, check if the list contains an element e such that e.equals(element).
	// If an equivalent element is found, return the index of the first equivalent element found.
	// Otherwise, returns -1.
	
	T remove(int index);
	// Throws IndexOutOfBoundsException if index argument is index < 0 or index >= size().
	// Otherwise, First remove element on the index position specified in the arguments.
	// Secondly, return the removed element. Thirdly, all elements at the positions where the
	// element was removed & higher have 1 subtracted from their index.
}

…

Each method that accepts an index as an argument throws an exception if the index is invalid

[UnderConstruction]