5 Differences between an array and linked list in Java

The difference between an array and a linked list is one of the frequently asked data structure and algorithm interview questions and you might have seen it before on your telephonic or face-to-face interview. It is also a very popular question during practical exams in Computer Science degree courses like B.E. and B.Tech. It's very simple and easy to answer but you just can't afford to miss this question in an interview. Both array and linked list are two of the most popular and fundamental data structures in Computer Science and Programming, and Java supports both of them.

One of the traits of a good programmer is extensive knowledge of data structure and algorithm and that's why it's very important for you to learn the difference between array and linked list data structure and understand when to use an array over a linked list and vice-versa.

Though this discussion is valid from C/C++ and other programming language perspectives, I'll give you examples and explanations in Java.

Remember, here we will not talk about ArrayList vs LinkedList in Java which is another popular core Java interview question, Instead, here we will talk about array and linked list data structure from a coding/programming interview perspective.

Btw, both are very similar because of java.util.ArrayList is based upon array and java.util.LinkedList is based upon the linked-list data structure. Once you understand these data structures you can easily answer the previous question and explain when you will use ArrayList over LinkedList and vice-versa.

Btw, If you are not familiar with basic data structures like an array, linked list, binary tree, string, etc then I suggest you first join a comprehensive data structure course like Data Structures and Algorithms: Deep Dive Using Java, which will explain all these data structures in good detail.

Difference between Array vs Linked List in Java

Here is my list of some key differences between an array and a linked list in Java. Don't try to remember these differences, instead, try to understand that by learning how array and linked list are actually implemented in any programming langue like Java or C++.

Once you understand how array and the linked list are implemented and work in any programming language e.g. Java, you can easily figure out these differences.

1. Flexibility

A linked list is more flexible than an array data structure because you can change the size of the linked list once created which is not possible with an array.

A linked list can also grow unlimited but the array cannot grow beyond its size. This is one of the most fundamental differences between an array and a linked list is that the length of the array cannot be changed once created but you can add unlimited elements into a linked list unless memory is not a constraint.

2. Memory utilization

One more significant difference between the linked list and array data structure comes from a memory perspective. the array requires a contiguous chunk of memory, which means if you want to create a large array and even if memory is available you may fail because there is no single chunk of memory that is big enough for your array.

This is a huge restriction and that's why any large array should be created at the very start of an application when you have a big chunk of memory available.

A linked list is more flexible in terms of memory as well. Since the linked list doesn't need a contiguous chunk of memory and nodes of a linked list can be scattered all around heap memory, it's possible to store more elements in the linked list than an array if you have fragmented heap space.

In short, a linked list is a better data structure for memory utilization than an array. You can also see Algorithms and Data Structures - Part 1 and 2 to learn more about the linked list data structure.

3. Memory required

linked list data structure requires slightly more memory than an array because apart from data i.e. the element you store, the linked list node also stores the address of the next node.

In Java, the linked list also has object metadata overhead because each node of the linked list is an object. In short, an array requires less memory than a linked list for storing the same number of elements. See a good book in a data structure like the Algorithms 4th Edition by Robert Sedgewick for more details.

The examples in this book are given in Java programming language, which makes it an ideal book for any Java developer.

4. Performance

Another key difference between an array and linked list data structure comes from a performance perspective, which is also the main factor to decide when to use the array over the linked list in Java.

An array gives O(1) performance for the searching element when you know the index but the linked list search is in order of O(n). So if you need fast retrieval and you know the index then you should use an array.

When it comes to the performance of adding and deleting elements then a linked list stores better than an array because adding into head or tail is O(1) operation if you have the necessary pointer but adding at a random position is O(n).

With an array, adding or removing is difficult because it requires rearranging all other elements as well.

5. Dimension and types

One of the structural differences between the linked list and array comes from their variety. The array can be multi-dimensional in Java which makes it an ideal data structure for representing matrices, 2D plain, 2D game board, terrain, etc.

On the other hand, a linked list has just one dimension but it also comes in two flavors, a singly linked list, and a doubly linked list.

The Singly linked list holds the address of the next node only and thus allows you to move only in one direction i.e. forward but the doubly linked list contains two points, one for storing the address of the next node and the other for storing the address of the previous node. Which means it allows you to traverse in both forward and backward directions.

Here is a nice summary of some key differences between array and singly linked list data structure in Java:

That's all about the difference between array and linked list data structure in Java. As I told you, most of the differences are at the data structure level so they are valid for other programming languages as well like C and C++. The key takeaway is to remember these differences so that programmer can choose when to use an array over the linked list and vice-versa.

Further Reading
Top 30 Array Interview Questions for Programmers
Top 30 linked list interview questions for Programmers 
10 Books to Prepare for Coding Interviews
7 Best Courses to learn Data Structure and Algorithms
10 Books to learn Computer Science Algorithms.
5 Website to Practice Coding Questions for Interviews

Thanks for reading this article so far. If you like this interview question and my explanation then please share it with your friends and colleagues. If you have any questions or doubt then please write a comment and I'll try to find an answer for you.

P. S. - If you are looking for some free courses to start with then you should also check out my list of FREE Data Structure and Algorithm courses for Java Developers.