Difference between Linked List and Array in Java? Example

Array and linked lists are two fundamental data structures in the programming world. Almost all programs use Array in some form or other, which makes it increasingly important to learn array and linked list. The difference between the linked list and array data structure is also a popular data structure question, frequently asked in the various programming job interviews. This makes it even more important to learn and understand the difference between an array and a linked list. Well, there are a lot of differences between these two starting from how they store data, to how you retrieve data from them.

The main difference comes from the fact that array elements are stored in a contiguous memory location, which makes it easy to retrieve them in quick time, while linked list elements are scattered throughout memory, where one element knows the address of other, it makes it hard to retrieve an element from a linked list in quick time.

Some of the differences which we saw in ArrayList vs LinkedList also applicable at the data structure level, because ArrayList is backed by an array, and LinkedList is internally backed by a double linked list in Java. 

In this tutorial, we will learn the differences between these two fundamental data structures in more detail. Once you know the difference, you can make a concise choice of which data structure suits your need better. Since both of them offers a distinctive advantage over others, in terms of speed and flexibility, You can make an informed choice based upon your need.

Array vs linked list in Java

Here is my list of differences between array and linked list. Though data structure concept are independent of any programming language and more or less applicable in all programming language including C and C++, I have explained differences in Java's context.

1. Random Access vs Sequential Access

The first and major difference between the linked list and array data structure is that the former doesn't support random access, while later supports random access. a linked list is sequential, in order to retrieve an element, you need to traverse till that, while if you know the index, you can retrieve an element from array very quickly because it doesn't involved traversal.

2. Contiguous vs Scattered Memory  

The second major difference between array and linked-list data structure is that, array needs contiguous memory allocation, which may result in java.lang.OutOfMemoryError: Java Heap Space if there is not enough contiguous ( a big chunk) of memory in Java Heap. On the other hand, linked list is distributed data structure, it's element are scattered over heap and doesn't need a contiguous memory allocation. This makes linked list ideal, if you have scattered memory.

3. Fixed length vs Flexible growth

The third major difference is fixed length, array is a fixed length data structure, you provide length or size of the array at the time of creation, later you can not modify that size. On the other hand, linked list is dynamic data structure, it can grow and doesn't required size to be specified at the time of creation, because each node keep tracks of other.

4. Ease of Insertion and Deletion

It's easy to insert and delete elements from linked list than array, especially inserting element at beginning of linked list, and deleting element from end of linked list is O(1) operation. On the other hand array is fixed length data structure, so memory is allocated during initialization, and doesn't really change due to addition and removal of elements.  Though you can set a particular index null, to cut the reference count of that object.

5. Usage in derived Data Structure

The array is ideal for implementing fast caches e.g. HashMap or Hashtable, which requires constant time retrieval e.g. Map data structure provides O(1) performance for get(Key key) operation, while linked list-based structure provides liner performance i.e. O(n) for retrieval operation, where n is the number of elements in a linked list.

6. Types 

Array can be one or multi-dimensional, while linked list can be singly, doubly, or circular linked list. Two-dimensional arrays are most common in multi-dimensional and are used to represent matrix in Java. 

You can use a two-dimensional array to represent a plain of x,y coordinates, frequently used in Game programming. Java programming language provides support for creating arrays at syntax level, it supports both single and multidimensional arrays. Java API also provides a class called java.util.LinkedList, which is an implementation of a doubly-linked list data structure.

And, if you prefer seeing difference in tabular format then here is a nice table which highlight the key difference between array and linked list data structure in Java:

That's all on my list of differences between array and linked list data structure. I strongly suggest getting a good hold of these data structures, especially the linked list, which is very popular among data structure interview questions. Questions like appending elements into linked list, deleting elements, reversing linked lists are quite common in various programming jobs. At very least, knowledge of fundamental data structure is essential to do well in programming jobs.

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• Difference between array and linked list data structure? (answer)
• Difference between a binary tree and binary search tree? (answer)
• How to reverse a linked list in Java using iteration and recursion? (solution)
• How to reverse an array in place in Java? (solution)
• How to find all permutations of a String in Java? (solution)
• How to reverse a String in place in Java? (solution)
• How to remove duplicate elements from an array without using Collections? (solution)
• Top 5 Books on Data Structure and Algorithms for Java Developers (books)
• Top 5 books on Programming/Coding Interviews (list)

Thanks for reading this article so far. If you find this article useful then please share with your friends and colleagues. If you have any questions or feedback then please drop a note.