Linked List in Cairo: Complete Solution & Deep Dive Guide

---

Mastering Doubly Linked Lists in Cairo: A Deep Dive Guide

A Doubly Linked List in Cairo is a powerful, dynamic data structure composed of nodes, each holding data and two pointers: one to the next node and one to the previous. This implementation leverages a Felt252Dict for efficient, non-contiguous memory management, ideal for on-chain StarkNet applications.

You're building a groundbreaking application on StarkNet, perhaps a complex DeFi protocol or a dynamic NFT project. You need to manage a collection of items that grows and shrinks frequently. An array seems simple, but every time you add or remove an item from the beginning, you face a gas-intensive operation that shifts every single element. You feel the sting of inefficiency, knowing there has to be a better, more gas-friendly way. This is where the elegance of a Doubly Linked List shines, and mastering its implementation in Cairo is a game-changer for any serious StarkNet developer.

This comprehensive guide, part of the exclusive kodikra.com learning path, will take you from zero to hero. We'll deconstruct a robust Doubly Linked List implementation in Cairo, exploring not just the 'how' but the critical 'why' behind its design. You will learn to build a flexible and efficient data structure perfect for the demands of decentralized applications.

---

What Exactly is a Doubly Linked List?

Before diving into the Cairo code, let's solidify the core concept. Imagine a train. Each carriage is a node in our list. The content inside the carriage—passengers, cargo, or in our case, a station number—is the data.

In a simple "singly" linked list, each carriage only has a coupling to the one in front of it (a next pointer). You can easily walk from the engine to the caboose. But what if you're in the last carriage and want to go back to the engine? You can't. You're stuck moving in one direction.

A Doubly Linked List solves this. Each carriage has two couplings: one connecting to the carriage in front (the next pointer) and another connecting to the one behind (the previous pointer). This bidirectional link is the superpower of this data structure. It allows you to traverse the list forward and backward with equal ease.

This structure consists of:

• Nodes: The fundamental building blocks. Each node contains the actual data (e.g., a station ID) and two pointers.
• `next` Pointer: An address or index pointing to the subsequent node in the sequence.
• `previous` Pointer: An address or index pointing to the preceding node.
• Head: A special pointer that marks the very first node of the list.
• Tail: A special pointer that marks the very last node of the list.

This design makes adding or removing nodes at either the beginning (head) or the end (tail) incredibly efficient, a concept we will see is vital for gas optimization in Cairo.

  Head Pointer
      │
      ▼
┌────────────┐     next     ┌────────────┐     next     ┌────────────┐
│ Node 1     ├─────────────►│ Node 2     ├─────────────►│ Node 3     │
│ Data: 10   │              │ Data: 20   │              │ Data: 30   │
│ Prev: None │◄─────────────┤ Prev: Node 1 │◄─────────────┤ Prev: Node 2 │
└────────────┘    previous  └────────────┘    previous  └────────────┘
                                                                 ▲
                                                                 │
                                                            Tail Pointer

---

Why Use a Doubly Linked List in Cairo?

In a general programming context, linked lists are chosen for their dynamic size and efficient insertions/deletions. In the world of Cairo and StarkNet, these benefits are amplified due to the nature of the blockchain environment, where computational cost (gas) is a primary concern.

The Gas Efficiency Advantage

The most significant advantage is the O(1) time complexity for adding or removing elements at the ends. Let's break this down:

• Push (Add to End): To add a new station to the end of the route, you simply create a new node, point the old tail's next to it, point the new node's previous to the old tail, and update the list's tail pointer to the new node. The number of existing stations doesn't matter. The cost is constant.
• Pop (Remove from End): To remove the last station, you just update the tail pointer to the second-to-last node and set its next pointer to null. Again, a constant-time operation.
• Unshift (Add to Start): Similar to `push`, but at the head. Constant time.
• Shift (Remove from Start): Similar to `pop`, but at the head. Constant time.

Contrast this with a dynamic array (like a Span<T> in Cairo). Adding an element to the beginning requires shifting every single existing element one position over. This is an O(n) operation, where 'n' is the number of elements. On a blockchain, an O(n) operation can become prohibitively expensive as the list grows.

The `Felt252Dict` Backbone: A Cairo-Specific Design

