Probably the most commonly used data structures are the linear (list) data structures. They are an abstraction of all kinds of rows, sequences, series and others from the real world.

The List ADT

List is a linear data structure, which contains a sequence of elements

A1, A2, A3, …, AN

N is the property length of the list (count of elements) and its elements are arranged consecutively with Ai before Ai+1

A1: first element, AN: last element, Ai: position i

If N = 0 then the list is empty

The list allows adding or inserting elements at different positions, deleting them , traversing from start to end (for example to print the contents of the list) and searching to find a specific element.

can define the List ADT as follows:

Characteristics

Length identifies the number of elements in the list

Operations

Add an element to the list - insert

Delete an element from the list - remove

Show the elements in the list - printList

Find an element in the list - find

Create an empty list - createList

Implementation of the List ADT

As noted previously, there can often be more than one way of implementing an ADT, and this is true for the List ADT. To implement List we need to:
1. Choose an internal data structure, i.e. how we actually store the elements of the List
2. Figure out the algorithm needed for each of the major operations in the List ADT
3. For each operation, write a function or method to implement the algorithm

When choosing the internal structure, we should consider the following:

Each element needs to be stored as an individual data item

The storage must allow the characteristics of the List to be represented. Remember that elements are arranged consecutively, and each element has a position, or index, in the list.

There are two standard implementations for the List ADT

Array list

Linked list

We will look at each of these, starting with the former as it is based on something you are already familiar with – the array. Note that an array in Java does not provide operations, so it is not a data structure, but it can provide a basis for implementing a data structure.

Elements are stored in contiguous array positions

An array is an indexed structure. In an indexed structure:

elements can be accessed in sequence using a loop that increments the subscript – SEQUENTIAL order

elements may be accessed in any order using subscript values – RANDOM order

With a Java Array you cannot:

increase or decrease its length (length is fixed)

add an element at a specified position without shifting elements to make room

remove an element at a specified position and keep the elements contiguous without shifting elements to fill in the gap

If you implement a list by storing the data in an array, these characteristics need to be taken into consideration.

Firstly, you need to estimate how much data the list is likely to need to hold, i.e. the maximum size of the list. When the length of the list is less than the size of the array, the rest of the array will be empty. You might then encounter situations where that estimate is too low - if there is not enough space in the array then ‘fatal errors’ have to be guarded against. It is usual to overestimate the size - thus wasting space.

Secondly, you need to consider how well the operations will perform when implemented as an array. When you have only a small set of data then this doesn't matter much, but if you have a very large list then the time taken to perform the operations can become significant.

Limitations of static arrays

Arrays are:

Simple,

Fast

but

Must specify size at construction time, which can't then change – static structure

Have to cater for possibility of under / over flow

"Murphy’s law"

Construct an array with space for n, where n = twice your estimate of largest collection….

Tomorrow you’ll need n+1

Need a more flexible/dynamic system.

The Java ArrayList class

The Java API provides implementations of a range of data structures, called the Collections Framework. These are in the package java.util, and include interfaces and classes that implement these. The List interface is implemented by classes that provide List data structures. Note that the names of the operations in the ArrayList class are a bit different from the List ADT we have defined here, and there are many more of them.

The simplest class that implements the java List interface is the ArrayList class. It uses an array to store the data in the list but overcomes the limitations of static arrays. It is a dynamic structure which can resize itself when it is nearly full. It does so by creating a new, larger array, copying the data to that, and discarding the old one.

The ArrayList class is particularly useful when:

you will be adding new elements to the end of a list

you need to access elements quickly in any order

Examples - using the ArrayList class

Need to import the ArrayList class and List interface:

import java.util.ArrayList;
import java.util.List;

To declare a List “object” whose elements will reference String objects (note that the ArrayList class is generic – it can store any kind of object, and you specify the type of object to store in <> when you create the ArrayList instance):

List<String> myList = new ArrayList<String>();

The initial List is empty and has a default initial capacity of 10 elements

To add strings to the list – the add operation places the new element at the end of the list:

myList.add("Glasgow"); 
myList.add("Edinburgh");
myList.add("Aberdeen");   
myList.add("Dundee");

📷 View Result

Adding an element with subscript 2:

