# 🔗 Linked Lists in the Age of AI

**A beginner-friendly and humorous guide to linked lists, nodes, references, operations, time complexity, cycle detection, reversal, and practical AI use cases with Python.**

* * *

# 😂 Everyone Knows Only the Next Person

Imagine a queue outside a famous food stall.

The first person knows who is standing behind them. That person knows the next person, and so on.

But if you ask the first person:

> “Who is standing at position 927?”

They cannot instantly point to that person. They must ask:

> “Who is next?”

Then that person asks the same question, until the stall has closed and your program has finally reached node number 927.

Congratulations. You have understood a **linked list**. 😄

A linked list is a collection of elements called **nodes**. Each node normally stores:

1.  Some data
    
2.  A reference to another node
    

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/6fcf5856-9acb-4563-bb76-463f61f78460.png align="center")

The first node is the **head**. The final node usually points to `None`, which is Python’s way of saying:

> “Boss, there is nobody after me.”

* * *

# 🤖 Why Linked Lists Still Matter in AI

Modern AI is dominated by tensors, arrays, GPUs, embeddings, and matrices. Those structures benefit from compact, contiguous memory.

So are linked lists useless in AI?

Not at all.

Linked structures help us understand or build:

*   Dynamic queues
    
*   Agent execution traces
    
*   Undo and redo histories
    
*   Streaming pipelines
    
*   LRU caches
    
*   Graph adjacency lists
    
*   Sparse and irregular relationships
    
*   Workflow chains
    
*   Memory allocators
    
*   Event-processing systems
    

They also teach important ideas:

*   References
    
*   Object identity
    
*   Dynamic memory
    
*   Two-pointer algorithms
    
*   Time complexity
    
*   Data-structure trade-offs
    

However, remember:

> Linked lists are not automatically faster just because insertion can be `O(1)`.

For dense numerical AI operations, Python lists, NumPy arrays, and tensors are generally better because they support fast indexing, compact storage, and hardware-friendly access.

Linked lists are most useful when relationships and dynamic updates matter more than random access.

* * *

# 🧱 What Is a Node?

A node stores a value and a link to the next node.

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

Create two nodes:

```python
first = Node("AI")
second = Node("Python")

first.next = second
```

Now:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/eb89b80b-3061-4853-82b5-b937c41fe4e2.png align="center")

![]( align="center")

`first.next` does not copy the second node. It stores a reference to it.

That connects directly to memory management: nodes are separate objects joined through references.

* * *

# 📦 Building a Basic Singly Linked List

A **singly linked list** supports movement in one direction.

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None
```

Initially:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/62e5d1af-3fb4-4c97-8dc2-fabaa7dae3d1.png align="center")

Core terms:

*   **Head:** first node
    
*   **Tail:** final node
    
*   **Traversal:** visiting nodes one by one
    
*   **Insertion:** adding a node
    
*   **Deletion:** removing a node
    
*   **Search:** finding a value
    
*   **Cycle:** a path that eventually returns to a previous node
    

A cycle is the linked-list version of:

> “We are going in circles.”

Except the computer means it literally.

* * *

# 🚶 Traversal

To display values, start at the head and follow `next`.

```python
class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def display(self):
        current = self.head

        while current is not None:
            print(current.value, end=" -> ")
            current = current.next

        print("None")
```

Example:

```python
first = Node("AI")
second = Node("Python")
third = Node("RAG")

first.next = second
second.next = third

linked_list = SinglyLinkedList()
linked_list.head = first

linked_list.display()
```

Output:

```text
AI -> Python -> RAG -> None
```

### Complexity

Time:

```text
O(n)
```

Extra space:

```text
O(1)
```

Unlike arrays, linked lists do not provide direct indexed access. To reach node 500, we normally walk through nodes 0 to 499 first.

* * *

# ⚡ Insert at the Beginning

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/aa848cfd-d4a1-49ae-ae91-827a4fcceb5d.png align="center")

```python
class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
```

Before:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/7089d1e8-7a18-428e-a5d9-d867836e1de8.png align="center")

After prepending `"DSA"`:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/79cb9085-4cc7-47f9-aed7-0d270f4e7120.png align="center")

Time:

```text
O(1)
```

Only two references change.

This remains constant whether the list contains five nodes or five million.

* * *

# 🏁 Insert at the End

Without a tail reference:

```python
def append(self, value):
    new_node = Node(value)

    if self.head is None:
        self.head = new_node
        return

    current = self.head

    while current.next is not None:
        current = current.next

    current.next = new_node
