A basic linked list implementation that doesn't allocate nodes individually.

linked_list_example.odin

/*
        A simple example of a linked list implementation that does NOT allocate the nodes individually.
        Written by TetraluxOnPC, 2024-07-28.
*/

package linked_list_example

import "core:mem"
import "core:mem/virtual"       
import "core:fmt"
import "core:math/rand"

List :: struct {
        head, tail, freelist: ^Node,
        len: int,
        arena: mem.Arena,
}

list_init :: proc(list: ^List, backing: []byte) {
        list^ = {}
        mem.arena_init(&list.arena, backing)
}

Node :: struct {
        value: int,
        next: ^Node,
}

make_node :: proc(list: ^List) -> ^Node {
        ally := mem.arena_allocator(&list.arena)
        return new(Node, ally)
}

push_front :: proc(list: ^List, item: int) {
        new_node := list.freelist
        if new_node == nil {
                new_node = make_node(list)
        } else {
                list.freelist = new_node.next
        }
        assert(new_node != nil, "OOM")

        new_node.value = item
        new_node.next = list.head
        list.head = new_node
        list.len += 1
}

pop_front :: proc(list: ^List) -> (item: int, ok: bool) {
        if list.head == nil { 
                return 0, false
        }

        front_node := list.head
        list.head = front_node.next
        front_node.next = list.freelist
        list.freelist = front_node
        list.len -= 1
        return front_node.value, true
}

list_print :: proc(list: ^List) {
        fmt.print("[")
        i := 0
        first := list.head
        for n := list.head; n != nil; n = n.next {
                defer i += 1
                if i > 0 && n == first {
                        fmt.print(" <LOOP>")
                        break
                }

                if i > 0 {
                        fmt.print(", ")
                }
                fmt.print(n.value)
        }
        fmt.println("]")
}

main :: proc() {
        track: mem.Tracking_Allocator
        mem.tracking_allocator_init(&track, context.allocator)
        context.allocator = mem.tracking_allocator(&track)
        defer {
                if len(track.allocation_map) > 0 {
                        fmt.eprintfln("\n\n%v memory leaks:", len(track.allocation_map))
                        for _, entry in track.allocation_map {
                                fmt.eprintfln("- %v: %vB", entry.location, entry.size)
                        }
                }
                if len(track.bad_free_array) > 0 {
                        fmt.eprintfln("\n\n%v bad frees:", len(track.bad_free_array))
                        for entry in track.bad_free_array {
                                fmt.eprintfln("- %v: %p", entry.location, entry.memory)
                        }
                }
        }

        backing := make([]byte, 64*mem.Megabyte)
        defer delete(backing) // NOTE: try commenting this out

        rand.reset(6) // NOTE: nice short output

        list: List
        list_init(&list, backing)

        list_print(&list)

        x := 10
        for i in 0..<10 {
                push_front(&list, x)
                x += 10
        }


        y := 500
        for list.len > 0 {
                list_print(&list)
                r := rand.uint32()
                if r % 2 == 0 {
                        item, has_item := pop_front(&list)
                        if !has_item { break }
                        fmt.print("-")
                } else {
                        push_front(&list, y)
                        fmt.print("+")
                        y += 10
                }
        }

}