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

// Creates an empty list of cities
List<City> myList = new ArrayList();

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

// Creates 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};
// Creates a fixed-lenght "wrapper" list around the array.
// No data is duplicated.
List<City> yetAnotherList = Arrays.asList(myArray);
  • Retrieve 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 (shift 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 a index i (shift the position of all subsequent elements by -1), and return it
myList.remove(1);
// Outputs 3
Sysetm.out.println(myList.size());
// Now contains (a reference to) Florence
secondCity = myList.get(1);
  • Remove the first occurrence of an object in the list (shift 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.