```

Time:

```text
O(n)
```

We must find the final node.

## Improve it with a tail

```python
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node
```

Now append is:

```text
O(1)
```

Maintaining one extra reference saves repeated traversal.

* * *

# 🎯 Insert After a Value

```python
def insert_after(self, target, value):
    current = self.head

    while current is not None:
        if current.value == target:
            new_node = Node(value)
            new_node.next = current.next
            current.next = new_node

            if self.tail is current:
                self.tail = new_node

            return True

        current = current.next

    return False
```

Searching for the target:

```text
O(n)
```

The actual pointer update after finding it:

```text
O(1)
```

Overall:

```text
O(n)
```

So when somebody says:

> “Linked-list insertion is always O(1),”

ask:

> “Do we already have the node, or are we first searching the whole list?”

The insertion is fast. Finding the location may not be.

* * *

# 📍 Insert at a Position

```python
def insert_at(self, index, value):
    if index < 0:
        raise IndexError("Index cannot be negative")

    if index == 0:
        self.prepend(value)
        return

    current = self.head
    current_index = 0

    while (
        current is not None
        and current_index < index - 1
    ):
        current = current.next
        current_index += 1

    if current is None:
        raise IndexError("Index out of range")

    new_node = Node(value)
    new_node.next = current.next
    current.next = new_node

    if new_node.next is None:
        self.tail = new_node
```

Time:

```text
O(n)
```

The list must be traversed to the requested position.

* * *

# 🔎 Search for a Value

```python
def contains(self, target):
    current = self.head

    while current is not None:
        if current.value == target:
            return True

        current = current.next

    return False
```

Best case:

```text
O(1)
```

Worst and average case:

```text
O(n)
```

Every node knows only the next node. Nobody has the complete attendance sheet.

* * *

# 🎲 Access by Index

```python
def get(self, index):
    if index < 0:
        raise IndexError("Index cannot be negative")

    current = self.head
    current_index = 0

    while current is not None:
        if current_index == index:
            return current.value

        current = current.next
        current_index += 1

    raise IndexError("Index out of range")
```

Time:

```text
O(n)
```

Array access is normally `O(1)`. Linked-list indexed access is `O(n)`.

This is one reason arrays dominate tensor and vector workloads. A GPU wants a predictable block of numbers, not a treasure hunt through Python objects.

* * *

# 🗑️ Delete the Head

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/847eefe8-d153-4118-b69a-820cec0ce4da.png align="center")

```python
def delete_first(self):
    if self.head is None:
        return None

    removed_value = self.head.value
    self.head = self.head.next

    if self.head is None:
        self.tail = None

    return removed_value
```

Time:

```text
O(1)
```

We simply move the head reference.

* * *

# 🗑️ Delete the Tail

In a singly linked list, the tail does not know the previous node.

```python
def delete_last(self):
    if self.head is None:
        return None

    if self.head.next is None:
        removed_value = self.head.value
        self.head = None
        self.tail = None
        return removed_value

    current = self.head

    while current.next.next is not None:
        current = current.next

    removed_value = current.next.value
    current.next = None
    self.tail = current

    return removed_value
```

Time:

```text
O(n)
```

Even with a tail reference, we must find the second-last node.

This is where a doubly linked list becomes useful.

* * *

# ✂️ Delete a Specific Value

```python
def delete_value(self, target):
    if self.head is None:
        return False

    if self.head.value == target:
        self.delete_first()
        return True

    current = self.head

    while current.next is not None:
        if current.next.value == target:
            node_to_remove = current.next
            current.next = node_to_remove.next

            if node_to_remove is self.tail:
                self.tail = current

            return True

        current = current.next

    return False
```

Time:

```text
O(n)
```

The pointer update is constant time, but the search may visit the whole list.

* * *

# 📏 Length of the List

## Traverse every time

```python
def length(self):
    count = 0
    current = self.head

    while current is not None:
        count += 1
        current = current.next

    return count
