 | Session 13 |  |
List (ArrayList, LinkedList)
List interface
We have discussed superficially the lists during session 4. In this session, we will provide some more details on them.
List interface is a subinterface on Collection interface. Lists are sometimes called sequences. Important features of lists:
- lists may contain duplicate elements;
- elements can be accessed by their position in the list (using a zero-based index);
- elements can be inserted or deleted from any position of the list;
- the capacity (length) of list is not fixed and can be increased at any time.
A full description of the lists is given in the API.
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
...
List<Integer> list1 = new ArrayList<>();
list1.add(42);
List<Integer> list2 = new ArrayList<>();
list2.addAll(Arrays.asList(1,2,3));
// a shorter version
List<Integer> list3 = Arrays.asList(1,2,3);
// arrays can be converted into lists
Integer[] myArray = {1, 2, 3};
List<Integer> list4 = Arrays.asList(myArray);
// lists can also be converted into arrays
Integer[] myArray2 = list4.toArray(new Integer[0]);
// make a copy of a list
List<Integer> list5 = new ArrayList<>(list4);
Lists and the lamba notation
Since Java 8, forEach and the lamba expression can be applied to list elements:
// print the elements of the list list1.forEach(elem -> System.out.println(elem));
The lamba expression can also be used in sorting the elements. The following piece of code sorts the strings taking into account the string length:
List<String> list6 = Arrays.asList("aa","ccc","b");
// compareTo lambda which takes in two parameters and returns an integer
Collections.sort(list6, (s1, s2) -> s1.length() - s2.length());
If we remove the lamba expression from the last line of the code Collections.sort(list6); , the strings will be sorted in the alphabetical order.
Implementing classes of the List interface
ArrayList class and LinkedList class are two non-abstract implementations of List interface.
ArrayList stores elements in an array. The array is created dynamically: if the capacity of an array is exceeded, a new larger array is created and all the elements from the current array are copied to the new array. Therefore, an ArrayList is a resizable-array implementation of List interface.
LinkedList stores elements in a linked list. The class provides methods for retrieving, inserting, and removing elements from both ends of the list. Note: retrieving an element by its index works slower than in the case of ArrayList.
Which of the two classes to use - depends on the specific needs. If it is needed to support random access through an index without inserting or removing elements at the beginning of the list, ArrayList offers the most efficient methods. If, however, the application requires the insertion or deletion of elements at the beginning of the list, choose LinkedList.
// insert an element into the middle of the list // NB! works with ArrayList as well List<Integer> list2 = new LinkedList<Integer>(); list2.addAll(Arrays.asList(1,2,3)); list2.add(2, 54); // '54' is the third element (with index 2)
It is recommended to create a list of the proper class (according to the list features), but assign it to a variable of the List data type (not ArrayList or LinkedList). The methods which manipulate with the variable know that the variable holds a reference to a list (but the method does not know the type of the list).
| Session 13 | |