Simple Linked List in Cairo: Complete Solution & Deep Dive Guide

---

The Ultimate Guide to Implementing Linked Lists in Cairo

A Simple Linked List is a foundational data structure in computer science. This guide provides a comprehensive walkthrough for implementing one in Cairo, covering everything from core concepts and memory management with Option and Box to creating a fully functional, generic, and reversible list from scratch.

---

You've been tasked with a fascinating project: prototyping a new music player application. The core of this prototype is the playlist feature. Users need to add songs, see them in order, and, most importantly, be able to reverse the playlist to listen in the opposite sequence. For this prototype, each song is simply represented by a unique number (an ID).

Your first thought might be to use an array or a vector. But what happens when the playlist grows indefinitely? Reallocating arrays can be inefficient. This is where a more dynamic, flexible data structure shines. You need something that can grow and shrink with ease, one element at a time. This is the perfect problem to solve with a Linked List, a cornerstone of computer science, especially in a systems-level language like Cairo.

This guide will take you from the basic theory of linked lists to a deep, line-by-line implementation in Cairo. You'll not only build a working playlist but also gain a profound understanding of Cairo's memory model, generics, and traits in a practical, real-world context drawn from the exclusive kodikra.com Cairo learning path.

---

What Exactly Is a Linked List?

At its core, a linked list is a linear data structure, but unlike an array, its elements are not stored at contiguous memory locations. Instead, each element, called a Node, is a separate object that contains two key pieces of information: the actual data and a reference (or "pointer") to the next node in the sequence.

Imagine a scavenger hunt. Each clue (a Node) contains a piece of the puzzle (the data) and tells you exactly where to find the next clue (the next pointer). The list begins at a starting point called the Head, and the last clue points to nowhere (None or null), signaling the end of the hunt.

This structure allows for efficient insertions and deletions from the beginning of the list, as you only need to change a couple of pointers, rather than shifting all subsequent elements as you would in an array.

Anatomy of a Linked List

• Node: The basic building block. It's a container holding the data and a pointer to the subsequent node.
• Data: The value stored within a node. In our music player example, this would be the song ID.
• Next Pointer: The reference within a node that points to the next node in the list. The final node's pointer is typically null (or None in Cairo/Rust).
• Head: A pointer that always points to the very first node in the linked list. It's the entry point to the entire structure.

  ● Head
  │
  ▼
┌───────────┐     ┌───────────┐     ┌───────────┐
│ Data: 101 │────→│ Data: 102 │────→│ Data: 103 │────→ None
│ Next:  ───┘     │ Next:  ───┘     │ Next:  ───┘
└───────────┘     └───────────┘     └───────────┘
   Node 1            Node 2            Node 3        (End of List)

---

Why Use a Linked List in Cairo?

Cairo is a language designed for performance, verifiability, and safety, particularly within the StarkNet ecosystem. Its memory model, inspired by Rust, emphasizes explicit ownership and control. This makes the linked list a particularly instructive and useful data structure to implement.

Key Advantages in the Cairo Context

• Dynamic Size: Playlists, transaction queues, or event logs can grow unpredictably. A linked list handles this gracefully without the overhead of reallocating and copying large, contiguous blocks of memory.
• Efficient Insertions/Deletions: Adding or removing a song from the beginning of our playlist (a push or pop operation) is extremely fast. It's an O(1) constant time operation, as it only involves redirecting the head pointer.
• Understanding Memory Management: Implementing a linked list forces you to engage directly with Cairo's concepts of ownership, heap allocation (via Box), and nullability (via Option). This is a fantastic practical exercise for mastering core language features.
• Foundation for Advanced Structures: Linked lists are the building blocks for more complex data structures like stacks, queues, and even graphs. Mastering them is a prerequisite for advanced computer science topics.

When to Choose a Linked List vs. an Array (Array)

Choosing the right data structure is critical for performance. Here’s a quick comparison to help you decide.