```

Time:

```text
O(n)
```

## Maintain a size attribute

```python
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size
```

Now length is:

```text
O(1)
```

But every successful insertion and deletion must update `size`.

Forget one decrement and your linked list begins lying about its age.

* * *

# 🔄 Reverse a Linked List

Original:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/1c9de0b2-0f2d-4553-a3ba-5babf6398024.png align="center")

Reversed:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/3f31076c-23ee-4a7e-b527-c748cd9a96c5.png align="center")

Use three references:

```python
def reverse(self):
    previous = None
    current = self.head

    self.tail = self.head

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    self.head = previous
```

We must save `next_node` before changing `current.next`.

Otherwise we lose the rest of the list.

That is less “reverse the list” and more “accidentally delete the project roadmap.”

Time:

```text
O(n)
```

Extra space:

```text
O(1)
```

## Recursive reversal

```python
def reverse_recursive(self):
    def reverse_node(node):
        if node is None or node.next is None:
            return node

        new_head = reverse_node(node.next)

        node.next.next = node
        node.next = None

        return new_head

    self.tail = self.head
    self.head = reverse_node(self.head)
```

Time:

```text
O(n)
```

Auxiliary space:

```text
O(n)
```

because recursion creates call frames.

The iterative version is usually more memory-efficient.

* * *

# 🎯 Find the Middle Node

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/a9aefc80-a89e-4137-aaa0-d3281802a690.png align="center")

Use slow and fast pointers:

```python
def find_middle(self):
    slow = self.head
    fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    return None if slow is None else slow.value
```

The slow pointer moves one step.

The fast pointer moves two.

When fast reaches the end, slow is near the middle.

Time:

```text
O(n)
```

Space:

```text
O(1)
```

This two-pointer pattern is useful for:

*   Finding the middle
    
*   Cycle detection
    
*   Finding the kth node from the end
    
*   Palindrome checks
    

The fast pointer is basically an intern who runs ahead and gathers information.

* * *

# 🔙 Find the Kth Node from the End

```python
def kth_from_end(self, k):
    if k <= 0:
        raise ValueError("k must be positive")

    first = self.head
    second = self.head

    for _ in range(k):
        if first is None:
            raise IndexError("k is larger than the list")

        first = first.next

    while first is not None:
        first = first.next
        second = second.next

    return second.value
```

Time:

```text
O(n)
```

Space:

```text
O(1)
```

The pointers maintain a gap of `k` nodes.

* * *

# ♻️ Detect a Cycle

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/a5732314-5783-4621-8bb3-59e77a52ad62.png align="center")

A cyclic list may look like:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/f8e5616e-b6d0-470f-9891-9fa5c7c1cabd.png align="center")

A normal traversal would never end.

## Floyd’s cycle detection

```python
def has_cycle(self):
    slow = self.head
    fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            return True

    return False
```

Time:

```text
O(n)
```

Space:

```text
O(1)
```

This is also called the tortoise-and-hare algorithm.

The hare runs faster, but the tortoise wins by having a better contract.

* * *

# 📍 Find the Start of a Cycle

```python
def cycle_start(self):
    slow = self.head
    fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            break
    else:
        return None

    slow = self.head

    while slow is not fast:
        slow = slow.next
        fast = fast.next

    return slow
```

After the first meeting, move one pointer to the head. Move both one step at a time. Their next meeting is the cycle start.

Time:

```text
O(n)
```

Space:

```text
O(1)
```

* * *

# 🔗 Merge Two Sorted Linked Lists

```python
def merge_sorted_lists(first, second):
    dummy = Node(0)
    current = dummy

    while first is not None and second is not None:
        if first.value <= second.value:
            current.next = first
            first = first.next
        else:
            current.next = second
            second = second.next

        current = current.next

    current.next = first if first is not None else second

    return dummy.next
```

For lists of sizes `n` and `m`:

Time:

```text
O(n + m)
```

Extra space:

```text
O(1)
```

when existing nodes are reused.

The dummy node handles edge cases and receives no credit in the final output. Classic office behaviour.

* * *

# 🧩 Find the Intersection of Two Lists

An intersection means the lists share the same node object:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/f8e43b56-70a2-458e-9b7b-d2636182c1be.png align="center")

```python
def find_intersection(head_a, head_b):
    pointer_a = head_a
    pointer_b = head_b

    while pointer_a is not pointer_b:
        pointer_a = (
            head_b
            if pointer_a is None
            else pointer_a.next
        )

        pointer_b = (
            head_a
            if pointer_b is None
            else pointer_b.next
        )

    return pointer_a
