package core:container/intrusive/list
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,
}
Hello World
Index
Constants (0)
This section is empty.
Variables (0)
This section is empty.
Procedures (22)
Procedure Groups (0)
This section is empty.
Types
Iterator ¶
Iterator :: struct($T: typeid) { … // See source for fields }
Related Procedures With Parameters
List ¶
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
Constants
This section is empty.
Variables
This section is empty.
Procedures
insert_after ¶
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
nilto 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,
}
1 2 3
insert_before ¶
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
nilto 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,
}
1 2 3
is_empty ¶
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 ¶
Retrieves the next element in a list and advances the iterator.
Inputs
- it: The iterator
Returns
- ptr: The next list element
- ok:
trueif the element is valid (the iterator could advance),falseotherwise
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,
}
1 2
iterate_prev ¶
Retrieves the previous element in a list and recede the iterator.
Inputs
- it: The iterator
Returns
- ptr: The previous list element
- ok:
trueif the element is valid (the iterator could recede),falseotherwise
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,
}
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
Tstructure
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
Tstructure
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
Tstructure
Returns An iterator pointing at the tail of list
move_after ¶
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
nilto 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,
}
1 2 3
move_before ¶
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
nilto 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,
}
1 2 3
pop_back ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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
trueif a node should be removed,falseotherwise
remove_by_proc_contextless ¶
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
trueif a node should be removed,falseotherwise
replace ¶
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,
}
1 2 3
splice_after ¶
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
nilto 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,
}
1 2 3 4
splice_before ¶
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
nilto 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,
}
1 2 3 4
split_after ¶
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
nilto 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,
}
list 1 list 2 back 3 back 4
split_before ¶
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
nilto 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,
}
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