An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
Some features in List are:
- List typically allows duplicate elements.
- List typically allows multiple null elements if they allow null elements at all.
- List (like Java Array) is zero-based.
- List provides the positional (indexed) access to the elements. The execution is in time proportional to the index value for some implementations.
Note, Vector and Stack classes basically fall in legacy classes.
List Interface extends Collection, hence it supports all the operations of Collection Interface, along with the following additional operations.
- void add(int index, E element): Inserts the specified element at the specified position in this list (optional operation).
List<Integer> l = new ArrayList<Integer>();
l.add(0, 1); // adds 1 at 0 index
l.add(1, 2); // adds 2 at 1 index - boolean addAll(int index, Collection c): Inserts all of the elements in the specified collection into this list at the specified position (optional operation).
List<Integer> l1 = new ArrayList<Integer>();
l1.add(0, 1);
l1.add(1, 2);
List<Integer> l2 = new ArrayList<Integer>();
l2.add(1);
l2.add(2);
l2.add(3);
l1.addAll(1, l2);-
E get(int index): Returns the element at the specified position in this list.
-
E remove(int index): Removes the element at the specified position in this list (optional operation). Note: it shifts any subsequent elements to the left (subtracts one from their indices).
-
E set(int index, E element): Replaces the element at the specified position in this list with the specified element (optional operation).
- int indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. Note: this is a linear (O(n)) operation.
List<String> l = new ArrayList<>();
l.add("Leet");
l.add("Code");
lastIndexOf("Code"); // returns 1
lastIndexOf("dumb"); // returns -1- int lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
- ListIterator listIterator() and ListIterator listIterator(int index): Returns a list iterator over the elements in this list (in proper sequence). The ListIterator is an iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.
- List subList(int fromIndex, int toIndex): Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < 10; i++)
l.add(i * 10);
List<Integer> sub = new ArrayList<Integer>();
sub = l.subList(2, 6); // return [20, 30, 40, 50]ArrayList class implements resizable-array under the List interface. The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).
Note that this implementation is not synchronized.
- ArrayList instance has a capacity. The capacity 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. The capacity can grow or shrink automatically.
- ArrayList can not be used for primitive types (it converts the primitive int data type into an Integer object).
- Since ArrayList can’t be created for primitive data types, members of ArrayList are always references to objects at different memory locations. Therefore in ArrayList, the actual objects are never stored at contiguous locations. References of the actual objects are stored at contiguous locations. In an array, it depends on whether the array is of primitive type or object type. In the case of primitive types, actual values are contiguous locations, but in the case of objects, allocation is similar to ArrayList.
- ArrayList in Java can be seen as similar to vector in C++.
- ArrayList(): builds an empty ArrayList.
- ArrayList(Collection c): builds an ArrayList initialized with the elements from collection c.
- ArrayList(int capacity): builds an ArrayList with initial capacity being specified.
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>(10);
for (int i = 0; i < 10; i++)
l2. add(i);
List<Integer> l3 = new ArrayList<>(l2);-
void ensureCapacity(int minCapacity): Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
-
void forEach(Consumer<? super E> action): Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
List<Integer> l = new ArrayList<>();
l.add(10);
l.add(20);
l.add(30);
l.forEach((n) -> System.out.println(n)); -
E remove(int index): Removes the element at the specified position in this list.
-
boolean removeIf(Predicate<? super E> filter): Removes all of the elements of this collection that satisfy the given predicate.
List<Integer> l = new ArrayList<>();
l.add(10);
l.add(20);
l.add(30);
l.removeIf(n -> (n % 3 == 0)); // {10, 20}-
Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence (from first to last element).
-
T[] toArray(T[] a): Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
Note: casting to array is hard to use (not well-implemented). I'd recommend to write a function to do so.
- void trimToSize(): Trims the capacity of this ArrayList instance to be the list's current size.
List is usually given as an input of the question in interviews.
- Is the list sorted or partially sorted?
If so, it means you can use binary search, which is
O(lgn). - Can you manipulate the list in place? The reference of a list is a pointer to the object. So any change will be preserved.
- Can you sort the list? Sometimes sorting the list first may significantly simplify the problem. Make sure that the order of list elements does not need to be preserved before attempting a sort.
- Are there duplicates in the list? Would it affect the answer? Make sure the result is unique or not.