```

Each pointer traverses both lists, equalizing the distance.

Time:

```text
O(n + m)
```

Space:

```text
O(1)
```

Use identity (`is`), not only value equality. Two nodes may contain `"AI"` without being the same node.

* * *

# 🧮 Remove Duplicates

Use a set for an unsorted list:

```python
def remove_duplicates(self):
    seen = set()
    current = self.head
    previous = None

    while current is not None:
        if current.value in seen:
            previous.next = current.next

            if current is self.tail:
                self.tail = previous
        else:
            seen.add(current.value)
            previous = current

        current = current.next
```

Average time:

```text
O(n)
```

Extra space:

```text
O(n)
```

Without extra memory, compare each node with all later nodes:

Time:

```text
O(n²)
```

Space:

```text
O(1)
```

Trade memory for speed—the same negotiation behind caches, indexes, embeddings, and KV cache.

* * *

# 🔁 Palindrome Check

Example:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/91fd2b67-b497-46d3-9832-d2abcfadf93e.png align="center")

Approach:

1.  Find the middle
    
2.  Reverse the second half
    
3.  Compare both halves
    

```python
def is_palindrome(self):
    if self.head is None or self.head.next is None:
        return True

    slow = self.head
    fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    previous = None
    current = slow

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    left = self.head
    right = previous

    while right is not None:
        if left.value != right.value:
            return False

        left = left.next
        right = right.next

    return True
```

Time:

```text
O(n)
```

Space:

```text
O(1)
```

Restore the second half afterward when preserving the original list matters.

* * *

# ↔️ Doubly Linked Lists

A doubly linked node knows both neighbours:

```python
class DoublyNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.previous = None
```

Structure:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/68cba23e-e871-4ffa-801d-5e60ea446564.png align="center")

```python
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
```

## Append

```python
def append(self, value):
    new_node = DoublyNode(value)

    if self.tail is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.previous = self.tail
        self.tail.next = new_node
        self.tail = new_node

    self.size += 1
```

Time:

```text
O(1)
```

## Prepend

```python
def prepend(self, value):
    new_node = DoublyNode(value)

    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.previous = new_node
        self.head = new_node

    self.size += 1
```

Time:

```text
O(1)
```

## Delete a Known Node

```python
def delete_node(self, node):
    if node.previous is None:
        self.head = node.next
    else:
        node.previous.next = node.next

    if node.next is None:
        self.tail = node.previous
    else:
        node.next.previous = node.previous

    self.size -= 1
```

If the node reference is already known:

```text
O(1)
```

### Trade-off

A doubly linked list uses more memory because each node stores another reference.

You gain backward traversal and faster deletion of known nodes, but you also gain more bookkeeping and more chances to connect the previous pointer to something it should have emotionally moved on from.

* * *

# 🔄 Circular Linked Lists

In a circular linked list, the final node points back to the head:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/572935ea-4a34-47e9-8899-d627e7c677d3.png align="center")

Use cases:

*   Round-robin scheduling
    
*   Repeating playlists
    
*   Turn rotation
    
*   Cyclic task assignment
    
*   Circular buffers
    

Traversal must stop when we reach the head again:

```python
def display_circular(head):
    if head is None:
        return

    current = head

    while True:
        print(current.value, end=" -> ")
        current = current.next

        if current is head:
            break

    print("(back to head)")
```

A missing stop condition produces an infinite loop.

The data structure is not broken. It is obeying your instructions with dangerous enthusiasm.

* * *

# 🆚 Arrays vs Linked Lists

| Operation | Dynamic Array / Python List | Singly Linked List |
| --- | --- | --- |
| Access by index | `O(1)` | `O(n)` |
| Search | `O(n)` | `O(n)` |
| Insert at beginning | `O(n)` | `O(1)` |
| Insert at end | Amortized `O(1)` | `O(1)` with tail |
| Delete beginning | `O(n)` | `O(1)` |
| Delete end | Usually `O(1)` | `O(n)` |
| Insert after known node | Not the same model | `O(1)` |
| Memory locality | Good | Poor |
| Extra link memory | Low | One or more references per node |

## Why arrays are often faster in practice

Big O is not the complete story.

Arrays provide:

*   Better CPU cache locality
    
*   Compact memory
    
*   Fast indexing
    
*   Fewer object allocations
    
*   Vectorization
    
*   GPU compatibility
    

Linked lists require:

*   One node object per element
    
*   Extra references
    
*   Pointer chasing
    
*   Poor memory locality
    
*   Allocation overhead
    

In Python, each node is a full object. For millions of small values, a linked list can use dramatically more memory than an array.

So even when both structures have `O(n)` traversal, the array may be much faster in practice.

* * *

# 💾 Space Complexity and `__slots__`

A singly linked list with `n` nodes requires:

```text
O(n)
```

total space.

Each node stores:

```text
Data + Next reference
```

A doubly linked node stores:

```text
Previous reference + Data + Next reference
```

A normal Python class often has an instance dictionary. When creating many nodes, `__slots__` can reduce overhead:

```python
class Node:
    __slots__ = ("value", "next")

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

