5 Difference between an array and linked list in Java

The difference between an array and linked list is one of the frequently asked data structure and algorithm interview question and you might have seen it before on your telephonic or face-to-face interview. It is also very popular question during practical exams on Computer Science degree courses e.g. B.E. and B.Tech. It's very simple and easy to answer but you just can't afford to miss this question on an interview. Both array and linked list are two of the most popular and fundamental data structure 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 linked list and vice-versa. Though this discussion is valid from C/C++ and other programming language perspective, I'll give you examples and explanation in Java.

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

Remember, here we will not talk about ArrayList vs LinkedList in Java which is also a popular core Java interview question, Instead, here we will talk about array and linked list data structure from 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 structure you can easily answer the previous question and explain when you will use ArrayList over LinkedList and vice-versa. Though if you need some points, you can check here.




Array vs Linked List

Here is my list of some key differences between an array and 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 e.g. Java or C++. Once you understand how array and linked list is implemented and work in any programming language e.g. Java, you can easily figure out these differences.

1) Flexibility
Linked list is more flexible than array data structure because you can change the size of linked list once created which is not possible with an array. 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 linked list unless memory is not a constraint.


2) Memory utilization
One more significant difference between 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 which 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 linked list doesn't need a contiguous chunk of memory and nodes of linked list can be scattered all around heap memory, it's possible to store more elements in linked list than array if you have fragmented heap space. In short, linked list is a better data structure for memory utilization than an array.



3) Memory required
linked list data structure requires slightly more memory than an array because apart from data i.e. the element you store, linked list node also stores the address of next node. In Java, linked list also has object metadata overhead because each Node of linked list is an object. In short, an array requires less memory than linked list for storing the same number of elements. See a good book in data structure e.g. Algorithms 4th Edition by Robert Sedgewick for more details. The examples in this book are given in Java programming lanague, 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 linked list in Java. array gives O(1) performance for the retrieving element when you know the index but 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 performance of adding and deleting element than 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 of all other elements as well.

Difference between Array and Linked List Data Structure in Java



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

On the other hand, linked list has just one dimension but it also comes in two flavors, singly linked list and doubly linked list. The Singly linked list holds the address of 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 next node and other for storing the address of the previous node. Which means it allows you to traverse in both forward and backward direction.

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

Difference between Array vs 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 data structure level so they are valid for other programming languages as well e.g. C and C++. The key takeaway is to remember these difference so that programmer can choose when to use an array over linked list and vice-versa.

Further Reading
Cracking the Coding Interview - 189 Problems with Solutions
10 Books to Prepare for Coding Interviews
10 Books to learn Computer Science Algorithms.
Top 30 Array Interview Questions for Programmers
Top 20 String Algorithm Questions from Interviews
5 Website to Practice Coding Questions for Interviews
Data Structure and Algorithm Made Easy in Java

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


No comments:

Post a Comment