Feature	Simple Linked List	Array / Vec
Memory Allocation	Nodes stored non-contiguously on the heap.	Elements stored in a single, contiguous block of memory.
Size	Dynamic. Grows and shrinks one node at a time.	Fixed size, or dynamic with potentially costly reallocations.
Insertion/Deletion (at Head)	O(1) - Extremely fast.	O(n) - Slow, requires shifting all other elements.
Insertion/Deletion (at End)	O(n) - Requires traversing the whole list.	O(1) - Amortized constant time for dynamic arrays (Vec).
Element Access (by index)	O(n) - Slow, must traverse from the head.	O(1) - Extremely fast direct access.
Use Case Fit	Stacks, Queues, dynamic lists with frequent head operations.	Frequent random access, stable collections, lookup tables.

---

How to Implement a Simple Linked List in Cairo

Now, let's dive into the code. We'll build our SimpleLinkedList step-by-step, explaining each component and the reasoning behind the design choices. This implementation is part of an exclusive module from the kodikra Cairo curriculum.

Step 1: Defining the Core Data Structures

First, we need to define the two main structs: the Node that holds the data and the SimpleLinkedList that manages the whole structure.

#[derive(Drop, Copy)]
pub struct SimpleLinkedList {
    head: List,
    len: usize,
}

type List = Option>>;

struct Node {
    data: T,
    next: List,
}

// Trait implementations for Node to allow Drop and Copy
impl NodeDrop> of Drop>;
impl NodeCopy> of Copy>;

Code Walkthrough:

• struct Node: This is our fundamental building block.
  • data: T: A generic field to hold any type of data (like our song ID `u32`, or a more complex struct). The T makes our list versatile.
  • next: List: This is the crucial pointer to the next node. Let's break down its type, List.
