Skip to main content

/

DocsCode

Self-referential structs

Some data structures don’t fit well with value semantics. Lists, trees, and graphs all need nodes that point to each other. You can’t build these by nesting one value inside another, because the type would keep growing forever.

In Mojo, you build these shapes with pointers, heap allocation, and manual cleanup. The idea may feel new at first, but the pattern stays simple once you see it in small steps.

Avoid direct self-reference​

Mojo won't let you build a type that stores another instance of itself, even when nested within an Optional:

struct Node:
    var value: String
    var next: Optional[Node]  # ERROR: Recursive reference

    # ...

Each struct has a fixed layout. If Node held another Node directly, the compiler wouldn’t know how much space to reserve. Optional fields don’t help, because the outer value still needs room for the inner one.

Pointers solve this problem. Pointers have a fixed size, and they let values point at each other without blowing up the type.

Adding self-referential pointers​

The following code shows how to set up a node that can point to its own type. This sample gives you a node type with a value slot and a single link to the next node:

struct Node[ElementType: ImplicitlyCopyable & Writable](Movable):
    comptime NodePointer = UnsafePointer[Self, MutOrigin.external]


    var value: Optional[Self.ElementType] # The `Node`'s value
    var next: Self.NodePointer # Pointer to the next `Node`


    # Uses an `Optional` value to allow 'empty' Node construction
    # that can be moved into newly allocated memory
    fn __init__(out self, value: Optional[Self.ElementType] = None):
        self.value = value
        self.next = Self.NodePointer()

The code defines a type-specific NodePointer type alias built on UnsafePointer. Add the comptime within the struct definition, as shown here. Including MutOrigin.external lets the pointer represent dynamically-allocated memory that won't be tracked by the lifetime checker. You'll need to both allocate and deallocate memory as needed.

The optional value lets you create "empty" nodes, enabling you to move new Node memory allocations into place.

Building nodes​

Here’s the key pattern you’ll use in many reference structures:

  1. Allocate space.
  2. Construct a value-holding node.
  3. Move it into the allocated memory.
  4. Return the pointer.

And here's an example of that pattern:

@staticmethod
fn make_node(value: Self.ElementType) -> Self.NodePointer:
    node_ptr = alloc[Self](1)
    node_ptr.init_pointee_move(Self(value))
    return node_ptr

This "allocate space, initialize, and move" approach creates safe pointer-based structures in Mojo.

Linking nodes​

To link nodes, create a new node and set your next pointer to it. This example shows how to append a new node using a supplied value. If a next node already exists, the code frees it before appending the new node.

fn append(mut self, value: Self.ElementType):
    # Free chain if replacing `next`
    if self.next:
        self.next[].free_chain()
        self.next.destroy_pointee()
        self.next.free()

    self.next = Self.make_node(value)

Walking the list​

To walk the list, follow the chain until you reach the end. Recursive code makes this easy to read. This example prints the value stored at each node:

@staticmethod
fn print_list(node_ptr: Self.NodePointer):
    if not node_ptr:
        print()
        return

    current_value: Optional[Self.ElementType] = node_ptr[].value
    if current_value:
        print(current_value.value(), end=" ")

    if node_ptr[].next:
        Self.print_list(node_ptr[].next)
    else:
        print()

The pattern is simple: check the value, print it if it exists, then move to the next link.

Cleaning up​

Because you allocate each node yourself, you’re also responsible for freeing it. This cleanup walks the chain and frees each node after destroying its pointee:

fn free_chain(self):
    current = self.next
    while current:
        next_node = current[].next
        current.destroy_pointee()
        current.free()
        current = next_node

The “head” node stays allocated unless you explicitly free it yourself:

list_head[].free_chain()
list_head.destroy_pointee()
list_head.free()

Destructors​

When you build real Mojo data structures, you usually want a safe API that hides raw pointers from users. In a complete linked-list type (rather than a small demo of linkable nodes) the parent list handles node allocation and freeing. Because it owns the nodes, it also performs cleanup in its destructor.

Here’s a small example based on the Mojo Standard Library that shows how to deinitialize self:

struct LinkedList[T]:
    var _head: Self._NodePointer

    fn __del__(deinit self):
        """Clean up the list by freeing all nodes.

        Notes:
            Time complexity: O(n) in len(self).

        See Also:
            "Choose the form of the Destructor!"
            -- Gozer, "Ghostbusters" (1984).
        """
        var curr = self._head
        while curr:
            var next = curr[].next
            curr.destroy_pointee()
            curr.free()
            curr = next

What next?​

Edit this page

Was this page helpful?

Models

Cookbook

Puzzles

Blog

Community

Contact