Use `__slots__` when:

*   Creating many lightweight objects
    
*   Dynamic attributes are unnecessary
    
*   Memory consumption matters
    

It does not transform a Python linked list into a NumPy array, but it can make each node less expensive.

* * *

# 🤖 Where Linked Structures Appear in AI

Linked lists are not used for every AI workload.

Storing model weights as Python nodes would make your GPU cry before inference begins.

But linked structures appear in several useful places.

* * *

# 🧠 1. Agent Execution Traces

An AI agent may perform:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/2fca3cdf-efc7-4b06-a655-a746f47e8d83.png align="center")

A step can reference the next step:

```python
class AgentStep:
    def __init__(self, action, result=None):
        self.action = action
        self.result = result
        self.next = None
```

This can support:

*   Workflow inspection
    
*   Dynamic insertion of steps
    
*   Replaying execution
    
*   Failure analysis
    
*   Explainability traces
    

In many Python applications, a built-in list is simpler. A linked structure becomes useful when steps are inserted, removed, or reconnected dynamically.

* * *

# ⏪ 2. Undo and Redo Histories

An AI editor may support:

*   Generate
    
*   Rewrite
    
*   Undo
    
*   Redo
    
*   Compare versions
    

A doubly linked history allows movement both ways:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/9785153a-502a-4fad-af6e-b71a60170090.png align="center")

```python
class Version:
    def __init__(self, content):
        self.content = content
        self.previous = None
        self.next = None
```

This resembles browser navigation.

* * *

# 🗃️ 3. LRU Cache Internals

An LRU cache removes the least recently used entry.

A common design combines:

*   A dictionary for `O(1)` key lookup
    
*   A doubly linked list for `O(1)` order updates
    

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/607182f9-00ca-42e6-a4d5-512bc8f0c5bb.png align="center")

When an entry is used:

1.  Find it in the dictionary
    
2.  Move its node to the front
    
3.  Remove the tail when capacity is exceeded
    

This pattern is relevant for caching:

*   Embeddings
    
*   Prompt results
    
*   Retrieved documents
    
*   Model responses
    
*   Feature computations
    

A linked list alone cannot give fast lookup by key. The performance comes from combining data structures.

Good architecture is often two ordinary structures cooperating instead of one magical structure doing everything.

* * *

# 🌐 4. Graph Adjacency Lists

AI systems use graphs for:

*   Knowledge graphs
    
*   Recommendations
    
*   Social connections
    
*   Agent workflows
    
*   Search and planning
    

Historically, adjacency lists could be implemented using linked lists.

In Python, ordinary lists are often used:

```python
graph = {
    "AI": ["ML", "NLP"],
    "ML": ["Deep Learning"],
    "NLP": ["LLM"]
}
```

The conceptual structure is dynamic and relationship-based even if the implementation uses arrays.

* * *

# 🌊 5. Processing Pipelines

A dynamic pipeline may look like:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/a3988b78-f5d7-4e5b-95e3-d047e6d63988.png align="center")

```python
class Handler:
    def __init__(self):
        self.next_handler = None

    def set_next(self, handler):
        self.next_handler = handler
        return handler

    def handle(self, data):
        if self.next_handler is not None:
            return self.next_handler.handle(data)

        return data
```

This resembles the **chain of responsibility** pattern.

Pipeline stages can be inserted, removed, or replaced without rewriting the entire flow.

* * *

# 🧬 6. Sparse and Irregular Structures

Linked relationships help when:

*   Each item has a different number of neighbours
    