Traditional languages like C++ or Rust implement linked lists with direct memory pointers. Cairo, running on the Cairo VM, has a different memory model. We can't just get a raw memory address. Instead, the canonical way to implement such structures is by using a dictionary or hash map, specifically Felt252Dict<V>.

In our implementation, we don't store nodes in contiguous memory. We store them in a dictionary where the key is a unique felt252 index and the value is the Node itself. The next and previous "pointers" are not memory addresses but simply the felt252 keys of the corresponding nodes in the dictionary. This provides the flexibility of non-contiguous storage, which is perfectly suited for the Cairo VM.

---

How to Implement a Doubly Linked List in Cairo: A Code Walkthrough

Let's dissect the complete implementation from the kodikra.com module. We'll analyze the data structures, the core logic, and each function's role in managing our train route.

The Core Data Structures

Everything starts with defining the `Node` and the `DoublyLinkedList` itself.

use core::dict::Felt252Dict;

// A type alias for clarity. `Option` makes our pointers nullable.
type Index = Option<felt252>;

#[derive(Drop, Copy)]
struct Node<T> {
    station: T,
    next: Index,
    previous: Index,
}

struct DoublyLinkedList<T> {
    dict: Felt252Dict<Nullable<Node<T>>>,
    head: Index,
    tail: Index,
    len: usize,
    next_index: felt252,
}

Dissecting the `Node<T>` Struct