• type List = Option<Box<Node<T>>>;: This type alias is the secret sauce.
  • Node<T>: We have a recursive type definition: a Node contains another Node. If we just wrote next: Node, the compiler would complain about an infinitely sized type.
  • Box<Node<T>>: To solve this, we use a Box. A Box is a smart pointer that allocates memory for the Node on the heap instead of the stack. The Box itself has a known, fixed size (it's just a pointer), breaking the recursive size calculation.
  • Option<...>: A linked list must have an end. The Option enum is perfect for this. It can either be Some(value), containing our boxed node, or None, signifying the end of the list. This is Cairo's safe way of handling nullability.
• pub struct SimpleLinkedList: This is the public-facing struct that users will interact with.
  • head: List: An Option that holds the first node of the list. If it's None, the list is empty.
  • len: usize: A counter to keep track of the number of elements, allowing for an efficient O(1) length check.
• #[derive(Drop, Copy)] and impl...: These lines add necessary trait implementations. Drop ensures memory is cleaned up properly when a list or node goes out of scope, and Copy is often required for passing values. We constrain our generic type T to also implement these traits.

Step 2: Implementing the Core Functionality

We'll create an implementation block using Cairo's trait generation feature. This keeps the interface clean and separates it from the struct definition.

#[generate_trait]
pub impl SimpleLinkedListImpl, +Copy> of SimpleLinkedListTrait {
    // ... methods go here ...
}

Constructor and Basic Info Methods

Every data structure needs a way to be created and to provide basic information about its state.

    fn new() -> SimpleLinkedList {
        SimpleLinkedList { head: Option::None, len: 0 }
    }

    fn is_empty(self: @SimpleLinkedList) -> bool {
        self.len == 0
    }

    fn len(self: @SimpleLinkedList) -> usize {
        self.len
    }

    fn peek(self: @SimpleLinkedList) -> Option {
        match self.head {
            Option::Some(node) => Option::Some(node.data),
            Option::None => Option::None,
        }
    }

Code Walkthrough:

• fn new(): The constructor. It returns a new SimpleLinkedList instance. The head is initialized to None (an empty list) and the len is 0. Simple and effective.
• fn is_empty(): Checks if the list is empty. Instead of checking self.head.is_none(), we can simply check if self.len == 0, which is a slightly more direct O(1) operation.
• fn len(): Returns the stored length of the list. This is why we keep a len counter—to avoid traversing the entire list (an O(n) operation) just to count the elements.
• fn peek(): Allows us to look at the data of the first element without removing it. It returns an Option because the list might be empty. We use a match statement to safely access the data from the head node if it exists (Some), otherwise we return None.

Adding and Removing Elements (Push & Pop)

These are the most common operations for a stack-like linked list. We'll be adding to and removing from the front (the head) of the list.

    fn push(ref self: SimpleLinkedList, element: T) {
        let old_head = self.head.take();
        let new_node = Box(Node { data: element, next: old_head });
        self.head = Option::Some(new_node);
        self.len += 1;
    }

    fn pop(ref self: SimpleLinkedList) -> Option {
        let old_head = self.head.take();
        match old_head {
            Option::Some(mut node) => {
                self.head = node.next.take();
                self.len -= 1;
                Option::Some(node.data)
            },
            Option::None => Option::None,
        }
    }

Code Walkthrough:

• fn push(ref self: ..., element: T): Adds a new element to the front of the list.
  1. let old_head = self.head.take();: The Option::take() method is brilliant. It moves the value out of the Option, leaving None in its place. This effectively disconnects the old head from the list while giving us ownership of it.
  2. let new_node = Box(Node { ... });: We create a new Node on the heap. Its data is the new element, and its next pointer is set to the old_head we just took. The new node now points to the rest of the list.
  3. self.head = Option::Some(new_node);: We update the list's head to be our newly created node.
  4. self.len += 1;: We increment the length counter.
• fn pop(ref self: ...) -> Option<T>: Removes the front element and returns its data.
  1. let old_head = self.head.take();: Again, we use take() to remove the head node from the list and take ownership of it.
  2. match old_head { ... }: We check if there was a head to take.
  3. If Some(mut node):
     • self.head = node.next.take();: The crucial step. We set the list's new head to be the next node of the one we just removed. We use take() again to move the pointer.
     • self.len -= 1;: Decrement the length.
     • Option::Some(node.data): We return the data from the removed node. The node itself, now un-owned, will be dropped and its memory deallocated.
  4. If None: The list was empty, so we just return None.

Step 3: The Reversal Logic

This is the core requirement for our music player—reversing the playlist. The standard algorithm involves iterating through the list and reversing the `next` pointers of each node as we go.

    fn rev(self: SimpleLinkedList) -> SimpleLinkedList {
        let mut new_list = SimpleLinkedListImpl::new();
        let mut current_head = self.head;

        while let Option::Some(mut node) = current_head {
            current_head = node.next.take();
            new_list.push(node.data);
        }

        new_list
    }

Code Walkthrough:

This implementation is clever and safe. Instead of manually juggling pointers, it leverages the `push` method we've already built.

1. let mut new_list = SimpleLinkedListImpl::new();: We create a new, empty list that will become our reversed list.
2. let mut current_head = self.head;: We take ownership of the original list's head. Note that `self` is consumed by this method, so the original list is no longer valid after `rev` is called.
3. while let Option::Some(mut node) = current_head: This is a powerful loop construct. It continues as long as `current_head` is `Some`. In each iteration, it unwraps the node and gives us ownership of it.
4. current_head = node.next.take();: We advance our position in the original list. We move the `next` pointer out of the current node, making it the new `current_head` for the next iteration.
5. new_list.push(node.data);: This is the key. We take the data from the current node of the old list and `push` it onto the front of our `new_list`. The first node of the old list becomes the last element of the new one, the second node becomes the second-to-last, and so on. This naturally reverses the order.
6. new_list: Finally, we return the fully reversed `new_list`.

This process is visually represented below:

Original List: Head → [1] → [2] → [3] → None

 ● Start Reversal
 │
 ▼
┌──────────────────────────┐
│ Create empty `new_list`  │
│ new_list: Head → None    │
└──────────┬───────────────┘
           │
           ▼
┌──────────────────────────┐
│ Loop 1: Pop [1] from old │
│ Push 1 onto new_list     │
│ new_list: Head → [1]     │
└──────────┬───────────────┘
           │
           ▼
┌──────────────────────────┐
│ Loop 2: Pop [2] from old │
│ Push 2 onto new_list     │
│ new_list: Head → [2]→[1] │
└──────────┬───────────────┘
           │
           ▼
┌──────────────────────────┐
│ Loop 3: Pop [3] from old │
│ Push 3 onto new_list     │
│ new_list: Head → [3]→[2]→[1] │
└──────────┬───────────────┘
           │
           ▼
    ● End Reversal
      Return new_list

Step 4: Utility Conversions

For convenience, it's helpful to have methods to create a list from a standard `Array` and to convert our list back into one.

    fn from_array(mut arr: Array) -> SimpleLinkedList {
        let mut list = SimpleLinkedListImpl::new();
        loop {
            match arr.pop_front() {
                Option::Some(element) => list.push(element),
                Option::None => break,
            }
        }
        list
    }

    fn into_array(self: SimpleLinkedList) -> Array {
        let mut arr = array
![];
        let mut list = self;
        loop {
            match list.pop()
 {
                Option::Some(element) => arr.append(element),
                Option::None => break,
            }
        }
        arr.reverse();
        arr
    }

Code Walkthrough:

• fn from_array(...): This function consumes an `Array` and builds a linked list. It repeatedly calls `pop_front` on the array and `push` on the list. Pushing to the front of the list while taking from the front of the array preserves the original order.
• fn into_array(...): This function consumes our list and returns an `Array`. It repeatedly `pop`s elements from the list and `append`s them to the array. Since `pop` takes from the front, the resulting array will be in reverse order. Therefore, a final `arr.reverse()` is needed to restore the original sequence.

---

FAQ: Simple Linked List in Cairo

Why is Option<Box<Node<T>>> necessary for the 'next' pointer?

This type signature solves two fundamental problems. First, Box<T> allocates the next node on the heap, giving it a fixed-size pointer on the stack and preventing an infinite-size compiler error for the recursive struct. Second, Option<T> provides a safe way to represent the end of the list (with None) without resorting to null pointers, which are a common source of bugs.

What is the difference between a singly and a doubly linked list?

A singly linked list, which we implemented here, has nodes that only point forward to the next node. A doubly linked list has nodes that point both forward (to next) and backward (to a previous node). This allows for efficient traversal in both directions but requires more memory per node and more complex logic for insertions and deletions.

Is a linked list in Cairo efficient?

It depends on the use case. For operations at the head of the list (like push and pop), it is extremely efficient with O(1) time complexity. However, for accessing an element by index (e.g., getting the 100th song), it is inefficient (O(n)) because you must traverse the list from the beginning. For such scenarios, an Array is a better choice.

How does Cairo's ownership model affect this implementation?

Cairo's ownership model ensures memory safety. Methods like take() are crucial because they allow us to safely move ownership of a node out of an Option. The compiler enforces rules that prevent issues like using a node after it has been moved or having multiple owners of the same mutable data, which are common pitfalls when implementing linked lists in languages like C++.

Can I store complex data types, like structs, in this SimpleLinkedList<T>?

Absolutely. The T in SimpleLinkedList is generic. As long as your custom struct implements the required traits (like Drop and Copy, as specified in our implementation), you can store it in the list. For example, you could define a Song struct with `id`, `title`, and `artist` fields and create a SimpleLinkedList<Song>.

What is the time complexity of the rev() method?

The rev() method has a time complexity of O(n), where n is the number of elements in the list. This is because it must visit every single node in the original list once to `push` its data onto the new list. The space complexity is also O(n) because it creates a completely new list to store the reversed elements.

---

Conclusion: From Playlist to Proficiency

You have successfully built a fully functional, generic, and reversible singly linked list in Cairo. This journey, inspired by the practical challenge of a music playlist from the kodikra.com curriculum, has taken us through some of Cairo's most important concepts: generics, traits, heap allocation with Box, safe nullability with Option, and the powerful ownership model.

The linked list is more than just an academic exercise; it's a practical tool for managing dynamic data efficiently. Understanding its trade-offs against arrays is fundamental to writing high-performance code. The patterns you've learned here—especially the use of take() and the `while let` loop—are idiomatic in modern systems programming and will serve you well in more complex projects.

Disclaimer: The code and concepts in this article are based on Cairo version 2.6.3. As Cairo is a rapidly evolving language, syntax and features may change in future versions. Always consult the official documentation for the latest updates.

Ready to tackle the next challenge? Explore more advanced data structures and Cairo concepts in our comprehensive Cairo Learning Roadmap, or deepen your foundational knowledge with our complete Cairo language guide.

---

Published by Kodikra — Your trusted Cairo learning resource.