Singly Linked Lists

What you'll learn

A linked list stores each element in its own node, and each node holds a pointer to the next one. The nodes can live anywhere in memory — following the chain is how you get around. That flexibility flips the array's trade-offs on their head.

By the end you'll be able to:

• Describe a node and how pointers chain nodes together
• Insert and delete in O(1) by rewiring pointers
• Explain why there's no random access — reaching index i is O(n)
• Choose between an array and a linked list

Nodes & pointers

Each node bundles a value with a next pointer to the following node. A single head reference marks the start, and the last node's next is null — the end of the chain. There's no index arithmetic here: to reach the 5th node you must hop through the first four.

Insert at the head

The linked list's signature move: adding to the front is O(1), no matter how long the list is. Just point the new node at the current head, then move the head. Watch a list built entirely by head-insertion:

Deletion

Deleting a node is just re-linking: point the previous node past the one being removed. The work is finding the node (O(n)); the unlink itself is O(1):

In code

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

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

    def prepend(self, value):        # insert at head: O(1)
        node = Node(value)
        node.next = self.head
        self.head = node

    def search(self, value):         # O(n)
        node = self.head
        while node:
            if node.value == value:
                return True
            node = node.next
        return False

Arrays vs linked lists

Recap & quick check

One-way chains are handy but limited. Next we add a backward pointer and close the loop. Next up: Module 6 — Doubly & Circular Linked Lists.