List is an interface for an ordered collection of elements in Java.
You can easily add, remove and get elements by index.
2 main things that you should keep in mind using Lists in Java:
- Lists guarantee an order of elements. That means if you will add 1, 2, 3 integers to the list, you can access it by 0, 1 and 2 indexes.
- Lists allow duplicates
There are 2 the most popular implementations of Java List: ArrayList and LinkedList.
Let’s take a look deeper at this 2 classes.
I’ll explain how to initialize list in Java, syntax, difference between ArrayList and LinkedList and of course I’ll mention few popular interview questions.
Java List Syntax
The list syntax should not be a problem for any person.
For example, we want to make an array list of string:
List<String> strings = new ArrayList<>();or initialize a linked list of integers:
List<Integer> numbers = new LinkedList<>();Note that currently (until Java 9) you cannot use primitive types as a generic type, you have to use corresponding primitive class wrappers like Integer, Long etc.
But JEP 218 promises to fix this situation and maybe in the future we’ll get this feature.
You can add elements calling add() method:
strings.add("Explain");
strings.add("Java");You can remove elements by index as well:
strings.remove(1);If an index is not valid IndexOutOfBoundException will be thrown.
You can access elements by index:
String explain = strings.get(0);Or you can iterate through the list using a for-each loop.
for (String s : strings) {
System.out.println(s);
}Let’s take a deeper look at list implementations.
ArrayList
Java ArrayList is built using a simple array.
Inside of array list, you can find a field:
transient Object[] elementData;Default capacity is 10 elements.
You can specify initial capacity via constructor as well.
Internal array size is always greater than list size because we need a gap to add elements fast.
If required capacity less than current element capacity – array will grow on 50%.
For example, current capacity is 10, we want to add one more element.
Required capacity is 11, that is more than current, so elementData array will grow to 15 elements.
Previous 10 elements will be copied using Arrays.copy() and new element will be added to the 11th position.
But when you remove an element capacity is not changed, it’s important to know.
One more thing that you should keep in mind that ArrayList is not a thread-safe collection.
If you need concurrency take a look at CopyOnWriteArrayList and Collections.synchronizedList().
Time Complexity
First of all, read what is algorithm time complexity on the Wiki if you don’t know what is it.
Now depends on your use case you should understand what data structure is better.
You should think about the most frequent operations, e.g. you need to add elements fast or you need to read elements by index.
We’re going to estimate the following use-cases:
- add/remove an element to/from the beginning
- add/remove an element to/from the end
- add/remove an element to/from the middle
- read element by index
- contains an element
- get list size
Let’s take a look at time complexity table:
| Use-case | Time Complexity | Description |
| add/remove an element to/from the beginning | O(n) | You need to copy each element to the i + 1 position and then you can write a new element to 0 index |
| add/remove an element to/from the end | O(1) | At the end of an array you have a gap, so it costs nothing to write a new element to the end |
| add/remove an element to/from the middle | O(n/2) | You need to copy 2nd half of element to i + 1 position |
| read element by index | O(1) | Get element by index in the array takes constant time |
| contains an element | O(n) | You need to iterate through the whole array and check if array[i] element equals to target object, worst case is an object is a last one in the array |
| get list size | O(1) | ArrayList stores a private field size and increments it every time when its growing, so it’s constant time to read this variable |
If we analyze this table we can say following:
- It’s really fast to add element to the end, read element by index and check array list size
- It could take time to check if object exists or not
- It could take time to add an element to the beginning or to the middle. In general
Arrays.copy()works really fast but if this is a frequent operation you should think twice before choosing anArrayList
LinkedList
LinkedList is one more List implementation that consists of Nodes that contains an object value and references to the next and previous nodes.
It’s double-linked – that means LinkedList contains references to the first and last nodes.
Node looks like this:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}What happens when you add a new node:
- the linked list takes the last node
- create a new node that contains the current element and last node as a prev
- sets new node as the last one
- old last node now points to the new node
Looks at the source code example:
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}One more important thing that LinkedList implements Deque interface.
You should keep it in mind because interviews can ask about it.
LinkedList is not synchronized as well.
If you need thread-safe behavior you need to wrap it like this:
List list = Collections.synchronizedList(new LinkedList(...));Time Complexity
| Use-case | Time Complexity | Description |
| add/remove an element to/from the beginning | O(1) | You need to create a new node and switch references to make a new element as a first and old first element as a 2nd one |
| add/remove an element to/from the end | O(1) | You need to create a new node and switch references to make a new element as a last and old last element as a previous one |
| add/remove an element to/from the middle | O(n/2) | Insert an element is not a problem, the problem is that you need to iterate half of the list until you will find a place to insert a new element |
| read element by index | O(n/2) | You need to iterate through the list to find a required index, implementation is double-linked that means you need to iterate through the half of list in the worst case |
| contains an element | O(n) | You need to iterate through the whole list and check if current element equals to target object, worst case is required object is the last one |
| get list size | O(1) | LinkedList stores a private field size and increments it every time when new node inserted, so it’s constant time to read this variable |
As you see it’s really fast to add elements to the beginning and to the end of a linked list, but it takes time to read element by index.
Difference Between LinkedList and ArrayList
Let’s compare ArrayList vs LinkedList.
So when to use an array list and when linked list:
- If you need to get element by index – take an array list
- if you need to add elements to the end or to the middle – take an array list
- if you care about memory usage – take an array list, because linked list needs to wrap each element in the Node object, that’s why it consumes more memory
- if you need to add elements to the beginning – take a linked list
- If you need a queue or deque behavior – linked list is a good option
Performance Test: LinkedList vs ArrayList
I wrote small performance test to show you the difference:
List<Long> time = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
long before = System.currentTimeMillis();
List<String> s = new LinkedList<>();
for (int j = 0; j < 1000000; j++) {
s.add("1");
}
time.add(System.currentTimeMillis() - before);
}
System.out.println(time.stream().mapToDouble(t -> t).average());I’m adding 1M strings to the end of the list, calculate a time and put it to another list to store results, at the end I’m calculating an average time.
Adding the last element is more or less the same:
- LinkedList 6.75 ms
- ArrayList 7.3 ms
Adding the first element – LinkedList is a winner:
- LinkedList 7 ms
- ArrayList 65243 ms
Adding an element to the middle – ArrayList is a winner:
- LinkedList 47373 ms
- ArrayList 2324 ms
I think it’s no sense to compare getting elements by index – it’s clear even without tests.
So check results and think what list implementation is better for your use-case.
How To Remove Elements From List in Loop (Important!)
It’s the most common mistake and popular interview question.
First Wrong Example
We’re iterating through the list using for loop and removing an element by index:
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("b");
list.add("a");
list.add("b");
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("b")) {
list.remove(i);
}
}What do you think is an output?
[a, b, a]What? Why “b” is still present?!
Second Wrong Example
Let’s refactor to for-each loop:
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("b");
list.add("a");
list.add("b");
for (String s : list) {
list.remove(s);
}Something changed? Yes…
Exception in thread "main" java.util.ConcurrentModificationExceptionIt even happens if we leave just one target element.
Correct Ways
There are 3 ways to do it without any problems.
Iterator:
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
if (iterator.next().equals("b")) {
iterator.remove();
}
}Java 8 removeIf() method:
list.removeIf(e -> e.equals("b"));Java 8 streams:
list.stream().filter(e -> !e.equals("b")).collect(Collectors.toList())Interview Questions
I just want to mention few of them, answers you can find in the text above:
- How ArrayList/LinkedList works inside?
- What is time complexity for adding/removing elements to the beginning/middle/end?
- What is a difference between LinkedList and ArrayList?
- How to remove an element from List, what happens if you’re removing elements in the loop?
- Is ArrayList/LinkedList thread-safe? How to make it thread-safe?
- When it’s better to use ArrayList and when to use LinkedList?
- What interfaces LinkedList implements (remember about Deque)?
- How to make an immutable list? (I mentioned about it in the article about immutable objects)
- If I remove an element from ArrayList will internal array be reduced?
And you should definitely open and save to bookmarks my ultimate collection of Java interview questions, search for answers on Java turorials page.
Conclusion
I gave you general information about 2 list implementations: ArrayList and LinkedList, so now you have enough knowledge to choose correct data structure.
I didn’t mention about Vector, it’s part of Java library and implements a List interface as well, but it’s deprecated at this moment and I think it’s no sense to talk about it.
Do you have any question? Want to add something? Please, comment.