Differences Between Array and Linked List

Arrays and Linked Lists are two of the most fundamental data structures in computer science. While both are used to store collections of elements, they differ significantly in how they manage memory, access elements, and support operations like insertion and deletion.

Key Differences

Visual Representation

Array

Index:   [0] [1] [2] [3] [4]
Array:   [10][20][30][40][50]
Memory:  Contiguous addresses: 1000, 1004, 1008, 1012, 1016

Linked List

Head -> [10|*] -> [20|*] -> [30|*] -> [40|*] -> [50|*] -> NULL
Memory:  Each node can be at arbitrary addresses: 1000, 2000, 3000, etc.

Code Examples

Array Operations

# Python list (dynamic array)
arr = [10, 20, 30, 40, 50]

# Access: O(1)
print(arr[2])  # 30

# Insert at end: O(1) amortized
arr.append(60)

# Insert at beginning: O(n)
arr.insert(0, 5)

# Delete from end: O(1)
arr.pop()

# Delete from beginning: O(n)
arr.pop(0)

# Search: O(n)
print(arr.index(30))

Linked List Operations

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

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

    # Insert at beginning: O(1)
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Insert at end: O(n) without tail pointer
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # Delete from beginning: O(1)
    def delete_at_beginning(self):
        if self.head:
            self.head = self.head.next

    # Search: O(n)
    def search(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False

When to Use Which

Use an Array when:

• You need fast random access by index (O(1)).
• The size is known in advance or doesn't change frequently.
• You need cache‑friendly iteration.
• Memory overhead is a concern.
• You need to perform binary search (sorted array).

Use a Linked List when:

• You have frequent insertions/deletions at the beginning or middle.
• The size is dynamic and unpredictable.
• You don't need random access (sequential access is fine).
• Memory is not a constraint (or you need to avoid contiguous memory allocation).
• You're implementing other data structures like stacks, queues, or graphs.

Applications

Arrays are used in:

• Database indexing and table storage.
• Matrix and image processing.
• Lookup tables and caches.
• Implementing dynamic structures like heaps and hash tables.

Linked Lists are used in:

• Implementation of stacks, queues, and deques.
• Graph adjacency lists.
• Memory allocation and management (free lists).
• Undo/Redo functionality in editors.
• Music playlists and browser history.