myList.add(2, "Inverness");

📷 View Result

Notice that the subscripts of "Aberdeen" and "Dundee" have changed from [2],[3] to [3],[4]

When no subscript is specified, an element is added at the end of the list:

myList.add("Stirling");

📷 View Result

Removing an element:

myList.remove(1);

📷 View Result

The strings referenced by [2] to [5] have changed to [1] to [4]

You may also replace an element:

myList.set(2, "Perth");

📷 View Result

You cannot access an element using a bracket index as you can with arrays (array[1])

Instead, you must use the get() method:

String city = myList.get(2);

The value of city becomes "Perth"

You can also search an ArrayList:

int pos = myList.indexOf("Perth");

This returns 2 while

int pos = myList.indexOf("Paisley");

returns -1 which indicates an unsuccessful search

ArrayList also supports Java streams, which allows powerful searching using lambda expressions. The following example finds the first element that starts with “P”, so returns “Perth”:

String city = myList.stream().filter(
   s -> s.startsWith("P")).findFirst().get();

You can see the full documentation for the ArrayList class at 🔗 https://docs.oracle.com/javase/9/docs/api/java/util/ArrayList.html

The Java Collections Framework classes are sophisticated, tried and tested implementations of common data structures. You would normally only create your own implementation if you need a structure that is not included in the Framework. However, it is useful to look at simpler implementations in order to understand the difference between different approaches. We will now look at a simple array list implementation to see how it works. We will look at the data storage and a couple of the operations.

First, let's define an interface to specify our List ADT– the characteristics and operations for this were stated earlier.

public interface ADTList {
    int length();
    void createList();
    String printList();
    void insert(String s);
    void remove(String s);
    boolean find(String s);
}

Note that this simple implementation will only store Strings, unlike the Collections Framework ArrayList class.

Now, let's look at part of an implementation of the ADTList interface. The data is stored in a field that is a String array, elements. The capacity of the array is stored as a constant, and the field length is the length of the list, i.e. the number of elements currently stored in the list:

public class SimpleArrayList implements ADTList {
    private String[] elements;
    private static final int CAPACITY = 10;
    private int length;

The length and createList method implementations are simple:

public int length() {
     return length;
 }

public void createList() {
    elements = new String[CAPACITY];
    length = 0;
}

This implementation of the insert operation adds a new element at the end of the list, if there is enough room, i.e. the new value goes into the first empty position in the array.

public void insert(String s)
{
    if (length < CAPACITY) {
        elements[length] = s;
        length++;
    }
}

This implementation operates in O(1) time, as the time taken does not depend on the length.

Another implementation of insert might add the new element at a specified position. This would require a loop to move the elements beyond that position along by one position to leave space for the new one, as shown in the code below. Note that the loop needs to count back from the end of the list to avoid overwriting elements.

public void insert(String s, int pos)
{
    if (length < CAPACITY) {
        for(int i=length-1; i>=pos; i--)
            elements[i+1] = elements[i];
        elements[pos] = s;
        length++;
    }
}

This implementation operates in O(n) time, as the number of times on average that the loop is executed, and hence the overall time taken, depends linearly on the length.

The remaining operations are left as a lab exercise.

The other common list implementation is the linked list. This uses a completely different way of storing the data. As a result, its operations have different efficiencies to array lists.

A linked list is particularly useful for situations that require inserting and removing at arbitrary locations. The array list is limited because, as you have seen its insert operation operates in linear (O(n)) time except for the case of inserting at the end as it requires a loop to shift elements. The same is true for the remove operation.

A linked list, on the other hand, can add and remove elements at a known location in O(1) time. This is because of the way that a linked list works.

In a single linked list, which is the simplest case, instead of an index each element is linked to the following element. A linked list is like a chain of elements.

A linked list has flexible space use – instead of creating an array to hold all the elements, it can dynamically allocate space for each element as needed.

Linked list implementation

Each element of the list is implemented as a node. A node is an object that contains:

the data item

an reference or pointer to the next node

The list data structure has a reference to the first node of the list is known as the head. The data structure doesn’t directly reference any other elements of the list – these can be reached by following the references to successive nodes. In an empty list, before any elements have been inserted, the head is a NULL reference.

Here, X is used to represent NULL or an empty link, i.e. one that doesn’t point to anything

The last node of a list is known as the tail. There is no specific reference to the tail node in a singly linked list, but you will see another variation on the linked list that does have such a reference.

Our simple linked list class should implement the same ADTList interface as our simple array list. However, this time we will use a variation on this interface that uses Java generics to allow any kind of object, not just Strings, to be stored. The type is referred to in the code by the placeholder type E, and the actual type is specified only in the application code that creates an instance of the list class that implements this interface. Note that the use of generics is not specific to linked lists - the SimpleArrayList class could have also been implemented with generics, but was done with Strings for simplicity in that first example.

public interface ADTListGeneric<E> {   
    int length();
    void createList();
    String printList();
    void insert(E e);
    void remove(E e);
    boolean find(E e);    
}

The linked list implementation consists of two classes. The first is a class Node, that represents a node of the list. Note that the type of the data item is the generic type E.

public class Node<E> {
    E data;
    Node<E> next; 
    