*   Connections change often
    
*   Traversal follows relationships
    
*   Nodes are inserted dynamically
    

Examples:

*   Parse structures
    
*   Symbolic AI systems
    
*   Rule engines
    
*   Search trees
    
*   Knowledge representations
    

Production implementations may use arrays, maps, compressed sparse formats, or graph libraries for better performance.

The linked-list concept remains useful even when the exact physical structure differs.

* * *

# 🎮 7. AI Serving and Memory Blocks

Production inference systems may manage KV-cache pages, free blocks, or request queues through linked free structures or similar low-level techniques.

They may track:

*   Available blocks
    
*   Occupied blocks
    
*   Eviction order
    
*   Request ownership
    
*   Reusable memory regions
    

The Python developer sees:

```python
model.generate(...)
```

The serving engine sees:

> “Which memory block belongs to which request, and who forgot to release it?”

* * *

# ⚠️ When a Linked List Is a Bad Choice

Avoid it when you need:

## Fast random access

```python
value = data[500_000]
```

Arrays win.

## Dense numerical operations

Matrix multiplication, convolution, and attention require tensors or array-like layouts.

## GPU computation

GPUs prefer large contiguous memory blocks and predictable access.

## Compact storage

A Python object per value adds substantial overhead.

## Simple append-only collections

Python’s built-in list may be easier and faster.

## Queue operations in Python

`collections.deque` is usually a better production choice than writing your own linked queue.

Do not use a linked list because the data “feels connected.”

Everything in a grocery list is connected by your hunger. That does not require custom nodes.

* * *

# 🛠️ Complete Singly Linked List Implementation

```python
class Node:
    __slots__ = ("value", "next")

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.head is None

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

        if self.tail is None:
            self.tail = new_node

        self.size += 1

    def append(self, value):
        new_node = Node(value)

        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

        self.size += 1

    def insert_at(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")

        if index == 0:
            self.prepend(value)
            return

        if index == self.size:
            self.append(value)
            return

        current = self.head

        for _ in range(index - 1):
            current = current.next

        new_node = Node(value)
        new_node.next = current.next
        current.next = new_node
        self.size += 1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")

        current = self.head

        for _ in range(index):
            current = current.next

        return current.value

    def contains(self, target):
        current = self.head

        while current is not None:
            if current.value == target:
                return True

            current = current.next

        return False

    def delete_first(self):
        if self.head is None:
            return None

        removed_value = self.head.value
        self.head = self.head.next
        self.size -= 1

        if self.head is None:
            self.tail = None

        return removed_value

    def delete_last(self):
        if self.head is None:
            return None

        if self.head is self.tail:
            removed_value = self.head.value
            self.head = None
            self.tail = None
            self.size = 0
            return removed_value

        current = self.head

        while current.next is not self.tail:
            current = current.next

        removed_value = self.tail.value
        current.next = None
        self.tail = current
        self.size -= 1

        return removed_value

    def delete_value(self, target):
        if self.head is None:
            return False

        if self.head.value == target:
            self.delete_first()
            return True

        current = self.head

        while current.next is not None:
            if current.next.value == target:
                node_to_remove = current.next
                current.next = node_to_remove.next

                if node_to_remove is self.tail:
                    self.tail = current

                self.size -= 1
                return True

            current = current.next

        return False

    def reverse(self):
        previous = None
        current = self.head
        self.tail = self.head

        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node

        self.head = previous

    def find_middle(self):
        if self.head is None:
            return None

        slow = self.head
        fast = self.head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow.value

    def has_cycle(self):
        slow = self.head
        fast = self.head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True

        return False

    def clear(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __iter__(self):
        current = self.head

        while current is not None:
            yield current.value
            current = current.next

    def __str__(self):
        if self.head is None:
            return "None"

        return " -> ".join(
            str(value)
            for value in self
        ) + " -> None"
```

Usage:

```python
topics = SinglyLinkedList()

topics.append("Big O")
topics.append("Classes & Objects")
topics.append("Memory Management")
topics.append("Linked Lists")

print(topics)
print(len(topics))
print(topics.find_middle())

topics.reverse()

print(topics)
```

* * *

# 📊 Time Complexity Cheat Sheet

## Singly Linked List