• #[derive(Drop, Copy)]: These traits are important. Drop ensures memory is handled correctly when a node is no longer needed. Copy allows us to pass nodes by value easily, which is idiomatic for simple structs in Cairo.
• station: T: This is the generic data payload. By using T, our linked list can hold any type of data, not just station numbers.
• next: Index and previous: Index: These are our "pointers." We use the type alias Index, which is an Option<felt252>. The Option enum is crucial here; it can either be Some(key), where key is the felt252 index of the next/previous node in our dictionary, or None, indicating the end of the list (e.g., the head's previous is None).

Dissecting the `DoublyLinkedList<T>` Struct

• dict: Felt252Dict<Nullable<Node<T>>>: This is the heart of our storage. It's a dictionary mapping a felt252 key to a Nullable<Node<T>>. We use Nullable to allow for efficient removal of nodes without immediately resizing the dictionary.
• head: Index: An Option<felt252> that holds the key of the first node in the list. It's None if the list is empty.
• tail: Index: An Option<felt252> that holds the key of the last node in the list. It's None if the list is empty.
• len: usize: A simple counter to keep track of the number of nodes. This provides an O(1) way to get the list's length without traversing it.
• next_index: felt252: An auto-incrementing counter used to generate unique keys for new nodes. This prevents key collisions in our dictionary.

The Implementation Trait and Constructor

We define the behavior of our list inside an impl block. The first step is creating a constructor, the new() function.

impl DoublyLinkedListImpl<T, +Drop<T>> of DoublyLinkedListTrait<T> {
    fn new() -> DoublyLinkedList<T> {
        DoublyLinkedList {
            dict: Felt252Dict<Nullable<Node<T>>::new(),
            head: Option::None,
            tail: Option::None,
            len: 0,
            next_index: 0,
        }
    }
    // ... other functions
}

The new() function is straightforward. It initializes an empty DoublyLinkedList. The dictionary is new and empty, head and tail are set to None, length is 0, and our index counter starts at 0.

Adding to the End: The `push` method

The `push` operation adds a new station to the end of the route. This is one of the most common operations.

    fn push(ref self: DoublyLinkedList<T>, station: T) {
        // 1. Create the new node
        let new_node = Node { station, next: Option::None, previous: self.tail };
        let new_index = self.next_index;

        // 2. Insert the new node into the dictionary
        self.dict.insert(new_index, nullable::new(new_node));
        self.next_index += 1;
        self.len += 1;

        // 3. Update the old tail's `next` pointer
        match self.tail {
            Option::Some(tail_index) => {
                let mut tail_node = self.dict.get(tail_index).deref();
                tail_node.next = Option::Some(new_index);
                self.dict.insert(tail_index, nullable::new(tail_node));
            },
            Option::None => {
                // 4. If list was empty, head is also the new node
                self.head = Option::Some(new_index);
            }
        };

        // 5. Update the list's tail pointer
        self.tail = Option::Some(new_index);
    }

`push` Logic Explained:

1. Create Node: We instantiate a new Node. Its station is the data passed in. Its next is None because it will be the new last node. Its previous points to the current tail of the list.
2. Insert into Dictionary: We insert this new node into our dict using the current next_index as the key. We then increment next_index and len.
3. Update Old Tail: We use a match statement to check if the list was empty (self.tail is None). If it wasn't, we get the old tail node from the dictionary, update its next pointer to point to our new node's index, and write it back to the dictionary.
4. Handle Empty List: If the list was empty (the Option::None case), this new node is both the head and the tail. So, we set self.head to the new index.
5. Update List Tail: Finally, we update the list's main tail pointer to the index of the new node we just added.

This process is visually represented below.

    ● Start: Push(40)
    │
    ▼
  ┌──────────────────────────┐
  │ List: [10] <-> [20] <-> [30] │
  │ Head: 10, Tail: 30       │
  └───────────┬──────────────┘
              │
              ▼
  ┌──────────────────────────┐
  │ 1. Create New Node(40)   │
  │    - next: None          │
  │    - prev: 30 (old tail) │
  └───────────┬──────────────┘
              │
              ▼
  ┌──────────────────────────┐
  │ 2. Update Old Tail(30)   │
  │    - node(30).next = 40  │
  └───────────┬──────────────┘
              │
              ▼
  ┌──────────────────────────┐
  │ 3. Update List's Tail    │
  │    - list.tail = 40      │
  └───────────┬──────────────┘
              │
              ▼
    ● End: [10]<->[20]<->[30]<->[40]

Removing from the End: The `pop` method

The `pop` operation removes the last station and returns its value. It's the inverse of `push`.

    fn pop(ref self: DoublyLinkedList<T>) -> Option<T> {
        match self.tail {
            Option::None => Option::None, // List is empty
            Option::Some(tail_index) => {
                // 1. Get the node to be removed
                let tail_node_nullable = self.dict.get(tail_index);
                let tail_node = tail_node_nullable.deref();

                // 2. Update the list's tail to the previous node
                self.tail = tail_node.previous;

                // 3. Update the new tail's `next` pointer
                match self.tail {
                    Option::Some(new_tail_index) => {
                        let mut new_tail_node = self.dict.get(new_tail_index).deref();
                        new_tail_node.next = Option::None;
                        self.dict.insert(new_tail_index, nullable::new(new_tail_node));
                    },
                    Option::None => {
                        // 4. If list is now empty, update head too
                        self.head = Option::None;
                    }
                };

                // 5. Decrement length and return station data
                self.len -= 1;
                // Note: The node is left in the dictionary as a null value,
                // to be cleaned up later by `squash()`.
                self.dict.insert(tail_index, nullable::null());
                
                Option::Some(tail_node.station)
            }
        }
    }

`pop` Logic Explained:

1. Get Tail Node: We retrieve the current tail node from the dictionary using the tail_index.
2. Update List Tail: We update the list's tail pointer to point to the previous node (tail_node.previous). This node is about to become the new tail.
3. Update New Tail: We check if the list is now empty. If not, we fetch the new tail node, set its next pointer to None (as it's now the last element), and save it back.
4. Handle Now-Empty List: If updating the tail resulted in None, it means we just removed the last element. So, we must also set the head to None.
5. Finalize: We decrement the length. Instead of truly removing the node from the dictionary (which can be expensive), we insert a null() value at its key. This marks the slot for future cleanup. Finally, we return the station data wrapped in Some.

Operations at the Beginning: `unshift` and `shift`

The logic for unshift (add to start) and shift (remove from start) is perfectly symmetrical to push and pop. Instead of manipulating the tail and previous pointers, they manipulate the head and next pointers.

For instance, in unshift, a new node's previous is set to None, its next points to the old head, the old head's previous is updated to point to the new node, and the list's head pointer is updated.

---

When to Use (and Not Use) a Linked List in Cairo

Choosing the right data structure is critical for performance and gas cost. A Doubly Linked List is a specialized tool, not a universal solution. Here’s a comparison with a standard dynamic array (like Cairo's Array<T> or Span<T>) to help you decide.

Pros and Cons Analysis

Operation	Doubly Linked List (Our Impl)	Dynamic Array (e.g., `Array<T>`)	Winner
Add/Remove at End (Push/Pop)	O(1) - Constant time	O(1) - Amortized constant time	Tie
Add/Remove at Start (Unshift/Shift)	O(1) - Constant time	O(n) - Linear time (must shift all elements)	Linked List
Insertion/Deletion in Middle	O(1) if you have the node's index, O(n) to find it	O(n) - Linear time (must shift elements)	Linked List (if node is known)
Element Access by Index (e.g., get 5th element)	O(n) - Linear time (must traverse from head/tail)	O(1) - Constant time	Array
Memory Usage	Higher per-element overhead (data + 2 pointers)	Lower per-element overhead (just data)	Array
Memory Layout	Fragmented (nodes can be anywhere in the dictionary)	Contiguous (elements are stored side-by-side)	Depends on use case

The Verdict

• Choose a Doubly Linked List when: Your primary use case involves frequent additions or removals from both the beginning and the end of the collection. Think of implementing a queue (FIFO) or a deque (double-ended queue). This is where its O(1) performance shines and saves significant gas.
• Choose an Array when: You need fast, random access to elements by their index. If you are frequently doing things like `get_element_at(5)`, an array is vastly superior. It's also more memory-efficient if you don't need the flexibility of a linked list.

---

Frequently Asked Questions (FAQ)

What is the main advantage of a doubly linked list over a singly linked list?

The key advantage is bidirectional traversal. In a doubly linked list, you can move from any node to its previous node in constant time, O(1). This makes operations like removing the last element (pop) or inserting before a given node highly efficient. A singly linked list can only move forward, making such operations O(n) in complexity.

Why does this Cairo implementation use a Felt252Dict instead of direct pointers?

The Cairo VM has a unique memory model that doesn't expose raw memory addresses in the same way as systems languages like C or Rust. The Felt252Dict (a hash map) is the idiomatic and safe way to simulate pointer-like relationships. It allows for non-contiguous storage, where each node is a value in the dictionary, and its "pointers" (next/previous) are simply the keys to other nodes in the same dictionary.

Is a linked list efficient for random access (e.g., getting the 5th element)?

No, it is highly inefficient. To get the 5th element, you must start at the head and follow the next pointer four times. This is an O(n) operation, where 'n' is the index of the element you want. For frequent random access, an Array<T> is the correct data structure, as it provides O(1) access.

How is memory managed for removed nodes in this implementation?

When a node is "removed" via pop or shift, its entry in the Felt252Dict is replaced with a nullable::null() value rather than being deleted outright. This is a performance optimization. The memory isn't truly freed until the entire linked list goes out of scope and its destruct function is called, which in turn calls self.dict.squash() to clean up and reclaim the memory used by the dictionary.

Can a Cairo linked list store complex data types?

Yes. The implementation uses generics (<T>). This means T can be any type that conforms to the required traits (like Drop). You can store simple types like felt252 or complex custom structs, making the data structure very versatile.

What are some common pitfalls when working with linked lists?

The most common errors involve pointer management. Forgetting to update a next or previous pointer during an insertion or deletion can break the chain, leading to orphaned nodes or incorrect list state. For example, in a `pop` operation, forgetting to set the new tail's `next` pointer to `None` would be a critical bug. Careful, step-by-step logic and thorough testing are essential.

---

Conclusion: Your New Go-To Data Structure

You have now journeyed through one of the most fundamental and powerful data structures, reimagined for the Cairo ecosystem. The Doubly Linked List, backed by a Felt252Dict, is more than just an academic exercise; it's a practical, gas-efficient tool for managing dynamic, ordered data on-chain. Its O(1) performance for head/tail operations makes it an indispensable asset for building sophisticated queues, deques, and state management systems in your StarkNet contracts.

By understanding the trade-offs between linked lists and arrays, you are now better equipped to make informed architectural decisions that will define the performance and cost-effectiveness of your applications. This knowledge is a cornerstone of becoming a proficient Cairo developer.

To continue your journey, dive deeper into the Cairo programming language or explore the next module in our complete Cairo Learning Path to master even more advanced concepts and build the next generation of decentralized applications.

Disclaimer: All code is based on the current stable versions of Cairo. As the language evolves, syntax and best practices may change. Always refer to the official documentation for the latest updates.

---

Published by Kodikra — Your trusted Cairo learning resource.