This article explain the differences between Array and Linked List (Array vs Linked List) in depth along with key points that will help you in deciding which one to use for a specific problem.

Table of Contents:

1. Differences between Array and Linked Lists
2. Basics of Array and Linked Lists
3. When to use Array over Linked List?
4. When to use Linked List over Array?

Differences between Array and Linked Lists

The Differences between Array and Linked Lists are as follows:

1. Memory allocated for array is contiguous memory while for Linked List, memory is allocated in discrete chunks (each chunk for a node).
2. If system memory is highly fragmented, there may not be a single big contiguous memory that can be allocated to an array. Hence, array allocation can fail even if memory is available. On the other hand, Linked List can take up any memory chunk.
3. For array, memory is allocated compile-time whereas for Linked List, memory is allocated run-time.
4. Array can use both statically allocated memory and dynamically allocated memory. Linked List can use only Dynamically allocated memory.
5. Accessing N-th element in array takes O(1) time while in Linked List, it takes O(N) time.
6. Deleting N-th element in array takes O(N) time if we want all elements to be together. In Linked List, deleting N-th element takes O(1) time if we do not consider the time to reach N-th element.
7. Merging two arrays of size O(N) takes O(N) time and new memory allocation. For merging two Linked Lists of size O(N), it takes O(1) time and no new memory allocation (provided we have access to the last and first node of each Linked List).
8. We need to define the total size of an array beforehand while in Linked List, the total size need not be defined. Dynamic Array is a solution to this limitation of array.
9. Worst case cost of inserting an element in Dynamic Array is O(N) time as we may need to resize the Dynamic Array. For Linked Lists, the worst case cost of inserting an element is O(1) time.
10. Array is considered to be safe in runtime as all required memory is pre-allocated. In this view, Linked List is not as safe as Array.
11. Array is an index based Data Structure but Linked List is not.

Basics of Array and Linked Lists

An array is defined as follows:

int array[] = new int[size];

Note: Memory is allocated at compile-time and entire memory is allocated beforehand.

A Linked List is defined as follows:

LinkedList<int> ll = new LinkedList<int>();

Note: No memory is allocated. Only a null pointer to Linked List is defined.

Adding element in an array is like:

array[last_index++] = new_element;

last_index is the index in which the new element should be inserted.

Adding element in a Linked List is like:

ll.add(new_element);

The process within the add() function is like

1. Create new node with new_element
2. Make the last node of Linked List to point to the new node.
3. New node becomes the last node of the Linked List.

Note: Memory is allocated dynamically in this case.
For adding new_element at the end of the Linked List, we need to traverse the Linked List to the end. We can avoid this by adding new element at the front.

When to use Array over Linked List?

You should use an Array over Linked List when:

1. Total number of elements to be inserted is known beforehand.
2. Accessing N-th element is a common operation.
3. You need to implement Algorithms that need random access.

Let us look into the points in more depth:

1. Total number of elements to be inserted is known beforehand.
   In this case, using array is considered to be a good option as memory allocation (which is a significant overhead) is done only once at the beginning. Memory related issues during runtime is minimized.

2. Accessing N-th element is a common operation.
   In this case, array must be used as random access allows for instant O(1) time access while in Linked List, it takes linear time O(N) time. Hence, arrays are more used in Database applications where random access is important.

3. You need to implement Algorithms that need random access.
   This is important as in certain algorithms using array is an optimization while using Linked List results in a overhead. Such algorithms where array is important are:

• Binary Search
• Interpolation Search
• Quick Sort
• Median of Medians algorithm
• and many more Algorithms.

When to use Linked List over Array?

You should use Linked List over Array when:

1. Inserting and Deleting new elements is a common operation.
2. Implementing Undo operation.
3. Array of Linked List.

Let us look into the points in more depth:

1. Inserting and Deleting new elements is a common operation.

In this case, Linked List must be used as depending on the implementation/ approach, insertion and deletion can be performed in constant time O(1) whereas in array, random deletions take linear time O(N) as all elements are readjusted.

2. Implementing Undo operation.
   The most common use case of Linked List is the implementation of undo operation in Browsers and Word editing softwares. This is the best option as the number of operations to be stored in memory varies and the only important operation is the go back. There can be branches and hence, Linked List is the perfect choice.

3. Array of Linked List.
   In many applications, we use an array of Linked List where at every index of the array, there is a Linked List. This structure is used in collision resolution in Hash Map.

With this article at OpenGenus, you must have the complete idea of the differences between Array and Linked List.