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 a very popular question during practical exams in 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 in 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

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 another popular core Java interview question, Instead, here we will talk about

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.

Btw, If you are not familiar with basic data structures like an array, linked list, binary tree, string etc then I suggest you to 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.

##

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 the linked list is implemented and work in any programming language e.g. Java, you can easily figure out these differences.

###

A linked list is more flexible than 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 linked list unless memory is not a constraint.

###

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

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 a linked list can be scattered all around heap memory, it's possible to store more elements in the linked list than 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.

###

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, 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 data structure e.g. 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.

###

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

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.

###

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, a linked list has just one dimension but it also comes in two flavors, singly linked list and a 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

That's all about the

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Top 30 Array Interview Questions for Programmers

Top 30 linked list interview questions for Programmers

Data Structures in Java 9 by Heinz Kabutz

10 Books to Prepare for Coding Interviews

10 Books to learn Computer Science Algorithms.

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.

**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 perspective, I'll give you examples and explanation 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 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.

Btw, If you are not familiar with basic data structures like an array, linked list, binary tree, string etc then I suggest you to 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.

##
__Array vs Linked List in Java__

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 the linked list is 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 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 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 a linked list can be scattered all around heap memory, it's possible to store more elements in the linked list than 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, linked list node also stores the address of 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 data structure e.g. 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 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.

###
**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, a linked list has just one dimension but it also comes in two flavors, singly linked list and a 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: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 e.g. C and C++. The key takeaway is to remember these difference so that programmer can choose when to use an array over the linked list and vice-versa.**Further Reading**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Top 30 Array Interview Questions for Programmers

Top 30 linked list interview questions for Programmers

Data Structures in Java 9 by Heinz Kabutz

10 Books to Prepare for Coding Interviews

10 Books to learn Computer Science Algorithms.

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.

**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.
## No comments:

## Post a Comment