Monday, July 15, 2013

Difference between linked list and array data structure in Java Programming

Array and linked list are two fundamental data structure in programming world. Almost all programs use Array in some form or other, which makes it increasingly important to learn array and linked list. Difference between linked list and array data structure is also a popular data structure question, frequently asked in various programming job interview. This makes it even more important to learn and understand difference between an array and a linked list. Well there are lot of difference between these two starting from how they store data, to how you retrieve data from them. Main difference comes from the fact that array elements are stored in contiguous memory location, which makes it easy to retrieve them in quick time, while linked list elements are scattered through out memory, where one element knows address of other, it makes it hard to retrieve element from linked list in quick time. Some of the differences which we saw in ArrayList vs LinkedList also applicable at data structure level, because ArrayList is backed by array and LinkedList is internally backed by double linked list in Java. 

In this tutorial, we will learn differences between these two fundamental data structure in more details. Once you know the difference, you can make a concise choice of which data structure suits your need better. Since both of them offers 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

array vs linked list in JavaHere 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. First and major difference between linked list and array data structure is that former doesn't support random access, while later support random access. linked list is sequential, in order to retrieve an element, you need to traverse till that, while if you know index, you can retrieve an element from array very quickly, because it doesn't involved traversal.

2. 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. Third major difference is fixed length, array is a fixed length data structure, you provide length or size of 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. 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. 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 linked list.

6. Array can be one or multi-dimensional, while linked list can be singly, doubly or circular linked list. Two dimensional array are most common in multi-dimensional and used to represent matrix in Java. You can use two dimensional array to represent a plain of x,y coordinates, frequently used in Game programming. Java programming language provides support for creating array at syntax level, it supports both single and multidimensional array. Java API also provides a class called java.util.LinkedList, which is an implementation of doubly linked list data structure.

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

Further Reading
Algorithms and Data Structures - Part 1 and 2
Java Fundamentals, Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions

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)


Hardik Gohel said...

Jave, J2EE Tutorials with Example on

You can learn any java related technology with example and sample code easy way from guruzon. We have they have included following topics. You can download sample code and useful tools also.
Java basics, Hibernate, Hadoop ,Scala, Spring

grails cookbook said...

I wish I could use linked list in future programs. But as of now, I haven't thought which cases this structure is better than plain old array.

Anonymous said...

One of the good book on alogorithms is - Data Structures and Algorithms Made Easy in Java by Narasimha Karumanchi

Anonymous said...

Hi Javin,
Need a clarification on one of my recent interview question.
For search and sort which Collection datastructure to prefer : ArrayList or LinkedList.
I mentioned ArrayList would be the choice for retrieval operations as it implements Random Access whereas Linked list would be a better choice for insertion / deletion as it holds pointers for before and after node.
My followup question, so do you mean to say retrieval is faster using an Arraylist which holds 1million records ? I said if index is known we can use the contains() and get the value. But clarify me on this 1million scenario in real dynamic case i.e. without knowing index. Would ArrayList be still faster ?

Post a Comment