package core:container/intrusive/list

⌘K
Ctrl+K
or
/

    Overview

    An intrusive doubly-linked list.

    The intrusive container requires a Node to be embedded in your own structure, like this.

    Example:
    My_String :: struct {
    	node:  list.Node,
    	value: string,
    }
    

    Embedding the members of a list.Node in your structure with the using keyword is also allowed.

    Example:
    My_String :: struct {
    	using node: list.Node,
    	value: string,
    }
    

    Here is a full example.

    Example:
    package test
    
    import "core:fmt"
    import "core:container/intrusive/list"
    
    main :: proc() {
        l: list.List
    
        one := My_String{value="Hello"}
        two := My_String{value="World"}
    
        list.push_back(&l, &one.node)
        list.push_back(&l, &two.node)
    
        iter := list.iterator_head(l, My_String, "node")
        for s in list.iterate_next(&iter) {
            fmt.println(s.value)
        }
    }
    
    My_String :: struct {
        node:  list.Node,
        value: string,
    }
    
    Output:
    Hello
    World
    

    Index

    Types (3)
    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedure Groups (0)

    This section is empty.

    Types

    Iterator ¶

    Iterator :: struct($T: typeid) {
    	… // See source for fields
    }

    Related Procedures With Parameters

    List ¶

    List :: struct {
    	head: ^Node,
    	tail: ^Node,
    }
     

    An intrusive doubly-linked list

    As this is an intrusive container, a Node must be embedded in your own structure which is conventionally called a "link". The use of push_front and push_back take the address of this node. Retrieving the data associated with the node requires finding the relative offset of the node of the parent structure. The parent type and field name are given to iterator_* procedures, or to the built-in container_of procedure.

    This data structure is two-pointers in size:

    8 bytes on 32-bit platforms and 16 bytes on 64-bit platforms
    

    Related Procedures With Parameters

    Node ¶

    Node :: struct {
    	prev: ^Node,
    	next: ^Node,
    }
     

    The list link you must include in your own structure.

    Related Procedures With Parameters

    Related Procedures With Returns

    Constants

    This section is empty.

    Variables

    This section is empty.

    Procedures

    insert_after ¶

    insert_after :: proc "contextless" (list: ^List, node, after: ^Node) {…}
     

    Inserts a new element after another with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure
    • after: The node to insert behind, or nil to push to the front
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    insert_after_example :: proc() {
    	l: list.List
    
    	one   := My_Insert_After_Struct{value=1}
    	two   := My_Insert_After_Struct{value=2}
    	three := My_Insert_After_Struct{value=3}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &three.node)
    	list.insert_after(&l, &two.node, &one.node)
    
    	it := list.iterator_head(l, My_Insert_After_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Insert_After_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    

    insert_before ¶

    insert_before :: proc "contextless" (list: ^List, node, before: ^Node) {…}
     

    Inserts a new element before another with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure
    • before: The node to insert in front of, or nil to push to the back
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    insert_before_example :: proc() {
    	l: list.List
    
    	one   := My_Insert_Before_Struct{value=1}
    	two   := My_Insert_Before_Struct{value=2}
    	three := My_Insert_Before_Struct{value=3}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &three.node)
    	list.insert_before(&l, &two.node, &three.node)
    
    	it := list.iterator_head(l, My_Insert_Before_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Insert_Before_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    

    is_empty ¶

    is_empty :: proc "contextless" (list: ^List) -> bool {…}
     

    Checks whether the given list does not contain any element.

    Inputs

    • list: The container list

    Returns true if list is empty, false otherwise

    iterate_next ¶

    iterate_next :: proc "contextless" (it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {…}
     

    Retrieves the next element in a list and advances the iterator.

    Inputs

    • it: The iterator

    Returns

    • ptr: The next list element
    • ok: true if the element is valid (the iterator could advance), false otherwise
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    iterate_next_example :: proc() {
    	l: list.List
    
    	one := My_Next_Struct{value=1}
    	two := My_Next_Struct{value=2}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &two.node)
    
    	it := list.iterator_head(l, My_Next_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Next_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    

    iterate_prev ¶

    iterate_prev :: proc "contextless" (it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {…}
     

    Retrieves the previous element in a list and recede the iterator.

    Inputs

    • it: The iterator

    Returns

    • ptr: The previous list element
    • ok: true if the element is valid (the iterator could recede), false otherwise
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    iterate_prev_example :: proc() {
    	l: list.List
    
    	one := My_Prev_Struct{value=1}
    	two := My_Prev_Struct{value=2}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &two.node)
    
    	it := list.iterator_tail(l, My_Prev_Struct, "node")
    	for num in list.iterate_prev(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Prev_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    2
    1
    

    iterator_from_node ¶

    iterator_from_node :: proc "contextless" (
    	node:       ^Node, 
    	$T:          typeid, 
    	$field_name: string, 
    ) -> Iterator(T) {…}
     

    Creates an iterator pointing at the specified node of a list.

    Inputs

    • node: a list node
    • T: The type of the list's elements
    • field_name: The name of the node field in the T structure

    Returns An iterator pointing at node

    iterator_head ¶

    iterator_head :: proc "contextless" (
    	list:       List, 
    	$T:          typeid, 
    	$field_name: string, 
    ) -> Iterator(T) {…}
     

    Creates an iterator pointing at the head of the given list. For an example, see iterate_next.

    Inputs

    • list: The container list
    • T: The type of the list's elements
    • field_name: The name of the node field in the T structure

    Returns An iterator pointing at the head of list

    iterator_tail ¶

    iterator_tail :: proc "contextless" (
    	list:       List, 
    	$T:          typeid, 
    	$field_name: string, 
    ) -> Iterator(T) {…}
     

    Creates an iterator pointing at the tail of the given list. For an example, see iterate_prev.

    Inputs

    • list: The container list
    • T: The type of the list's elements
    • field_name: The name of the node field in the T structure

    Returns An iterator pointing at the tail of list

    move_after ¶

    move_after :: proc "contextless" (list: ^List, node, after: ^Node) {…}
     

    Moves an element after another with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure
    • after: The node to move behind, or nil to move to the front
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    move_after_example :: proc() {
    	l: list.List
    
    	one   := My_Move_After_Struct{value=1}
    	two   := My_Move_After_Struct{value=2}
    	three := My_Move_After_Struct{value=3}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &three.node)
    	list.push_back(&l, &two.node)
    	list.move_after(&l, &two.node, &one.node)
    
    	it := list.iterator_head(l, My_Move_After_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Move_After_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    

    move_before ¶

    move_before :: proc "contextless" (list: ^List, node, before: ^Node) {…}
     

    Moves an element before another with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure
    • before: The node to move in front of, or nil to move to the back
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    move_before_example :: proc() {
    	l: list.List
    
    	one   := My_Move_Before_Struct{value=1}
    	two   := My_Move_Before_Struct{value=2}
    	three := My_Move_Before_Struct{value=3}
    
    	list.push_back(&l, &two.node)
    	list.push_back(&l, &three.node)
    	list.push_back(&l, &one.node)
    	list.move_before(&l, &one.node, &two.node)
    
    	it := list.iterator_head(l, My_Move_Before_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Move_Before_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    

    pop_back ¶

    pop_back :: proc "contextless" (list: ^List) -> ^Node {…}
     

    Removes and returns the element at the back of the list with O(1) time complexity.

    Inputs

    • list: The container list

    Returns The node member of the user-defined element structure, or nil if the list is empty

    pop_front ¶

    pop_front :: proc "contextless" (list: ^List) -> ^Node {…}
     

    Removes and returns the element at the front of the list with O(1) time complexity.

    Inputs

    • list: The container list

    Returns The node member of the user-defined element structure, or nil if the list is empty

    push_back ¶

    push_back :: proc "contextless" (list: ^List, node: ^Node) {…}
     

    Inserts a new element at the back of the list with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure

    push_front ¶

    push_front :: proc "contextless" (list: ^List, node: ^Node) {…}
     

    Inserts a new element at the front of the list with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure

    remove ¶

    remove :: proc "contextless" (list: ^List, node: ^Node) {…}
     

    Removes an element from a list with O(1) time complexity.

    Inputs

    • list: The container list
    • node: The node member of the user-defined element structure to be removed

    remove_by_proc ¶

    remove_by_proc :: proc(list: ^List, to_erase: proc(^Node) -> bool) {…}
     

    Removes from the given list all elements that satisfy a condition with O(N) time complexity.

    Inputs

    • list: The container list
    • to_erase: The condition procedure. It should return true if a node should be removed, false otherwise

    remove_by_proc_contextless ¶

    remove_by_proc_contextless :: proc(list: ^List, to_erase: proc "contextless" (^Node) -> bool) {…}
     

    Removes from the given list all elements that satisfy a condition with O(N) time complexity.

    Inputs

    • list: The container list
    • to_erase: The contextless condition procedure. It should return true if a node should be removed, false otherwise

    replace ¶

    replace :: proc "contextless" (list: ^List, old, new: ^Node) {…}
     

    Replaces an element of the list with a new element with O(1) time complexity.

    Inputs

    • list: The container list
    • old: The node to take out of the list
    • new: The node to put in its place
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    replace_example :: proc() {
    	l: list.List
    
    	one   := My_Replace_Struct{value=1}
    	two   := My_Replace_Struct{value=2}
    	three := My_Replace_Struct{value=3}
    	four  := My_Replace_Struct{value=4}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &four.node)
    	list.push_back(&l, &three.node)
    	list.replace(&l, &four.node, &two.node)
    
    	it := list.iterator_head(l, My_Replace_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Replace_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    

    splice_after ¶

    splice_after :: proc "contextless" (list, other: ^List, after: ^Node) {…}
     

    Moves all elements of another list after an element with O(1) time complexity, leaving the other list empty.

    Inputs

    • list: The container list
    • other: The list to move the elements from
    • after: The node to move them behind, or nil to move them to the front
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    splice_after_example :: proc() {
    	l, other: list.List
    
    	one   := My_Splice_After_Struct{value=1}
    	two   := My_Splice_After_Struct{value=2}
    	three := My_Splice_After_Struct{value=3}
    	four  := My_Splice_After_Struct{value=4}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &four.node)
    	list.push_back(&other, &two.node)
    	list.push_back(&other, &three.node)
    	list.splice_after(&l, &other, &one.node)
    
    	it := list.iterator_head(l, My_Splice_After_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Splice_After_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    4
    

    splice_before ¶

    splice_before :: proc "contextless" (list, other: ^List, before: ^Node) {…}
     

    Moves all elements of another list before an element with O(1) time complexity, leaving the other list empty.

    Inputs

    • list: The container list
    • other: The list to move the elements from
    • before: The node to move them in front of, or nil to move them to the back
    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    splice_before_example :: proc() {
    	l, other: list.List
    
    	one   := My_Splice_Before_Struct{value=1}
    	two   := My_Splice_Before_Struct{value=2}
    	three := My_Splice_Before_Struct{value=3}
    	four  := My_Splice_Before_Struct{value=4}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &four.node)
    	list.push_back(&other, &two.node)
    	list.push_back(&other, &three.node)
    	list.splice_before(&l, &other, &four.node)
    
    	it := list.iterator_head(l, My_Splice_Before_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println(num.value)
    	}
    }
    
    My_Splice_Before_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    1
    2
    3
    4
    

    split_after ¶

    split_after :: proc "contextless" (list: ^List, after: ^Node) -> (back: List) {…}
     

    Splits off all elements after an element into a new list with O(1) time complexity.

    Inputs

    • list: The container list
    • after: The node to split behind, or nil to split off the whole list

    Returns The elements that were behind after, as a new list

    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    split_after_example :: proc() {
    	l: list.List
    
    	one   := My_Split_After_Struct{value=1}
    	two   := My_Split_After_Struct{value=2}
    	three := My_Split_After_Struct{value=3}
    	four  := My_Split_After_Struct{value=4}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &two.node)
    	list.push_back(&l, &three.node)
    	list.push_back(&l, &four.node)
    	back := list.split_after(&l, &two.node)
    
    	it := list.iterator_head(l, My_Split_After_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println("list", num.value)
    	}
    	it = list.iterator_head(back, My_Split_After_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println("back", num.value)
    	}
    }
    
    My_Split_After_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    list 1
    list 2
    back 3
    back 4
    

    split_before ¶

    split_before :: proc "contextless" (list: ^List, before: ^Node) -> (front: List) {…}
     

    Splits off all elements before an element into a new list with O(1) time complexity.

    Inputs

    • list: The container list
    • before: The node to split in front of, or nil to split off the whole list

    Returns The elements that were in front of before, as a new list

    Example:
    import "core:fmt"
    import "core:container/intrusive/list"
    
    split_before_example :: proc() {
    	l: list.List
    
    	one   := My_Split_Before_Struct{value=1}
    	two   := My_Split_Before_Struct{value=2}
    	three := My_Split_Before_Struct{value=3}
    	four  := My_Split_Before_Struct{value=4}
    
    	list.push_back(&l, &one.node)
    	list.push_back(&l, &two.node)
    	list.push_back(&l, &three.node)
    	list.push_back(&l, &four.node)
    	front := list.split_before(&l, &three.node)
    
    	it := list.iterator_head(front, My_Split_Before_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println("front", num.value)
    	}
    	it = list.iterator_head(l, My_Split_Before_Struct, "node")
    	for num in list.iterate_next(&it) {
    		fmt.println("list", num.value)
    	}
    }
    
    My_Split_Before_Struct :: struct {
    	node : list.Node,
    	value: int,
    }
    
    Output:
    front 1
    front 2
    list 3
    list 4
    

    Procedure Groups

    This section is empty.

    Source Files

    Generation Information

    Generated with odin version dev-2026-11 (vendor "odin") Windows_amd64 @ 2026-11-18 21:05:19.828955300 +0000 UTC