Java Collection Interview Questions

Comparing ArrayList and LinkedList in Java

Know all the differences and comparisons and rock your interview.

Hey, I’m back with another article on the Collections framework. While ago when I was preparing for the interviews, I find this very common question in all of the interviews. If you search on the web, you’ll find many answers, but most of them are just writing basic differences that anyone can answer.

When I was giving interviews my focus was not just to tell the technical difference but craft my answer on a use case driven. I presented the answers with their use cases and along with that explained the differences.

Through this article, you will find a better approach to answering your technical interview questions, which will definitely impress your interviewer.

First thing first, the Basics of Array List and Linked List:

ArrayList vs LinkedList:

• ArrayList is a resizable-array implementation of the List interface. Whereas LinkedList is a Doubly-linked list implementation of the List and Deque interfaces.
• In ArrayList accessing an element takes constant time O(1)and adding an element takes O(n) time in the worst case(i.e. adding an item at the first position). Whereas in LinkedList adding an element takes O(n) time(at the end of the list) and accessing also takes O(n) time.
• But LinkedList uses more memory than ArrayList because of extra overhead for the next and previous pointers for each node in the linked list.

Now let’s dive deeper into the time complexities for different operations of these two collection classes.

As with standard linked list and array list operations, the various operations will have different algorithmic run times.

Let’s discuss these time complexities:

ArrayList<E>:

• get(int index) is O(1). Main benefit of ArrayList<E>.
• add(E element) is O(1) amortized, but O(n) worst-case since the array. must be resized and copied.
• add(int index, E element) is O(n).
• remove(int index) is O(n).
• Iterator.remove() is O(n).
• ListIterator.add(E element) is O(n).

LinkedList<E>:

• get(int index) is O(n), but O(1) when index = 0 or index = list.size() - 1 (in this case, we can also use getFirst() and getLast()). One of the main benefits of LinkedList<E> .
• add(int index, E element) is O(n), but O(1) when index = 0 or index = list.size() - 1 (in this case, we can also use addFirst() and addLast()). One of the main benefits of LinkedList<E> .
• remove(int index) is O(n), but O(1) when index = 0 or index = list.size() - 1 (in this case, we can also use removeFirst() and removeLast()). One of the main benefits of LinkedList<E> .
• Iterator.remove() is O(1). One of the main benefits of LinkedList<E> .
• ListIterator.add(E element) is O(1). One of the main benefits of LinkedList<E> .

Which One Takes More Memory?

If we have a large list, keep in mind that memory usage will be different for these data structures. Each element of a LinkedList has more overhead since the next and previous pointers are also stored. ArrayLists don't have this overhead.

However, ArrayLists take up as much memory as it is allocated for the capacity, regardless of whether elements have actually been added or not into the list. Basically, whatever initial capacity we specify while constructing the ArrayListthat much of memory is assigned to the list even though there aren’t that many objects stored initially.

Note: The default initial capacity of an ArrayList is small (10), But since the underlying implementation is an array, the array must be re-sized if we want to add a lot of elements. To avoid the high cost of re-sizing, when we know that we're going to add a lot of elements, we should construct the ArrayList with a higher initial capacity.

Now let’s understand when we should use these two data structures.

Let me put two scenarios for you:

1. Let’s say you have to create a grocery list for all the items for your daily needs for the next month and
2. Another list you need to create for your favorite songs.

Now can you guess what kind of data structure you should use for the first and second use cases?

Where To Use ArrayList?

In our first use case, we can definitely use an array list as our list can grow if we need more items and we can directly access any item on this list. Basically, ArrayList<E> allows fast random read access, so you can grab any element in constant time.

Also, if we want to add more elements than the capacity of the underlying array, a new array is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

But adding or removing from anywhere requires shifting all the latter elements over to make an opening or fill the gap.

Where To Use LinkedList?

Now for our second use case, we can use LinkedList as LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of the elements.

Now let’s say I’m playing the ‘X’ song of this playlist and want to move to the next song or go back to the previous song then, we can walk the list either forward or backward using the next and previous pointers of each Node.

But finding a position in the list takes time proportional to the size of the list.

How To Choose One?

• So depending on the operations we intend to do, we should choose the implementations accordingly.
• Searching in a LinkedList means following the links in O(n) time for the worst case, whereas in an ArrayList the desired position can be computed mathematically using the base address and offset and can be accessed inO(1) .

Note: The benefit of using a LinkedList can also arise when we want to add or remove from the head of the list since those operations are O(1), while they are O(n) for ArrayList.

Note that ArrayDeque maybe a good alternative to LinkedList for adding and removing from the head, but it is not a List.

That’s all for this article. Hope you enjoyed it.

You Can Follow Vikram Gupta For Similar Content.

1. Comparing ArrayList and LinkedList in Java

2. Internal Working of HashMap in Java

3. Comparing HashMap and ConcurrentHashMap in Java

4. Complete Guide on LinkedHashMap in Java

5. Internal Working Of TreeMap in Java Collection Framework

6. Internal Working of HashSet in Java