List

List #

The abstract data type list simulates a tuple.

Accordingly, a list may contain duplicates.

A list may expose the following methods:

  • “isEmpty” is self-explanatory,
  • “append” adds an element at the end of the list,
  • “prepend” adds an element at the beginning of the list,
  • “tail” returns the sub-list identical to the current one, but without its first element,
  • etc.

Note. The size of a list is often unbounded (as opposed to the size of an array for instance). This can be implemented in different ways, for instance with a dynamic array or a linked list.

in Java #

Java has an interface List with 8 native implementations (i.e. 8 different classes that implement this interface). The most commonly used are ArrayList and LinkedList.

The interface List extends the interface Collection.

Syntax #

Here are code snippets for a few operations specified in the interface List.

Create a List and populate it:

City milan = new City("Milan", 20100);
City florence = new City("Florence", 50100);

// create an empty list of cities;
// alternatively, we could use another implementation, like `LinkedList`
List<City> myList = new ArrayList();

// append Milan to the list
myList.add(milan);
// append Florence to the list
myList.add(florence);
// append Milan again to the list
myList.add(milan);

Convention. In this example, the class ArrayList is only used to create the list (by calling its constructor). The rest of the code refers to (methods of) the interface List.

This is the standard way to use an interface in Java.

As a benefit, we can use a different implementation of List by modifying a single line of code:

List<City> myList = new ArrayList();

becomes

List<City> myList = new LinkedList();

Alternative syntaxes to create a list:

// create a list identical to the previous one, but which cannot be modified
List<City> myOtherList = List.of(milan, florence, milan);

City[] myArray = new City[]{milan, florence};
// create a fixed-lenght "wrapper" list around the array;
// no data is duplicated
List<City> yetAnotherList = Arrays.asList(myArray);

Get the size of a list:

// outputs 3
System.out.println(myList.size());

Retrieve the element at index i (the first index being 0, like in an array):

// contains (a reference to) Florence
City secondCity = myList.get(1);

Insert an element at index i (shifts the position of all subsequent elements by 1):

City trento = new City("Trento", 38100);
myList.add(1, trento);

// now contains (a reference to) Trento
secondCity = myList.get(1);
// contains (a reference to) Florence
City thirdCity = myList.get(2);

Remove the element at index i (shifts the position of all subsequent elements by -1), and return it:

myList.remove(1);
// outputs 3
System.out.println(myList.size());
// now contains (a reference to) Florence
secondCity = myList.get(1);

Remove the first occurrence of an object in the list (shifts the position of all subsequent elements by -1):

myList.remove(milan);
// contains (a reference to) Florence
City firstCity = myList.get(0);

For more operations, consult the Javadoc of the interface List.