    Node(E e) {
        this.data = e;
        this.next = null;
    } 
}

The actual list data structure is represented by a class SingleLinkedList, which has a field to represent the head, which is a reference to a Node.

public class SingleLinkedList<E> implements ADTListGeneric<E> {
    private Node<E> head;
    private int length;

    public int length() {
        return length;
    }
    
    public void createList() {
        head = null;
        length = 0;
    }

An instance of the list can be created to hold String data as follows:

ADTListGeneric<String> strlist = new SingleLinkedList<String>();
sllist.createList();

You can create an instance to hold some other type of object, e.g. a class Person that you might have defined in your application:

ADTListGeneric<Person> personlist = new SingleLinkedList<Person>();
personlist.createList();

Inserting an item at the beginning of the list

Inserting first item to an empty list:
1. Allocate space in memory for node
2. Set its data item
3. Set Head to point to new node

Insert a second item – this involves “breaking” the link between the head and the first node, inserting the new node, and creating links to position the new node in the “chain”

This algorithm for insert at the start of a linked list is the same no matter how many elements are in the list as the rest of the list past the first node is not involved, so this operates in O(1) time.

The algorithm can be implemented as follows. Note that this works for both empty and non-empty list cases:

public void insert(E item) {
    Node<E> tmp = new Node<E>(item);
    tmp.next = head;
    head = tmp;
    length++;
}

Finding a specified item

To find an item we need to traverse the list from the head until we reach an element whose data item matches what we are looking for. Traversal is done by creating a temporary node reference that initially points to the first node in the list, i.e. the same node as the list head points to. The algorithm is as follows:

The implementation is as follows. validAccess is a private method that encapsulates the while condition.

public boolean find(E e) {
    Node<E> tmp = head;

    while (validAccess(tmp)) {
        if (e.equals(tmp.data)) {
            return true;
        }
        tmp = tmp.next;
    }
    // to get here we fell off the end of the list 
    // so can’t be in the list
    return false;
}

private boolean validAccess(Node<E> node){
    if(node == null)
        return false;
    if(node.next == null)
        return false;
    return true;
}

Traversing, on average, depends linearly on the list size, so this operates in O(n) time.

Note that this implementation of find simply tells us whether a data item is present. Alternatively, we could implement it so that it returns the data item itself.

Inserting an item at a specified other position in the list

This is very similar to inserting at the start of the list, but with the additional requirement to find that position in the list first:

The actual insertion of the node operates in O(1) time as before, but the time to find the position by traversing, on average, does depend linearly on the list size, so operates in O(n) time.

You can look at the implementations of insert and find which you have seen, and the implementation of remove which follows, to work out how to implement this version of insert.

Removing a specified item

The algorithms for removing an item is similar to inserting.

To remove the first item, we simply change the head to refer to the next (second) element. The rest of the list is not involved, so this operates in O(1) time.

public Node<E> removeFirst() {
    Node<E> tmp;
    if (validAccess(head)) {
        tmp = head;
        head = head.next;
        length--;
    } else { // list is empty
        tmp = null;
        length = 0;
    }
    return tmp;
}

To remove an item at a specified position, we need to traverse the list to find that position, and then change the next reference of the previous node to point to the next node instead of the current one.

The actual removal of the node operates in O(1) time as before, but the time to find the position by traversing, on average, does depend linearly on the list size, so operates in O(n) time.

The following code implements both cases:

public void remove(E e) {
    Node previous = null;
    Node current = head;

    while (validAccess(current)) {
        if (e.equals(current.data)) {
            // found the node that needs to be removed
            if (previous == null) {
                // must be removing the first node in the list
                head = current.next;
            } else {
                // removing a node that’s not first in list
                previous.next = current.next;
            }
            current = null;
        } else {
            previous = current;
            current = current.next;
        }
    }
}

Traversing

Simple traversal of the list is similar to the traversal you have already seen for finding and removing elements.

public String printList() {
    StringBuilder listString = new StringBuilder();
    int count = 0;
    Node<E> tmp = head;
    while (validAccess(tmp)) {
        listString.append(String.format("(%d) ==> %s ", count, 
             tmp.data.toString()));
        tmp = tmp.next;
        count++;
    }
    listString.append(String.format("(%d) ==> %s ", count,  
         tmp.data.toString()));
    return listString.toString();
}

Summary of key characteristics of the linked list

Storage:

Uses only as much memory as needed for the elements in the list. Requires no estimate of the maximum size of the list, so no wasted space as there is in the array implementation. However, each item requires more memory space than an item in an array as the reference to the next node also needs to be stored.

Circular Singly linked lists

The last node points to the first node of the list.

Different implementations are possible – can have a reference to the head and/or the tail.

If implemented without a tail reference, how do we know when we have finished traversing the list? Needs additional code: could use size() of the current list or check against Head node twice!

Circular lists are useful in applications to repeatedly go around the list, for example:

keeping track of who is next to play in a game

representing stops in the Glasgow subway (if you live in Glasgow, you’ll understand this right away, if not take a look at the map at 🔗 http://www.spt.co.uk/subway/maps-stations/)

Doubly linked lists

Limitations of a singly-linked list include:

Insertion at the front is O(1) but insertion at other positions is O(n)

Insertion is convenient only after a referenced node has been found

Removing a node requires obtaining a reference to the previous node

We can traverse the list only in the forward direction

We can overcome these limitations:

Add a reference in each node to the previous node, creating a double-linked list

Can modify Node class definition to include a prev reference as well as the existing next reference

Each node points to not only successor but the predecessor

There are two NULL (𝜙): at the first and last nodes in the list

Advantage: given a node, it is easy to visit its predecessor. Convenient to traverse lists backwards

public class Node<E> {
E data;
Node<E> prev;
    Node<E> next; 
    
    Node(E e) {
        this.data = e;
	  this.prev = null;
        this.next = null;
    } 
}

As with the single-linked class, the actual list data structure is represented by a class which has the following fields:

head (a reference to the first list Node)

tail (a reference to the last list Node)

length

public class DoubleLinkedList<E> implements ADTListGeneric<E> {
    private Node<E> head;
    private Node<E> tail;
    private int length;

Because we have a reference to the tail, and the last node has a reference to the preceding node, insertion at the end is very similar to insertion at the beginning, and can be done without traversing. Insertion at either end is therefore O(1). However, insertion elsewhere is still O(n) as traversal is needed to reach any other position.

Array implementation of linked lists

It is possible to implement a linked list in a different way, using either a two dimensional array or two separate arrays. In this implementation, one array (or dimension) stores the data items while the other stores the index of the next data item.

As a single linked list the data structure has to hold a head reference. Here, the head is simply the index of the first item in the data array.

What word would the contents of the data array, in list order, spell out for the following example?

As items are inserted and removed this data structure also needs to keep track of what positions in the array are free. This can be done with using the same arrays. The data structure then needs a First reference that contains the index of the first free position in the data array, and the other array is used to build up a list of free positions.

The efficiency of this is similar to the linked list based on nodes. This implementation might be useful if you want a fixed limit to the size of the list rather than a dynamic structure.

Implementation Hierarchy

A list data structure can be implemented in different ways:

Specialisation Hierarchy

List can be the basis for other more specialized data structures, some of which you will study later in the module. These are based on sequences of data, but have more specific access rules, e.g. last-in-first-out (LIFO).