| Operation | Without Tail/Size | With Tail/Size |
| --- | --- | --- |
| Access head | `O(1)` | `O(1)` |
| Access tail | `O(n)` | `O(1)` |
| Access by index | `O(n)` | `O(n)` |
| Search | `O(n)` | `O(n)` |
| Prepend | `O(1)` | `O(1)` |
| Append | `O(n)` | `O(1)` |
| Delete head | `O(1)` | `O(1)` |
| Delete tail | `O(n)` | `O(n)` |
| Insert after known node | `O(1)` | `O(1)` |
| Delete after known node | `O(1)` | `O(1)` |
| Get length | `O(n)` | `O(1)` |
| Reverse | `O(n)` | `O(n)` |
| Find middle | `O(n)` | `O(n)` |
| Detect cycle | `O(n)` | `O(n)` |

## Doubly Linked List

| Operation | Complexity |
| --- | --- |
| Access by index | `O(n)` |
| Search | `O(n)` |
| Prepend | `O(1)` |
| Append with tail | `O(1)` |
| Delete head | `O(1)` |
| Delete tail | `O(1)` |
| Delete known node | `O(1)` |
| Move to next or previous | `O(1)` per step |
| Full traversal | `O(n)` |

## Important Reminder

`O(1)` insertion usually assumes that the insertion node or position is already known.

If we first search for the position, the complete operation may still be:

```text
O(n)
```

* * *

# 🎤 Common Interview Questions

## Why is insertion at the head `O(1)`?

Because we change only a fixed number of references:

```python
new_node.next = head
head = new_node
```

## Why is indexed access `O(n)`?

Nodes are not addressed through direct offsets. We must follow links from the head.

## Is appending always `O(1)`?

Only when a tail reference is maintained. Without it, appending requires traversal.

## Why is deleting the tail of a singly linked list `O(n)`?

We need the previous node, but the list stores only forward links.

## Why can a doubly linked list delete a known node in `O(1)`?

The node directly references both neighbours.

## What is the disadvantage of a doubly linked list?

Extra memory and more complex reference maintenance.

## How do you detect a cycle without extra memory?

Use Floyd’s slow-and-fast pointer algorithm.

## What is the difference between `==` and `is` for nodes?

`==` may compare values. `is` checks whether two references identify the exact same object.

## Why are linked lists less cache-friendly?

Nodes may be scattered across memory, forcing the processor to chase references rather than scanning a compact block.

## Are linked lists frequently used directly in Python?

The concepts are common, but built-ins such as `list`, `deque`, dictionaries, and specialized libraries are usually more practical.

## When should a linked list be preferred?

When frequent insertion or deletion around already-known nodes matters more than fast random access and compact memory.

* * *

# 🚨 Common Mistakes

## 1\. Losing the Rest of the List

Wrong reversal logic:

```python
current.next = previous
current = current.next
```

After changing `current.next`, the original next node is lost.

Correct:

```python
next_node = current.next
current.next = previous
current = next_node
```

## 2\. Forgetting the Empty-List Case

Always handle:

```python
if self.head is None:
```

## 3\. Forgetting to Update the Tail

Deleting or appending around the end may require changing `self.tail`.

## 4\. Incorrect Size Tracking

Every successful insertion and deletion should update `size` exactly once.

## 5\. Infinite Traversal Because of a Cycle

A normal display method may never terminate if the list contains a loop.

## 6\. Comparing Values Instead of Node Identity

Two nodes can both store `"AI"` and still be different objects.

## 7\. Accidentally Sharing Nodes Across Lists

Two lists may unintentionally share the same tail. Updating one structure can affect the other.

## 8\. Assuming Theoretical Complexity Guarantees Speed

Poor cache locality and Python-object overhead may make linked lists slower than built-in arrays even when Big O looks attractive.

* * *

# ✅ Questions to Ask Before Choosing a Linked List

*   Do I need fast random access?
    
*   Will I traverse nearly every item frequently?
    
*   Do I already know the node where insertion occurs?
    
*   Are insertions and deletions more common than indexing?
    
*   Is extra node memory acceptable?
    
*   Does CPU cache locality matter?
    
*   Will the data be processed on a GPU?
    
*   Would `collections.deque` solve the problem more simply?
    
*   Do I need backward traversal?
    
*   Can cycles occur?
    
*   Who owns the nodes?
    
*   Will millions of Python objects create excessive overhead?
    
*   Should the logical links be represented using arrays or indexes instead?
    
