func New
New creates a new unbounded deque.
v0 source pure
Package deque provides a doubly-linked deque with optional size limits, optimized for minimal storage updates and O(1...
View source
gno.land/p/moul/deque
A doubly-linked deque, optionally bounded, written for chain storage rather than for RAM.
1d := deque.New() // unbounded
2d = deque.NewBounded(3) // evicts from the front past 3 elements
3
4d.PushBack("a", "b", "c")
5d.PushFront("z")
6first := d.PopFront()
7last := d.Last()
Why not a slice
A slice-backed queue rewrites the whole backing array on append-and-grow and shifts every element on pop-front. On gno that is not a constant factor, it is the storage bill: the VM persists what changed, so touching N elements costs N.
Each operation here updates one or two node pointers and nothing else:
| operation | cost |
|---|---|
PushBack, PushFront, PopFront, PopBack |
O(1), 1-2 node writes |
First, Last, Size, IsEmpty |
O(1), no write |
Get(i) |
O(n) walk, no write |
Use it when you want a bounded log (the last N events), a FIFO work queue, or
any list where reads are "first / last / how many / iterate" and Get(i) is
rare. Use an avl tree instead when you need keyed lookup or ordering by
anything but insertion.
Bounded mode
NewBounded(n) makes eviction automatic and symmetric: pushing past the limit
at the back drops from the front, and pushing past it at the front drops from
the back. MaxSize() returns 0 for unbounded, IsBounded() says which.
Iteration
All() walks front to back, Backward() back to front. Both return a function
taking a func(any) bool callback; return false to stop early.
1d.All()(func(v any) bool {
2 println(v)
3 return true
4})
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
⚠️ Disclaimer: provided as-is, without warranty; not security-audited. Full disclaimer: DISCLAIMER.
Package deque provides a doubly-linked deque with optional size limits, optimized for minimal storage updates and O(1) operations in Gno environments.
This implementation uses a doubly-linked list structure that provides: - O(1) push back operations - O(1) pop front operations - O(1) access to first/last elements - No array resizing or slice shifting - Minimal allocations (one node per element) - Minimal storage updates (typically 1-2 pointer updates per operation) - Optional max-size eviction policy
Optimized for Gno blockchain storage: each operation updates only specific nodes rather than entire data structures, making it ideal for storage-efficient lists that need simple read operations like first/last access, size checks, list enumeration, and iteration with minimal storage update overhead.
Example usage:
Example
1// Unbounded deque
2d := deque.New()
3d.PushBack("a", "b", "c")
4
5// Bounded deque with automatic eviction
6d = deque.NewBounded(3)
7d.PushBack("a", "b", "c", "d") // "a" gets evicted
8
9first := d.PopFront() // Returns "b"
10last := d.Last() // Returns "d"
11
12// Iterate forward
13iter := d.All()
14iter(func(val any) bool {
15 println(val)
16 return true // continue
17})
18
19// Iterate backward
20iter = d.Backward()
21iter(func(val any) bool {
22 println(val)
23 return true // continue
24})
2
func NewBounded
NewBounded creates a new bounded deque with the specified maximum size. When the deque exceeds maxSize, elements are removed from the front.
2
type Deque
structDeque represents a doubly-linked deque with optional size limits
Methods on Deque
func All
method on DequeAll returns an iterator function for forward traversal (Go 1.23+ compatible) Note: range-over-func syntax is not yet supported in Gno, use iter() directly
func Backward
method on DequeBackward returns an iterator function for backward traversal (Go 1.23+ compatible) Note: range-over-func syntax is not yet supported in Gno, use iter() directly
func Clear
method on DequeClear removes all elements from the deque
func Enumerate
method on DequeEnumerate calls fn for each element with its index (0-based from front)
func First
method on DequeFirst returns the front element without removing it. Returns nil if the deque is empty.
func Get
method on DequeGet returns the element at the specified index (0 = front). Returns nil if index is out of bounds.
func IsBounded
method on DequeIsBounded returns true if the deque has a size limit
func IsEmpty
method on DequeIsEmpty returns true if the deque is empty
func Last
method on DequeLast returns the back element without removing it. Returns nil if the deque is empty.
func List
method on DequeList returns all elements as a slice, ordered from front to back
func MaxSize
method on DequeMaxSize returns the maximum size limit (0 = unlimited)
func PopBack
method on DequePopBack removes and returns the back element. Returns nil if the deque is empty.
func PopFront
method on DequePopFront removes and returns the front element. Returns nil if the deque is empty.
func PushBack
method on DequePushBack adds one or more elements to the back of the deque. If the deque exceeds maxSize, elements are removed from the front.
func PushFront
method on DequePushFront adds one or more elements to the front of the deque. If bounded and size limit is exceeded, elements are removed from the back.
func SetMaxSize
method on DequeSetMaxSize changes the maximum size limit. If the new limit is smaller than current size, elements are removed from front.
func Size
method on DequeSize returns the current number of elements
type Node
structNode represents a single element in the doubly-linked list
Imports 0
Imports nothing.
/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/deque/v0
