> For the complete Mojo documentation index, see [llms.txt](/llms.txt).
> Markdown versions of all pages are available by appending .md to any URL (e.g. /docs/manual/basics.md).

# 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`:

```mojo
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:

```mojo
struct Node[ElementType: ImplicitlyCopyable & Writable](https://mojolang.org/docs/manual/structs/Movable.md):
    comptime NodePointer = UnsafePointer[Self, MutExternalOrigin]

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

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

The code defines a type-specific `NodePointer` type alias built on
[`UnsafePointer`](/docs/std/memory/unsafe_pointer/UnsafePointer/).

[`MutExternalOrigin`](/docs/manual/values/lifetimes/)
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 `next` field is an `Optional[Self.NodePointer]` because a node may or may
not link to another node. `UnsafePointer` is non-nullable, so `Optional`
provides the null state. `Optional[UnsafePointer]` has the same memory layout as
a raw pointer, so there's no overhead. For more on this pattern, see
[Working with nullability](/docs/manual/pointers/unsafe-pointers/#working-with-nullability).

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.
1. Construct a value-holding node.
1. Move it into the allocated memory.
1. Return the pointer.

And here's an example of that pattern:

```mojo
@staticmethod
def make_node(value: Self.ElementType) -> Self.NodePointer:
    var node_ptr = alloc[Self](https://mojolang.org/docs/manual/structs/1.md)
    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 point at 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.

```mojo
def append(mut self, value: Self.ElementType):
    # Free chain if replacing `next`
    if self.next:
        var next_ptr = self.next.value()
        next_ptr[].free_chain()
        next_ptr.destroy_pointee()
        next_ptr.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:

```mojo
@staticmethod
def print_list(node: Optional[Self.NodePointer]):
    if not node:
        print("Empty list")
        return

    var node_ptr = node.value()

    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.

:::note
This example uses a static method, but you can also implement
it as an instance method.
:::

## 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:

```mojo
def free_chain(self):
    var current = self.next
    while current:
        var current_ptr = current.value()
        next_node = current_ptr[].next
        current_ptr.destroy_pointee()
        current_ptr.free()
        current = next_node
```

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

```mojo
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](/docs/manual/lifecycle/death/).

Here's a small example that shows how to deinitialize `self`:

```mojo
struct LinkedList[T]:
    var _head: Optional[Self._NodePointer]

    def __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.value()[].next
            curr.value().destroy_pointee()
            curr.value().free()
            curr = next
```

<!-- markdownlint-disable MD033 -->

:::info Putting it together

### View full sample code

```mojo
from std.os import abort
comptime Element = String # Adapt for your type
comptime ListNode = Node[Element] # Constructing a LinkedList
struct Node[ElementType: ImplicitlyCopyable & Writable](https://mojolang.org/docs/manual/structs/Movable.md):
comptime NodePointer = UnsafePointer[Self, MutExternalOrigin]
var value: Optional[Self.ElementType] # The `Node`'s value
var next: Optional[Self.NodePointer] # Pointer to the next `Node`
# Uses an `Optional` value to allow 'empty' Node construction
# that can be moved into newly allocated memory
def __init__(out self, value: Optional[Self.ElementType] = None):
self.value = value
self.next = {}
# Constructs a `Node` with a `value` with heap allocation and
# returns a pointer to the new `Node`.
@staticmethod
def make_node(value: Self.ElementType) -> Self.NodePointer:
var node_ptr = alloc[Self](https://mojolang.org/docs/manual/structs/1.md)
node_ptr.init_pointee_move(Self(value))
return node_ptr
# Constructs a `Node` with allocated memory, assigns a value, appends
# the pointer to `self.next`. Replaces any existing `next`.
def append(mut self, value: Self.ElementType):
# Free chain if replacing `next`
if self.next:
var next_ptr = self.next.value()
next_ptr[].free_chain()
next_ptr.destroy_pointee()
next_ptr.free()
self.next = Self.make_node(value)
# Prints the list starting at this pointer's pointee
@staticmethod
def print_list(node: Optional[Self.NodePointer]):
if not node:
print("Empty list")
return
var node_ptr = node.value()
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()
# Releases all successively allocated `Node` pointees. Does not release self
def free_chain(self):
var current = self.next
while current:
var current_ptr = current.value()
next_node = current_ptr[].next
current_ptr.destroy_pointee()
current_ptr.free()
current = next_node
def main():
var values: List[Element] = ["one", "one", "two", "three", "five", "eight"]
var list_head = ListNode.make_node(values[0])
var current = list_head
for idx in range(1, len(values), 1):
current[].append(values[idx])
current = current[].next.value()
ListNode.print_list(list_head)
# Demonstrates cleanup. In short-lived programs, the OS reclaims memory
# at exit
list_head[].free_chain()
list_head.destroy_pointee()
list_head.free()
```
Output:
```output
one one two three five eight
```
:::

<!-- markdownlint-enable MD033 -->

## What next?

- Learn more about **pointers and memory safety** in Mojo's
  [UnsafePointer](/docs/std/memory/unsafe_pointer/UnsafePointer/)
  and [lifetime and origin rules](/docs/manual/values/lifetimes/) guides.
- Learn more about how to **manage cleanup** in the Mojo
  [destructor](/docs/manual/lifecycle/death/) documentation.
- Learn more about
  [generic structures with traits](/docs/manual/traits/#generic-structs-with-traits)
  and how they let you build **reusable node and list types**.