*   Would a dictionary plus doubly linked list be more suitable?
    

The best data structure is not the one with the coolest diagram.

It is the one matching the actual workload.

* * *

# 📌 Linked List Quick Cheat Sheet

## Node

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

## Prepend

```python
new_node.next = head
head = new_node
```

Time:

```text
O(1)
```

## Append with Tail

```python
tail.next = new_node
tail = new_node
```

Time:

```text
O(1)
```

## Search

```python
while current is not None:
    if current.value == target:
        return True

    current = current.next
```

Time:

```text
O(n)
```

## Reverse

```python
previous = None
current = head

while current is not None:
    next_node = current.next
    current.next = previous
    previous = current
    current = next_node

head = previous
```

Time:

```text
O(n)
```

Space:

```text
O(1)
```

## Find the Middle

```python
slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
```

## Cycle Detection

```python
if slow is fast:
    cycle_exists = True
```

## Singly Linked List

```text
Data + Next
```

## Doubly Linked List

```text
Previous + Data + Next
```

## Circular Linked List

```text
Tail.next = Head
```

## Golden Rule

> Linked lists provide flexible relationships, not magical performance.

* * *

# 🎯 Final Thoughts

A linked list begins with a simple picture:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/5a03016e-4761-4de0-884f-040335b143a5.png align="center")

But it teaches several deep computer-science ideas:

*   References
    
*   Object identity
    
*   Dynamic memory
    
*   Traversal
    
*   Time complexity
    
*   Two-pointer algorithms
    
*   Cycles
    
*   Data-structure trade-offs
    
*   Cache locality
    
*   Composite architecture
    

In the age of AI, linked lists are not the default structure for tensors, embeddings, or model weights.

Arrays and specialized numerical structures dominate those workloads.

But linked ideas still appear in:

*   Agent workflows
    
*   Version histories
    
*   LRU caches
    
*   Graph representations
    
*   Event pipelines
    
*   Memory managers
    
*   Dynamic execution chains
    
*   AI-serving infrastructure
    

Most importantly, linked lists teach us to ask:

> What operations must this system perform most frequently?

If the answer is:

> “Jump directly to item 900,000,”

choose an array.

If the answer is:

> “Insert and remove items around known locations while preserving relationships,”

a linked structure may be exactly right.

So the next time someone says:

> “Linked-list insertion is always `O(1)`,”

politely ask:

> “Do we already have the node, or are we travelling through the entire list like a courier without Google Maps?” 😄

Good data-structure decisions are not made by memorizing one complexity value.

They are made by understanding the complete operation, the memory layout, and the real workload.

In AI engineering, that difference can determine whether a system is elegant and scalable—or simply a chain of objects pointing toward production chaos. 🤖🔗🚀

* * *

# 🌐 Let’s Connect

Whether you are learning data structures, building AI systems, preparing for interviews, or trying to understand why your linked list entered an infinite loop, I am always happy to connect.

Let us continue building AI systems that are not only intelligent, but also supported by strong computer-science foundations.

**LinkedIn:** Connect with me for AI, AWS, cloud engineering, Python, and software-development content.  
**hardeepjethwani@LinkedIn**

**TopMate:** Looking for guidance, brainstorming, or a technical discussion over a virtual coffee?  
**hardeepjethwani@TopMate**

**Instagram:** Follow my learning journey, technology experiments, and behind-the-scenes builder content.  
**hardeepjethwani@Instagram**

**X:** Join the conversation around AI, cloud, Python, data structures, and developer humour.  
**hardeepjethwani@X**

Want to support my AI, cloud, and educational adventures? Feel free to buy me a virtual coffee.

After all, coffee is basically a circular linked list:

![](https://cdn.hashnode.com/uploads/covers/606357ed26d9c50a54babbdb/370332ce-590b-4931-8afe-e28bded416b2.png align="center")

There is no `None` at the end. ☕😂

* * *

#LinkedList #DataStructures #DSA #Python #ArtificialIntelligence #AIEngineering #Algorithms #TimeComplexity #SpaceComplexity #SinglyLinkedList #DoublyLinkedList #PythonProgramming #MachineLearning #GenerativeAI #SoftwareEngineering #ComputerScience #Coding #Programming #TechEducation #DeveloperCommunity #BeginnerFriendly #InterviewPreparation