icaoberg / Data structures - Linked List

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:17 -0400

Jupyter Notebook python

Data structures - Linked List¶

A linked list is a linear data structure where each element (node) stores a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory — insertion and deletion at any position are O(1) once you have a reference to the node, but random access is O(n).

This notebook covers:

What is a Linked List?
The Node and LinkedList classes
Core operations: append, prepend, insert_after, delete, search, size
Example: music playlist manager

1. What is a Linked List?¶

      head
        │
        ▼
   +-----+-----+     +-----+-----+     +-----+-----+     +-----+-------+
   |  A  |  •  | ──► |  B  |  •  | ──► |  C  |  •  | ──► |  D  | None  |
   +-----+-----+     +-----+-----+     +-----+-----+     +-----+-------+

Each node holds:

data — the stored value
next — a reference to the next node (None for the tail)

Operation	Description	Time complexity
`append(value)`	Add a node at the tail	O(n)
`prepend(value)`	Add a node at the head	O(1)
`insert_after(target, value)`	Insert after the first node matching target	O(n)
`delete(value)`	Remove the first node matching value	O(n)
`search(value)`	Return the node matching value or `None`	O(n)
`size()`	Return the number of nodes	O(n)
`to_list()`	Return all values as a Python list	O(n)

2. The `Node` and `LinkedList` classes¶

In [1]:

class Node:
    """A single node in a singly linked list."""

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

    def __repr__(self):
        return f"Node({self.data!r})"


class LinkedList:
    """Singly linked list with head pointer."""

    def __init__(self):
        self.head = None

    # ── Insertion ──────────────────────────────────────────────────────

    def prepend(self, value):
        """Insert *value* at the front of the list in O(1)."""
        node = Node(value)
        node.next = self.head
        self.head = node

    def append(self, value):
        """Insert *value* at the tail of the list in O(n)."""
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node

    def insert_after(self, target, value):
        """Insert *value* after the first node whose data equals *target*.
        Raises ValueError if *target* is not found.
        """
        current = self.head
        while current:
            if current.data == target:
                node = Node(value)
                node.next = current.next
                current.next = node
                return
            current = current.next
        raise ValueError(f"{target!r} not found in list")

    # ── Deletion ───────────────────────────────────────────────────────

    def delete(self, value):
        """Remove the first node whose data equals *value*.
        Raises ValueError if *value* is not found.
        """
        if self.head is None:
            raise ValueError(f"{value!r} not found in list")
        if self.head.data == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                return
            current = current.next
        raise ValueError(f"{value!r} not found in list")

    # ── Search ─────────────────────────────────────────────────────────

    def search(self, value):
        """Return the first Node whose data equals *value*, or None."""
        current = self.head
        while current:
            if current.data == value:
                return current
            current = current.next
        return None

    # ── Utility ────────────────────────────────────────────────────────

    def size(self):
        """Return the number of nodes in O(n)."""
        count, current = 0, self.head
        while current:
            count += 1
            current = current.next
        return count

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

    def is_empty(self):
        """Return True if the list has no nodes."""
        return self.head is None

    def __repr__(self):
        return " -> ".join(str(v) for v in self.to_list()) or "(empty)"

3. Core operations¶

In [2]:

ll = LinkedList()
print("Empty?  ", ll.is_empty())
print("List:   ", ll)

for v in ["B", "C", "D"]:
    ll.append(v)
    print(f"append({v!r})    →  {ll}")

ll.prepend("A")
print(f"prepend('A')  →  {ll}")

Empty?   True
List:    (empty)
append('B')    →  B
append('C')    →  B -> C
append('D')    →  B -> C -> D
prepend('A')  →  A -> B -> C -> D

In [3]:

ll.insert_after("B", "B2")
print(f"insert_after('B', 'B2')  →  {ll}")

insert_after('B', 'B2')  →  A -> B -> B2 -> C -> D

In [4]:

print("search('C'):  ", ll.search("C"))
print("search('Z'):  ", ll.search("Z"))
print("size():       ", ll.size())

search('C'):   Node('C')
search('Z'):   None
size():        5

In [5]:

ll.delete("B2")
print(f"delete('B2')  →  {ll}")

ll.delete("A")   # head deletion
print(f"delete('A')   →  {ll}")

ll.delete("D")   # tail deletion
print(f"delete('D')   →  {ll}")

delete('B2')  →  A -> B -> C -> D
delete('A')   →  B -> C -> D
delete('D')   →  B -> C

In [6]:

try:
    ll.delete("Z")
except ValueError as e:
    print("Caught:", e)

try:
    ll.insert_after("Z", "X")
except ValueError as e:
    print("Caught:", e)

Caught: 'Z' not found in list
Caught: 'Z' not found in list

4. Example: music playlist manager¶

A linked list is a natural fit for a playlist: songs can be inserted or removed anywhere without shifting elements, and the list is traversed sequentially during playback.

In [7]:

class Playlist:
    """Music playlist backed by a LinkedList."""

    def __init__(self, name):
        self.name = name
        self._songs = LinkedList()

    def add(self, song):
        """Add a song to the end of the playlist."""
        self._songs.append(song)

    def add_next(self, current_song, song):
        """Queue *song* to play immediately after *current_song*."""
        self._songs.insert_after(current_song, song)

    def remove(self, song):
        """Remove *song* from the playlist."""
        self._songs.delete(song)

    def play(self):
        """Print the full playback order."""
        songs = self._songs.to_list()
        print(f'Playlist: "{self.name}" ({len(songs)} songs)')
        for i, song in enumerate(songs, 1):
            print(f"  {i:>2}. {song}")


# Build a playlist
pl = Playlist("Road Trip Mix")
for song in ["Hotel California", "Bohemian Rhapsody", "Stairway to Heaven", "Wonderwall"]:
    pl.add(song)

print("── Initial playlist ──")
pl.play()

# Insert a song to play right after "Bohemian Rhapsody"
pl.add_next("Bohemian Rhapsody", "Don't Stop Me Now")
print("\n── After inserting 'Don't Stop Me Now' after 'Bohemian Rhapsody' ──")
pl.play()

# Remove a song
pl.remove("Wonderwall")
print("\n── After removing 'Wonderwall' ──")
pl.play()

── Initial playlist ──
Playlist: "Road Trip Mix" (4 songs)
   1. Hotel California
   2. Bohemian Rhapsody
   3. Stairway to Heaven
   4. Wonderwall

── After inserting 'Don't Stop Me Now' after 'Bohemian Rhapsody' ──
Playlist: "Road Trip Mix" (5 songs)
   1. Hotel California
   2. Bohemian Rhapsody
   3. Don't Stop Me Now
   4. Stairway to Heaven
   5. Wonderwall

── After removing 'Wonderwall' ──
Playlist: "Road Trip Mix" (4 songs)
   1. Hotel California
   2. Bohemian Rhapsody
   3. Don't Stop Me Now
   4. Stairway to Heaven

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.