Array vs Linked List [Which one is better!]

In computer science, arrays and linked lists are two of the most commonly used data structures for storing and organizing data. They both have unique characteristics and are used for different purposes. In this blog, we will be discussing the differences between arrays and linked lists, as well as their advantages and disadvantages.

Array

An array is a collection of elements of the same type, stored in contiguous memory locations. Elements of an array can be accessed by their index, which is an integer value that starts at 0. For example, in the array [1, 2, 3] the element at the index 0 is 1, the element at the index 1 is 2, and the element at the index 2 is 3.

Here is an example of an array in Python:

# Declaring an array
numbers = [1, 2, 3, 4, 5]

# Accessing elements of an array
print(numbers[0]) # Output: 1
print(numbers[2]) # Output: 3

# Modifying elements of an array
numbers[3] = 6
print(numbers) # Output: [1, 2, 3, 6, 5]

Arrays are widely used in programming as they allow us to store multiple values in a single variable, and can be easily accessed and modified. It is important to note that arrays have a fixed size, which is determined when it is created, and cannot be changed later.

Advantages of Arrays:

Arrays have a fixed size, which means their size is determined at the time of creation and cannot be changed later. This makes them easy to manage and understand.
Arrays are stored in contiguous memory locations, which makes them cache friendly and therefore faster to access elements.
Arrays have a built-in index that allows for constant-time access to elements. This makes them very efficient for searching and accessing specific elements.
Arrays are widely supported in many programming languages, so they are easy to use and understand for most programmers.

Disadvantages of Arrays:

Arrays have a fixed size, which can be a limitation if the size of the data set is not known in advance or if it needs to change dynamically.
Insertion and deletion operations can be expensive, as they require the moving of other elements by one position.
Arrays use more memory as they store all the elements in contiguous memory locations.
Arrays are not suitable when memory allocation is a concern or when the size of the data set is huge.

Linked List

A linked list is a data structure that consists of a sequence of nodes, where each node contains a reference (or link) to the next node in the sequence. The first node is typically referred to as the head, and the last node is typically referred to as the tail.

Here is an example of a singly linked list in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()
# Output:
# 1
# 2
# 3

Linked Lists are useful in situations where the size of the data set may change during the execution of a program, and also it can save memory space since it doesn't need to store all the elements in contiguous memory locations.

In addition to singly linked lists, there are also doubly linked lists, which contain a reference to both the next and previous nodes in the sequence. These are useful in certain situations, such as when traversing the list in both directions is required.

Advantages of Linked Lists:

Linked Lists are dynamic data structures, which means their size can change during the execution of a program. This makes them suitable for situations where the size of the data set is not known in advance or if it needs to change dynamically.
Insertion and deletion operations are efficient in linked lists as they only require updating the links between nodes, which is O(1) operation.
Linked Lists are more memory efficient as they only store the value and reference to the next element, whereas arrays store all the elements in contiguous memory locations.
Linked lists can save memory space and also it's useful when you want to insert or delete elements in the middle of the list.

Disadvantages of Linked Lists:

Linked Lists are stored in non-contiguous memory locations, which means that elements are not stored in a contiguous block of memory. This makes them less cache-friendly and therefore slower to access elements.
Linked lists are not as easy to access elements as arrays, as they require traversing through the list to find a specific element.
Linked Lists are less widely supported in many programming languages, so they are not as easy to use and understand for most programmers.
Linked lists have a higher overhead as they require extra memory to store the reference(next pointer) to the next node.

Array vs Linked List

Memory allocation

Arrays are stored in contiguous memory locations, whereas linked lists are stored in non-contiguous memory locations and each node in the list contains a reference (or link) to the next node. For example, in an array, we can access an element by its index in constant time, but in a linked list, we have to traverse through the list to find a specific element.

Size

The size of an array is fixed, it is determined at the time of creation and cannot be changed later. A linked list can grow or shrink in size during the execution of a program.

Insertion and Deletion

Insertion and deletion operations are expensive in arrays as they require the moving of other elements by one position. But in a linked list, it only requires updating the links between nodes, which is O(1) operation.

Memory efficiency

Linked Lists are more memory efficient as they only store the value and reference to the next element whereas the array stores all the elements in contiguous memory locations.

Implementation

Arrays are implemented with a block of memory with a fixed size and elements are accessed by index, whereas linked lists are implemented with a collection of nodes, where each node contains a value and a reference to the next node in the list.

Both Array and Linked list have their advantages and disadvantages, it depends on the requirement of the problem which one to use.

What to use when?

Both arrays and linked lists have their advantages and disadvantages. The choice between the two depends on the specific requirements of the problem.

Arrays are better when:

The size of the data set is known in advance and does not change dynamically.
The program needs to access elements by their index in constant time.
The program requires cache-friendly memory allocation.
Memory allocation is not a concern.

Linked lists are better when:

The size of the data set is not known in advance or changes dynamically.
The program requires efficient insertion and deletion operations.
The program requires efficient use of memory.
The program requires insertion or deletion at the middle of the list.

In general, arrays are more suitable for situations where performance is critical and memory usage is not a concern. Linked lists are more suitable for situations where memory usage is critical and performance is not as important.

Conclusion

In conclusion, both arrays and linked lists have their advantages and disadvantages. The choice between the two depends on the specific requirements of the problem. Arrays are more suitable for situations where performance is critical and memory usage is not a concern. Linked lists are more suitable for situations where memory usage is critical and performance is not as important.