Lists
Tags: java, programming, learning, beginners
Published: 2024-07-09 18:39:26

The **List** interface extends the **Collection** interface and defines a collection for storing elements in a sequential order. To create a list, use one of its two concrete classes: **ArrayList** or **LinkedList**.

We used **ArrayList** to test the methods in the **Collection** interface in the preceding sections. Now we will examine **ArrayList** in more depth. We will also introduce another useful list, **LinkedList**, in this section.

##  The Common Methods in the List Interface

**ArrayList** and **LinkedList** are defined under the **List** interface. The **List** interface extends **Collection** to define an ordered collection with duplicates allowed. The **List** interface adds position-oriented operations, as well as a new list iterator that enables the user to traverse the list bidirectionally. The methods introduced in the **List** interface are shown in Figure below.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jh8fo3id30m2f4v64qw9.png)

The **add(index, element)** method is used to insert an element at a specified index, and the **addAll(index, collection)** method to insert a collection of elements at a specified index. The **remove(index)** method is used to remove an element at the specified index from the list. A new element can be set at the specified index using the **set(index, element)** method.

The **indexOf(element)** method is used to obtain the index of the specified element’s first occurrence in the list, and the **lastIndexOf(element)** method to obtain the index of its last occurrence. A sublist can be obtained by using the **subList(fromIndex, toIndex)** method.

The **listIterator()** or **listIterator(startIndex)** method returns an instance of **ListIterator**. The **ListIterator** interface extends the **Iterator** interface to add bidirectional traversal of the list. The methods in **ListIterator** are listed in Figure below.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mt18qqffqxemsyp9paey.png)

The **add(element)** method inserts the specified element into the list. The element is inserted immediately before the next element that would be returned by the **next()** method defined in the **Iterator** interface, if any, and after the element that would be returned by the **previous()** method, if any. If the list doesn’t contain any elements, the new element becomes the sole element in the list. The **set(element)** method can be used to replace the last element returned by the **next** method or the **previous** method with the specified element.

The **hasNext()** method defined in the **Iterator** interface is used to check whether the iterator has more elements when traversed in the forward direction, and the **hasPrevious()** method to check whether the iterator has more elements when traversed in the backward direction.

The **next()** method defined in the **Iterator** interface returns the next element in the iterator, and the **previous()** method returns the previous element in the iterator. The **nextIndex()** method returns the index of the next element in the iterator, and the **previousIndex()** returns the index of the previous element in the iterator.

The **AbstractList** class provides a partial implementation for the **List** interface. The **AbstractSequentialList** class extends **AbstractList** to provide support for linked lists.

## The ArrayList and LinkedList Classes

The **ArrayList** class and the **LinkedList** class are two concrete implementations of the **List** interface. **ArrayList** stores elements in an array. The array is dynamically created. If the capacity of the array is exceeded, a larger new array is created and all the elements from the current array are copied to the new array. **LinkedList** stores elements in a _linked list_. Which of the two classes you use depends on your specific needs. If you need to support random access through an index without inserting or removing elements at the beginning of the list, **ArrayList** offers the most efficient collection. If, however, your application requires the insertion or deletion of elements at the beginning of the list, you should choose **LinkedList**. A list can grow or shrink dynamically. Once it is created, an array is fixed. If your application does not require the insertion or deletion of elements, an array is the most efficient data structure.

**ArrayList** is a resizable-array implementation of the **List** interface. It also provides methods for manipulating the size of the array used internally to store the list, as shown in Figure below. Each ArrayList instance has a capacity, which is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an **ArrayList**, its capacity grows automatically. An **ArrayList** does not automatically shrink. You can use the **trimToSize()** method to reduce the array capacity to the size of the list. An **ArrayList** can be constructed using its no-arg constructor, **ArrayList(Collection)**, or **ArrayList(initialCapacity)**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d2puj8pfzh911jdjfsf6.png)

**LinkedList** is a linked list implementation of the **List** interface. In addition to implementing the **List** interface, this class provides the methods for retrieving, inserting, and removing elements from both ends of the list, as shown in Figure below. A **LinkedList** can be constructed using its no-arg constructor or **LinkedList(Collection)**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g74h2rt5at7kuwi2dbbd.png)

The code below gives a program that creates an array list filled with numbers and inserts new elements into specified locations in the list. The example also creates a linked list from the array list and inserts and removes elements from the list. Finally, the example traverses the
list forward and backward.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t3h6nna6jxd5rh5cbqhw.png)

`A list of integers in the array list:
[10, 1, 2, 30, 3, 1, 4]
Display the linked list forward:
green 10 red 1 2 30 3 1
Display the linked list backward:
1 3 30 2 1 red 10 green`

A list can hold identical elements. Integer **1** is stored twice in the list (lines 8, 11). **ArrayList** and **LinkedList** operate similarly. The critical difference between them pertains to internal implementation, which affects their performance. **ArrayList** is efficient for retrieving elements and **LinkedList** is efficient for inserting and removing elements at the beginning of the list. Both have the same performance for inserting and removing elements in the middle or at the end of the list.

The **get(i)** method is available for a linked list, but it is a time-consuming operation. Do not use it to traverse all the elements in a list as shown in (a). Instead you should use an iterator as shown in (b). Note that a foreach loop uses an iterator implicitly.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f1guawufwum0iycfbnc2.png)

Java provides the static **asList** method for creating a list from a variable-length list of arguments. Thus you can use the following code to create a list of strings and a list of integers:

`List<String> list1 = Arrays.asList("red", "green", "blue");
List<Integer> list2 = Arrays.asList(10, 20, 30, 40, 50);`