Home » Programming » Arrays Vs Linked Lists
📌 Pin 🔗 Copy Link 📋 Copy Markdown ⬇️ Download
2 min read

Arrays vs Linked Lists

Arrays and Linked Lists are two of the most fundamental data structures used to store collections of elements. While they serve similar purposes, their underlying implementation and performance characteristics are vastly different.

1. Memory Layout

Arrays

  • Contiguous Memory: Elements are stored next to each other in memory.
  • Fixed Size: Traditionally, the size is determined at creation (though dynamic arrays like ArrayList or Python list abstract this).
  • Visual: [1][2][3][4]

Linked Lists

  • Non-Contiguous Memory: Elements (Nodes) can be scattered anywhere in memory.
  • Nodes: Each element is a "Node" containing the data and a pointer (reference) to the next node.
  • Visual: [1|*]-> [2|*]-> [3|*]-> null

2. Operations & Time Complexity (Big O)

Operation Array Linked List Note
Access (Read) $O(1)$ $O(n)$ Arrays allow random access via index. Lists require traversal.
Insertion (Beginning) $O(n)$ $O(1)$ Arrays must shift all elements. Lists just update the head pointer.
Insertion (End) $O(1)$* $O(1)$ *Arrays might need resizing ($O(n)$) if full. Lists just update the tail.
Insertion (Middle) $O(n)$ $O(1)$* *List insertion is $O(1)$ only if you already have the pointer to that location. Finding it is $O(n)$.
Deletion $O(n)$ $O(1)$ Similar to insertion.

3. Pros and Cons

Arrays

  • Pros:
    • Fast Lookups: Instant access to any element arr[500].
    • Cache Locality: Because memory is contiguous, CPU caching works very efficiently.
    • Memory Efficient: No overhead for storing pointers.
  • Cons:
    • Fixed Size: Resizing is expensive (requires copying entire array).
    • Slow Insert/Delete: Shifting elements is costly.

Linked Lists

  • Pros:
    • Dynamic Size: Can grow and shrink easily without reallocation.
    • Fast Insert/Delete: Adding/removing nodes is cheap if you have the pointer.
  • Cons:
    • Slow Lookups: Must traverse from the head to find an element ($O(n)$).
    • Memory Overhead: Extra memory needed for pointers (4-8 bytes per element).
    • Poor Cache Locality: Nodes are scattered, leading to cache misses.

4. Types of Linked Lists

  • Singly Linked List: Each node points to the next. Traversal is one-way.
  • Doubly Linked List: Each node points to the next and previous. Traversal is two-way, but uses more memory.
  • Circular Linked List: The last node points back to the head.

5. Doubly Linked List Implementation

A Doubly Linked List node contains data, a pointer to the next node, and a pointer to the previous node.

Node Structure (Python)

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return

        last = self.head
        while last.next:
            last = last.next

        last.next = new_node
        new_node.prev = last

programming/arrays-and-lists programming/algorithms programming/common-syntax

Backlinks

Created: March 17, 2026 • Last Modified: January 31, 2026