Python · Arrays & Linked Lists

Complete Guide to Arrays & Linked Lists in Python

In this chapter you will learn two core data structures: arrays (Python lists) and linked lists. These are the foundation of many other structures (stacks, queues, hash tables, etc.).

What you will learn

How arrays work internally (contiguous memory, indexing, shifting)
Time complexity of array operations
How linked lists store nodes using pointers
Full Python implementation of a singly linked list
When to choose arrays vs linked lists

ARRAYS

1. Arrays

An array is a fundamental data structure that stores a collection of elements (values) in a contiguous block of memory. In Python, the built-in list type behaves like a dynamic array.

1.1 What Is an Array?

An array is a sequence of elements stored in contiguous memory. This allows very fast access by index.

Index: 0 1 2 3 Value: [10] [20] [30] [40] Memory: |10|20|30|40| (contiguous)

Python does not expose low-level C-style arrays directly, but its built-in list type behaves like a dynamic array.

1.2 Python List as Dynamic Array

Python's list type is a dynamic array that can grow and shrink in size. It supports fast index access and amortized O(1) appends.

1.3 Time Complexity for Arrays (Lists)

Here are the average time complexities for common array (list) operations in Python:

Operation	Average Time
Access by index `arr[i]`	O(1)
Append at end	O(1) amortized
Insert at index	O(n)
Delete / remove	O(n)
Search (unsorted)	O(n)

1.4 Typed Arrays with `array` Module

For memory-efficient storage of numbers, Python provides the array module (all elements have the same fixed type).

1.5 When to Use Arrays

Use arrays (Python lists) when:

You need fast random access by index
You work with fixed-size or mostly fixed-size data
You perform lots of sorting and numeric processing
You care about memory locality and cache friendliness

LINKED LISTS

2. Linked Lists

2.1 What Is a Linked List?

A linked list is a linear data structure where elements are stored in nodes, and each node contains a value and a reference (pointer) to the next node. Memory is not contiguous.

[10 | next] → [20 | next] → [30 | next] → None

Each node has:

data – the value
next – reference to the next node (or None)

2.2 Why Use Linked Lists?

Advantages:

Fast insertion and deletion at the head: O(1)
No need for contiguous memory
No expensive shifting of elements like in arrays

Disadvantages:

Slow access by position: O(n), you must traverse from the head
Extra memory for pointers (next, and maybe prev)
Cache-unfriendly compared to arrays

3. Implementing a Singly Linked List in Python

3.1 Node Class

Each node contains data and a pointer to the next node.

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

3.2 LinkedList Class with Core Operations

The LinkedList class manages the nodes and provides methods to manipulate the list.

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

def insert_at_front(self, data):
        """Insert new node at the beginning (O(1))."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

def insert_at_end(self, data):
        """Insert new node at the end (O(n))."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

def search(self, target):
        """Return True if target is found, else False (O(n))."""
        curr = self.head
        while curr:
            if curr.data == target:
                return True
            curr = curr.next
        return False

def delete(self, target):
        """Delete first node with value == target (O(n))."""
        curr = self.head

# If head is the node to delete
        if curr and curr.data == target:
            self.head = curr.next
            return

prev = None
        while curr and curr.data != target:
            prev = curr
            curr = curr.next

# If found, unlink it
        if curr:
            prev.next = curr.next

def to_list(self):
        """Return Python list of all node values."""
        result = []
        curr = self.head
        while curr:
            result.append(curr.data)
            curr = curr.next
        return result

3.3 Using the Linked List

Example usage of the LinkedList class:

ll = LinkedList()
ll.insert_at_front(10)   # [10]
ll.insert_at_front(5)    # [5, 10]
ll.insert_at_end(20)     # [5, 10, 20]

print(ll.to_list())      # [5, 10, 20]
print(ll.search(10))     # True
print(ll.search(99))     # False

ll.delete(10)            # [5, 20]
print(ll.to_list())

4. Time Complexity of Linked Lists

Here are the average time complexities for common linked list operations:

Operation	Time
Insert at head	O(1)
Insert at end (no tail pointer)	O(n)
Delete head	O(1)
Delete by value (search + unlink)	O(n)
Search by value	O(n)
Access by index	O(n)

We usually do not use linked lists when we need random access by index. They shine when we care about frequent insertions and deletions.

5. Types of Linked Lists

5.1 Singly Linked List

Each node points only to the next node.

[10] → [20] → [30] → None

5.2 Doubly Linked List

Each node points to both previous and next nodes.

None ← [10] ⇄ [20] ⇄ [30] ← None

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

Python's collections.deque is implemented as a doubly-linked list, optimized for fast appends and pops from both ends.

5.3 Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circle.

[10] → [20] → [30] ↑ ↓ ← ← ← ← ← ←

Useful for round-robin scheduling or cyclic buffers.

6. Arrays vs Linked Lists (Comparison)

Here is a side-by-side comparison of arrays (Python lists) and linked lists:

Feature	Array (Python list)	Linked List
Memory layout	Contiguous block	Scattered nodes with pointers
Access by index	O(1)	O(n) (must traverse)
Insert at head	O(n) (shift elements)	O(1)
Insert in middle	O(n)	O(n) (find node, then link)
Delete at head	O(n)	O(1)
Memory overhead	Lower (only values)	Higher (values + pointers)
Cache friendliness	High (contiguous)	Low (jumps in memory)
Typical uses	Random access, numeric arrays, sorting	Queues, stacks, LRU cache, playlists

7. When to Use Arrays vs Linked Lists

Here are guidelines on when to choose arrays (lists) or linked lists:

7.1 Use an Array (List) when...

You need fast indexing: arr[i]
Your data size is known or changes infrequently
You perform many sorting and searching operations
You want better CPU cache performance

7.2 Use a Linked List when...

You need frequent insertions and deletions without shifting:

You frequently insert or delete elements at the beginning
You implement queues, stacks, or LRU caches
You do not need random access by index
You prefer stable references to nodes while modifying the list

8. Classic Problems (Arrays & Linked Lists)

Here are some classic coding problems involving arrays and linked lists to practice your skills:

8.1 Array Problems

Two Sum – find two numbers that add up to a target
Maximum Subarray – Kadane's algorithm
Product of Array Except Self
Merge Intervals
Rotate Array
Find Missing Number in 1..n

8.2 Linked List Problems

Here are some common linked list problems to solve:

Reverse a Linked List
Detect Cycle (Floyd's cycle detection)
Merge Two Sorted Lists
Find Middle Node
Remove N-th Node From End
Add Two Numbers (numbers stored as linked lists)

These are very common in coding interviews and are excellent practice for mastering arrays and linked lists.