An easy to use, lightweight, thread-safe and append-only in-memory data structure inspired by Apache Kafka

[![Go
Reference](https://pkg.go.dev/badge/github.com/embano1/memlog.svg)](https://pkg.go.dev/github.com/embano1/memlog)
[![Tests](https://github.com/embano1/memlog/actions/workflows/tests.yaml/badge.svg)](https://github.com/embano1/memlog/actions/workflows/tests.yaml)
[![Latest
Release](https://img.shields.io/github/release/embano1/memlog.svg?logo=github&style=flat-square)](https://github.com/embano1/memlog/releases/latest)
[![Go Report
Card](https://goreportcard.com/badge/github.com/embano1/memlog)](https://goreportcard.com/report/github.com/embano1/memlog)
[![codecov](https://codecov.io/gh/embano1/memlog/branch/main/graph/badge.svg?token=TC7MW723JO)](https://codecov.io/gh/embano1/memlog)
[![go.mod Go
version](https://img.shields.io/github/go-mod/go-version/embano1/memlog)](https://github.com/embano1/memlog)
[![Mentioned in Awesome Go](https://awesome.re/mentioned-badge.svg)](https://github.com/avelino/awesome-go)  

# About

## tl;dr

An easy to use, lightweight, thread-safe and append-only in-memory data
structure modeled as a *Log*.

The `Log` also serves as an abstraction and building block. See
[`sharded.Log`](./sharded/README.md) for an implementation of a *sharded*
variant of `memlog.Log`.

❌ Note: this package is not about providing an in-memory `logging` library. To
read more about the ideas behind `memlog` please see ["The Log: What every
software engineer should know about real-time data's unifying
abstraction"](https://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying).

## Motivation

I keep hitting the same user story (use case) over and over again: one or more
clients connected to my application wanting to read an **immutable** stream of
data, e.g. events or sensor data, **in-order**, **concurrently** (thread-safe)
and **asynchronously** (at their own pace) and in a resource (memory)
**efficient** way.

There's many solutions to this problem, e.g. exposing some sort of streaming API
(*gRPC*, HTTP/REST long-polling) based on custom logic using Go channels or an
internal [ring buffer](https://pkg.go.dev/container/ring), or putting data into
an external platform like [Kafka](https://kafka.apache.org/), [Redis
Streams](https://redis.io/topics/streams-intro) or [RabbitMQ
Streams](https://blog.rabbitmq.com/posts/2021/07/rabbitmq-streams-overview).

The challenges I faced with these solutions were that either they were too
**complex** (or simply **overkill**) for my problem. Or, the system I had to
integrate with and read data from did not have a nice streaming API or Go SDK,
thus repeating myself writing complex internal caching, buffering and
concurrency handling logic for the client APIs.

I looked around and could not find a simple and easy to use Go library for this
problem, so I created `memlog`: an **easy to use, lightweight (in-memory),
thread-safe, append-only log** inspired by popular streaming systems with a
**minimal API** using Go's **standard library** primitives 🤩

💡 For an end-to-end API modernization example using `memlog` see the
`vsphere-event-streaming`
[project](https://github.com/embano1/vsphere-event-streaming), which transforms
a SOAP-based events API into an HTTP/REST streaming API.

# Usage

```go
	ml, _ := memlog.New(ctx) // create log
	offset, _ := ml.Write(ctx, []byte("Hello World")) // write some data
	record, _ := ml.Read(ctx, offset) // read back data
	fmt.Printf(string(record.Data)) // prints "Hello World"
```

The `memlog` API is intentionally kept minimal. A new `Log` is constructed with `memlog.New(ctx, options...)`. Data as
`[]byte` is written to the log with `Log.Write(ctx, data)`.

The first write to the `Log` using *default* `Options` starts at position
(`Offset`) `0`. Every write creates an immutable `Record` in the `Log`.
`Records` are purged from the `Log` when the *history* `segment` is replaced
(see notes below).

The *earliest* and *latest* `Offset` available in a `Log` can be retrieved with
`Log.Range(ctx)`.

A specified `Record` can be read with `Log.Read(ctx, offset)`.

💡 Instead of manually polling the `Log` for new `Records`, the *streaming* API
`Log.Stream(ctx, startOffset)` should be used.

## (Not) one `Log` to rule them all

One is not constrained by just creating **one** `Log`. For certain use cases,
creating multiple `Logs` might be useful. For example:

- Manage completely different data sets/sizes in the same process
- Setting different `Log` sizes (i.e. retention times), e.g. premium users will
  have access to a larger *history* of `Records`
- Partitioning input data by type or *key*

💡 For use cases where you want to order the log by `key(s)`, consider using the
specialised [`sharded.Log`](sharded/README.md).

## Full Example

```go
package main

import (
	"context"
	"fmt"
	"os"

	"github.com/embano1/memlog"
)

func main() {
	ctx := context.Background()
	l, err := memlog.New(ctx)
	if err != nil {
		fmt.Printf("create log: %v", err)
		os.Exit(1)
	}

	offset, err := l.Write(ctx, []byte("Hello World"))
	if err != nil {
		fmt.Printf("write: %v", err)
		os.Exit(1)
	}

	fmt.Printf("reading record at offset %d\n", offset)
	record, err := l.Read(ctx, offset)
	if err != nil {
		fmt.Printf("read: %v", err)
		os.Exit(1)
	}

	fmt.Printf("data says: %s", record.Data)

	// reading record at offset 0
	// data says: Hello World
}
```

## Purging the `Log`

The `Log` is divided into an *active* and *history* `segment`. When the *active*
`segment` is full (configurable via `WithMaxSegmentSize()`), it is *sealed*
(i.e. read-only) and becomes the *history* `segment`. A new empty *active*
`segment` is created for writes. If there is an existing *history*, it is
replaced, i.e. all `Records` are purged from the *history*.

See [pkg.go.dev](https://pkg.go.dev/github.com/embano1/memlog) for the API
reference and examples.

## A stateless Log? You gotta be kidding!

True, it sounds like an oxymoron. Why would someone use (build) an *in-memory*
append-only log that is not durable?

I'm glad you asked 😀

This library certainly is not intended to replace messaging, queuing or
streaming systems. It was built for use cases where there exists a *durable
data/event source*, e.g. a legacy system, REST API, database, etc. that can't
(or should not) be changed. But the requirement being that the (source) data
should be made available over a streaming-like API, e.g. *gRPC* or processed by
a Go application which requires the properties of a `Log`.

`memlog` helps as it allows to bridge between these different APIs and use cases
as a *building block* to extract and store data `Records` from an external
system into an *in-memory* `Log` (think ordered cache).

These `Records` can then be internally processed (lightweight ETL) or served
asynchronously, in-order (`Offset`-based) and concurrently over a *modern
streaming API*, e.g. *gRPC* or HTTP/REST (chunked encoding via long polling), to
remote clients.

As another example of such an in-memory log-structured design,
[`DDlog`](https://github.com/vmware/differential-datalog) follows a similar
approach, where a `DDlog` program is used in conjunction with a persistent
database, with database records being fed to DDlog as ground facts.

### Checkpointing

Given the data source needs to be durable in this design, one can optionally
build periodic checkpointing logic using the `Record` `Offset` as the checkpoint
value. 

💡 When running in Kubernetes,
[`kvstore`](https://github.com/knative/pkg/tree/main/kvstore) provides a nice
abstraction on top of a `ConfigMap` for such requirements. 

If the `memlog` process crashes, it can then resume from the last checkpointed
`Offset`, load the changes since then from the source and resume streaming. 

💡 This approach is quiet similar to the Kubernetes `ListerWatcher()`
[pattern](https://youtu.be/YIBQrP1grPE?t=1132). See
[`memlog_test.go`](./memlog_test.go) for some inspiration.

# Benchmark

I haven't done any extensive benchmarking or code optimization. Feel free to
chime in and provide meaningful feedback/optimizations. 

One could argue, whether using two *slices* (*active* and *history* `data
[]Record` as part of the individual `segments`) is a good engineering choice,
e.g. over using a growable slice as an alternative. 

The reason I went for two `segments` was that for me dividing the `Log` into
multiple `segments` with fixed *size* (and *capacity*) was easier to reason
about in the code (and I followed my intuition from how log-structured data
platforms do it). I did not inspect the Go compiler optimizations, e.g. it might
actually be smart and create one growable slice under the hood. 🤓

These are some results on my MacBook  using a log size of `1,000` (records),
i.e. where the `Log` history is constantly purged and new `segments` (*slices*)
are created.

```console
go test -v -run=none -bench=. -cpu 1,2,4,8,16 -benchmem
goos: darwin
goarch: amd64
pkg: github.com/embano1/memlog
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
BenchmarkLog_write
BenchmarkLog_write              11107804               103.0 ns/op            89 B/op          1 allocs/op
BenchmarkLog_write-2            11115896               107.1 ns/op            89 B/op          1 allocs/op
BenchmarkLog_write-4            11419497               105.7 ns/op            89 B/op          1 allocs/op
BenchmarkLog_write-8            10253677               109.6 ns/op            89 B/op          1 allocs/op
BenchmarkLog_write-16           10865994               107.7 ns/op            89 B/op          1 allocs/op
BenchmarkLog_read
BenchmarkLog_read               24461548                49.49 ns/op           32 B/op          1 allocs/op
BenchmarkLog_read-2             25002574                46.63 ns/op           32 B/op          1 allocs/op
BenchmarkLog_read-4             23829378                47.47 ns/op           32 B/op          1 allocs/op
BenchmarkLog_read-8             22936821                47.47 ns/op           32 B/op          1 allocs/op
BenchmarkLog_read-16            24121807                48.25 ns/op           32 B/op          1 allocs/op
PASS
ok      github.com/embano1/memlog       12.541s
```


memlog

Multiple thread-safe, generic queue implementations for Go

# queue

![GitHub release](https://img.shields.io/github/v/tag/adrianbrad/queue)
[![GitHub go.mod Go version of a Go module](https://img.shields.io/github/go-mod/go-version/adrianbrad/queue)](https://github.com/adrianbrad/queue)
[![GoDoc reference example](https://img.shields.io/badge/godoc-reference-blue.svg)](https://pkg.go.dev/github.com/adrianbrad/queue)
[![Mentioned in Awesome Go](https://awesome.re/mentioned-badge.svg)](https://github.com/avelino/awesome-go)

[![CodeFactor](https://www.codefactor.io/repository/github/adrianbrad/queue/badge)](https://www.codefactor.io/repository/github/adrianbrad/queue)
[![Go Report Card](https://goreportcard.com/badge/github.com/adrianbrad/queue)](https://goreportcard.com/report/github.com/adrianbrad/queue)
[![codecov](https://codecov.io/gh/adrianbrad/queue/branch/main/graph/badge.svg)](https://codecov.io/gh/adrianbrad/queue)

[![lint-test](https://github.com/adrianbrad/queue/actions/workflows/lint-test.yaml/badge.svg)](https://github.com/adrianbrad/queue/actions?query=workflow%3Alint-test)
[![grype](https://github.com/adrianbrad/queue/actions/workflows/grype.yaml/badge.svg)](https://github.com/adrianbrad/queue/actions?query=workflow%3Agrype)
[![codeql](https://github.com/adrianbrad/queue/actions/workflows/codeql.yaml/badge.svg)](https://github.com/adrianbrad/queue/actions?query=workflow%3ACodeQL)

---

The `queue` package provides thread-safe generic implementations in Go for the following data structures: `BlockingQueue`, `PriorityQueue`, `CircularQueue` and `Linked Queue`.

A queue is a sequence of entities that is open at both ends where the elements are
added (enqueued) to the tail (back) of the queue and removed (dequeued) from the head (front) of the queue.

The implementations are designed to be easy-to-use and provide a consistent API, satisfying the `Queue` interface provided by this package. .

Benchmarks and Example tests can be found in this package. 


* [queue](#queue)
  * [Installation](#installation)
  * [Import](#import)
  * [Usage](#usage)
    * [Queue Interface](#queue-interface)
    * [Blocking Queue](#blocking-queue)
    * [Priority Queue](#priority-queue)
    * [Circular Queue](#circular-queue)
    * [Linked Queue](#linked-queue)
  * [Benchmarks](#benchmarks-)


## Installation
To add this package as a dependency to your project, run:

```shell
go get -u github.com/adrianbrad/queue
```

## Import
To use this package in your project, you can import it as follows:

```go
import "github.com/adrianbrad/queue"
```

## Usage

### Queue Interface

```go
// Queue is a generic queue interface, defining the methods that all queues must implement.
type Queue[T comparable] interface {
	// Get retrieves and removes the head of the queue.
	Get() (T, error)

	// Offer inserts the element to the tail of the queue.
	Offer(T) error

	// Reset sets the queue to its initial state.
	Reset()

	// Contains returns true if the queue contains the element.
	Contains(T) bool

	// Peek retrieves but does not remove the head of the queue.
	Peek() (T, error)

	// Size returns the number of elements in the queue.
	Size() int

	// IsEmpty returns true if the queue is empty.
	IsEmpty() bool

	// Iterator returns a channel that will be filled with the elements
	Iterator() <-chan T

	// Clear removes all elements from the queue.
	Clear() []T
}
```

### Blocking Queue

Blocking queue is a FIFO ordered data structure. Both blocking and non-blocking methods are implemented.
Blocking methods wait for the queue to have available items when dequeuing, and wait for a slot to become available in case the queue is full when enqueuing.
The non-blocking methods return an error if an element cannot be added or removed. 
Implemented using sync.Cond from the standard library.

```go
package main

import (
	"fmt"

	"github.com/adrianbrad/queue"
)

func main() {
	elems := []int{2, 3}

	blockingQueue := queue.NewBlocking(elems, queue.WithCapacity(3))

	containsTwo := blockingQueue.Contains(2)
	fmt.Println(containsTwo) // true

	size := blockingQueue.Size()
	fmt.Println(size) // 2

	empty := blockingQueue.IsEmpty()
	fmt.Println(empty) // false

	if err := blockingQueue.Offer(1); err != nil {
		// handle err
	}

	elem, err := blockingQueue.Get()
	if err != nil {
		// handle err
	}

	fmt.Println("elem: ", elem) // elem: 2
}
```

### Priority Queue

Priority Queue is a data structure where the order of the elements is given by a comparator function provided at construction. 
Implemented using container/heap standard library package.

```go
package main

import (
	"fmt"

	"github.com/adrianbrad/queue"
)

func main() {
	elems := []int{2, 3, 4}

	priorityQueue := queue.NewPriority(
		elems, 
		func(elem, otherElem int) bool { return elem < otherElem },
        )

	containsTwo := priorityQueue.Contains(2)
	fmt.Println(containsTwo) // true

	size := priorityQueue.Size()
	fmt.Println(size) // 3

	empty := priorityQueue.IsEmpty()
	fmt.Println(empty) // false

	if err := priorityQueue.Offer(1); err != nil {
		// handle err
	}

	elem, err := priorityQueue.Get()
	if err != nil {
		// handle err
	}

	fmt.Printf("elem: %d\n", elem) // elem: 1
}
```

### Circular Queue

Circular Queue is a fixed size FIFO ordered data structure. When the queue is full, adding a new element to the queue overwrites the oldest element.

Example:
We have the following queue with a capacity of 3 elements: [1, 2, 3].
If the tail of the queue is set to 0, as if we just added the element `3`,
the next element to be added to the queue will overwrite the element at index 0.
So, if we add the element `4`, the queue will look like this: [4, 2, 3].
If the head of the queue is set to 0, as if we never removed an element yet,
then the next element to be removed from the queue will be the element at index 0, which is `4`.

```go
package main

import (
  "fmt"

  "github.com/adrianbrad/queue"
)

func main() {
  elems := []int{2, 3, 4}

  circularQueue := queue.NewCircular(elems, 3)

  containsTwo := circularQueue.Contains(2)
  fmt.Println(containsTwo) // true

  size := circularQueue.Size()
  fmt.Println(size) // 3

  empty := circularQueue.IsEmpty()
  fmt.Println(empty) // false

  if err := circularQueue.Offer(1); err != nil {
    // handle err
  }

  elem, err := circularQueue.Get()
  if err != nil {
    // handle err
  }

  fmt.Printf("elem: %d\n", elem) // elem: 1
}
```

### Linked Queue

A linked queue, implemented as a singly linked list, offering O(1)
time complexity for enqueue and dequeue operations. The queue maintains pointers
to both the head (front) and tail (end) of the list for efficient operations
without the need for traversal.

```go
package main

import (
  "fmt"

  "github.com/adrianbrad/queue"
)

func main() {
  elems := []int{2, 3, 4}

  circularQueue := queue.NewLinked(elems)

  containsTwo := circularQueue.Contains(2)
  fmt.Println(containsTwo) // true

  size := circularQueue.Size()
  fmt.Println(size) // 3

  empty := circularQueue.IsEmpty()
  fmt.Println(empty) // false

  if err := circularQueue.Offer(1); err != nil {
    // handle err
  }

  elem, err := circularQueue.Get()
  if err != nil {
    // handle err
  }

  fmt.Printf("elem: %d\n", elem) // elem: 2
}
```

## Benchmarks 

Results as of October 2023.

```text
BenchmarkBlockingQueue/Peek-8           84873882                13.98 ns/op            0 B/op          0 allocs/op
BenchmarkBlockingQueue/Get_Offer-8      27135865                47.00 ns/op           44 B/op          0 allocs/op
BenchmarkBlockingQueue/Offer-8          53750395                25.40 ns/op           43 B/op          0 allocs/op
BenchmarkCircularQueue/Peek-8           86001980                13.76 ns/op            0 B/op          0 allocs/op
BenchmarkCircularQueue/Get_Offer-8      32379159                36.83 ns/op            0 B/op          0 allocs/op
BenchmarkCircularQueue/Offer-8          63956366                18.77 ns/op            0 B/op          0 allocs/op
BenchmarkLinkedQueue/Peek-8             1000000000              0.4179 ns/op           0 B/op          0 allocs/op
BenchmarkLinkedQueue/Get_Offer-8        61257436                18.48 ns/op           16 B/op          1 allocs/op
BenchmarkLinkedQueue/Offer-8            38975062                30.74 ns/op           16 B/op          1 allocs/op
BenchmarkPriorityQueue/Peek-8           86633734                14.02 ns/op            0 B/op          0 allocs/op
BenchmarkPriorityQueue/Get_Offer-8      29347177                39.88 ns/op            0 B/op          0 allocs/op
BenchmarkPriorityQueue/Offer-8          40117958                31.37 ns/op           54 B/op          0 allocs/op
```

queue

Fast ring-buffer deque (double-ended queue)

# deque

[![GoDoc](https://pkg.go.dev/badge/github.com/gammazero/deque)](https://pkg.go.dev/github.com/gammazero/deque)
[![Build Status](https://github.com/gammazero/deque/actions/workflows/go.yml/badge.svg)](https://github.com/gammazero/deque/actions/workflows/go.yml)
[![Go Report Card](https://goreportcard.com/badge/github.com/gammazero/deque)](https://goreportcard.com/report/github.com/gammazero/deque)
[![codecov](https://codecov.io/gh/gammazero/deque/branch/master/graph/badge.svg)](https://codecov.io/gh/gammazero/deque)
[![License](https://img.shields.io/badge/License-MIT-blue.svg)](LICENSE)

Fast ring-buffer deque ([double-ended queue](https://en.wikipedia.org/wiki/Double-ended_queue)) implementation.

For a pictorial description, see the [Deque diagram](https://github.com/gammazero/deque/wiki)

## Installation

```
$ go get github.com/gammazero/deque
```

## Deque data structure

Deque generalizes a queue and a stack, to efficiently add and remove items at either end with O(1) performance. [Queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) (FIFO) operations are supported using `PushBack` and `PopFront`. [Stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) (LIFO) operations are supported using `PushBack` and `PopBack`.

## Ring-buffer Performance

This deque implementation is optimized for CPU and GC performance. The circular buffer automatically re-sizes by powers of two, growing when additional capacity is needed and shrinking when only a quarter of the capacity is used, and uses bitwise arithmetic for all calculations. Since growth is by powers of two, adding elements will only cause O(log n) allocations. A base capacity can be set, with `SetBaseCap`, so that there is no resizing at or below that specified amount. The Deque can also be grown, using `Grow`, to ensure sufficient storage for n additional items, to prevent resizing when adding a number of itmes.

The ring-buffer implementation improves memory and time performance with fewer GC pauses, compared to implementations based on slices or linked lists. By wrapping around the buffer, previously used space is reused, making allocation unnecessary until all buffer capacity is used. The ring buffer implementation performs best when resizes are infrequest, as is the case when items moving in and out of the Deque are balanced or when the base capacity is large enough to rarely require a resize.

For maximum speed, this deque implementation leaves concurrency safety up to the application to provide, however the application chooses, if needed at all.

## Reading Empty Deque

Since it is OK for the deque to contain a `nil` value, it is necessary to either panic or return a second boolean value to indicate the deque is empty, when reading or removing an element. This deque panics when reading from an empty deque. This is a run-time check to help catch programming errors, which may be missed if a second return value is ignored. Simply check `Deque.Len()` before reading from the deque.

## Generics

Deque uses generics to create a Deque that contains items of the type specified. To create a Deque that holds a specific type, provide a type argument with the `Deque` variable declaration. For example:
```go
    stringDeque := new(deque.Deque[string])
    var intDeque deque.Deque[int]
```

Deque supports iterators that allow traversal or removal of items. When removing items this is useful to avoid intermediate resizes of the internal buffer. It also allows Deque to be used with the stdlib [`slices.Collect`](https://pkg.go.dev/slices#Collect), [`slices.Sorted`](https://pkg.go.dev/slices#Sorted), and others that take [`iter.Seq`](https://pkg.go.dev/iter#Seq) argumments.

## Example

```go
package main

import (
    "fmt"
    "github.com/gammazero/deque"
)

func main() {
    var q deque.Deque[string]
    q.PushBack("foo")
    q.PushBack("bar")
    q.PushBack("baz")

    fmt.Println(q.Len())   // Prints: 3
    fmt.Println(q.Front()) // Prints: foo
    fmt.Println(q.Back())  // Prints: baz

    q.PopFront() // remove "foo"
    q.PopBack()  // remove "baz"

    q.PushFront("hello")
    q.PushBack("world")

    // Consume deque and print elements.
    for q.Len() != 0 {
        fmt.Println(q.PopFront())
    }
}
```

## Uses

Deque can be used as both a:
- [Queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) using `PushBack` and `PopFront`
- [Stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) using `PushBack` and `PopBack`


deque

[![go.dev reference](https://img.shields.io/badge/go.dev-reference-007d9c?logo=go&logoColor=white)](https://pkg.go.dev/mod/github.com/enriquebris/goconcurrentqueue) [![godoc reference](https://img.shields.io/badge/godoc-reference-blue.svg)](https://godoc.org/github.com/enriquebris/goconcurrentqueue) ![version](https://img.shields.io/badge/version-v0.7.0-yellowgreen.svg?style=flat "goconcurrentqueue v0.7.0") [![Build Status](https://api.travis-ci.org/enriquebris/goconcurrentqueue.svg?branch=master)](https://travis-ci.org/enriquebris/goconcurrentqueue) [![Go Report Card](https://goreportcard.com/badge/github.com/enriquebris/goconcurrentqueue)](https://goreportcard.com/report/github.com/enriquebris/goconcurrentqueue)  [![codecov](https://codecov.io/gh/enriquebris/goconcurrentqueue/branch/master/graph/badge.svg)](https://codecov.io/gh/enriquebris/goconcurrentqueue) [![CodeFactor](https://www.codefactor.io/repository/github/enriquebris/goconcurrentqueue/badge)](https://www.codefactor.io/repository/github/enriquebris/goconcurrentqueue) [![Mentioned in Awesome Go](https://awesome.re/mentioned-badge.svg)](https://github.com/avelino/awesome-go)

# goconcurrentqueue - Concurrent safe queues
The package goconcurrentqueue offers a public interface Queue with methods for a [queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)).
It comes with multiple Queue's concurrent-safe implementations, meaning they could be used concurrently by multiple goroutines without adding race conditions.

## Topics
 - [Installation](#installation)
 - [Documentation](#documentation)
 - [Classes diagram](#classes-diagram)
 - [Queues](#queues)
    - [FIFO](#fifo)
    - [FixedFIFO](#fixedfifo)
    - [Benchmarks](#benchmarks-fixedfifo-vs-fifo)
 - [Get started](#get-started)
 - [History](#history)

## Installation

Execute
```bash
go get github.com/enriquebris/goconcurrentqueue
```

This package is compatible with all golang versions >= 1.7.x

## Documentation
Visit [goconcurrentqueue at go.dev](https://pkg.go.dev/mod/github.com/enriquebris/goconcurrentqueue)

## Classes diagram
![goconcurrentqueue class diagram](web/class-diagram.svg "goconcurrentqueue class diagram")

## Queues

- First In First Out (FIFO)
    - [FIFO](#fifo)
    - [FixedFIFO](#fixedfifo)
    - [Benchmarks FixedFIFO vs FIFO](#benchmarks-fixedfifo-vs-fifo)

### FIFO

**FIFO**: concurrent-safe auto expandable queue.

#### pros
 - It is possible to enqueue as many items as needed.
 - Extra methods to get and remove enqueued items:
     - [Get](https://godoc.org/github.com/enriquebris/goconcurrentqueue#FIFO.Get): returns an element's value and keeps the element at the queue
     - [Remove](https://godoc.org/github.com/enriquebris/goconcurrentqueue#FIFO.Get): removes an element (using a given position) from the queue

#### cons
 - It is slightly slower than FixedFIFO.

### FixedFIFO

**FixedFIFO**: concurrent-safe fixed capacity queue.

#### pros
 - FixedFIFO is, at least, 2x faster than [FIFO](#fifo) in concurrent scenarios (multiple GR accessing the queue simultaneously).

#### cons
 - It has a fixed capacity meaning that no more items than this capacity could coexist at the same time. 

## Benchmarks FixedFIFO vs FIFO

The numbers for the following charts were obtained by running the benchmarks in a 2012 MacBook Pro (2.3 GHz Intel Core i7 - 16 GB 1600 MHz DDR3) with golang v1.12 

### Enqueue

![concurrent-safe FixedFIFO vs FIFO . operation: enqueue](web/FixedFIFO-vs-FIFO-enqueue.png "concurrent-safe FixedFIFO vs FIFO . operation: enqueue")

### Dequeue

![concurrent-safe FixedFIFO vs FIFO . operation: dequeue](web/FixedFIFO-vs-FIFO-dequeue.png "concurrent-safe FixedFIFO vs FIFO . operation: dequeue")

## Get started

### FIFO queue simple usage
[Live code - playground](https://play.golang.org/p/CRhg7kX0ikH)

```go
package main

import (
	"fmt"

	"github.com/enriquebris/goconcurrentqueue"
)

type AnyStruct struct {
	Field1 string
	Field2 int
}

func main() {
	queue := goconcurrentqueue.NewFIFO()

	queue.Enqueue("any string value")
	queue.Enqueue(5)
	queue.Enqueue(AnyStruct{Field1: "hello world", Field2: 15})

	// will output: 3
	fmt.Printf("queue's length: %v\n", queue.GetLen())

	item, err := queue.Dequeue()
	if err != nil {
		fmt.Println(err)
		return
	}

	// will output "any string value"
	fmt.Printf("dequeued item: %v\n", item)

	// will output: 2
	fmt.Printf("queue's length: %v\n", queue.GetLen())

}
```

### Wait until an element gets enqueued
[Live code - playground](https://play.golang.org/p/S7oSg3iUNhs)

```go
package main

import (
	"fmt"
	"time"

	"github.com/enriquebris/goconcurrentqueue"
)

func main() {
	var (
		fifo = goconcurrentqueue.NewFIFO()
		done = make(chan struct{})
	)

	go func() {
		fmt.Println("1 - Waiting for next enqueued element")
		value, _ := fifo.DequeueOrWaitForNextElement()
		fmt.Printf("2 - Dequeued element: %v\n", value)

		done <- struct{}{}
	}()

	fmt.Println("3 - Go to sleep for 3 seconds")
	time.Sleep(3 * time.Second)

	fmt.Println("4 - Enqueue element")
	fifo.Enqueue(100)

	<-done
}

```

### Wait until an element gets enqueued with timeout
[Live code - playground](https://play.golang.org/p/E3xdHcW5nJy)

```go
package main

import (
	"context"
	"fmt"
	"time"

	"github.com/enriquebris/goconcurrentqueue"
)

func main() {
	var (
		fifo = goconcurrentqueue.NewFIFO()
		ctx, cancel = context.WithTimeout(context.Background(), 3*time.Second)
	)
	defer cancel()

	fmt.Println("1 - Waiting for next enqueued element")
	_, err := fifo.DequeueOrWaitForNextElementContext(ctx)
    
	if err != nil {
		fmt.Printf("2 - Failed waiting for new element: %v\n", err)
		return
	}
}

```

### Dependency Inversion Principle using concurrent-safe queues

*High level modules should not depend on low level modules. Both should depend on abstractions.* Robert C. Martin

[Live code - playground](https://play.golang.org/p/3GAbyR7wrX7)

```go
package main

import (
	"fmt"

	"github.com/enriquebris/goconcurrentqueue"
)

func main() {
	var (
		queue          goconcurrentqueue.Queue
		dummyCondition = true
	)

	// decides which Queue's implementation is the best option for this scenario
	if dummyCondition {
		queue = goconcurrentqueue.NewFIFO()
	} else {
		queue = goconcurrentqueue.NewFixedFIFO(10)
	}

	fmt.Printf("queue's length: %v\n", queue.GetLen())
	workWithQueue(queue)
	fmt.Printf("queue's length: %v\n", queue.GetLen())
}

// workWithQueue uses a goconcurrentqueue.Queue to perform the work
func workWithQueue(queue goconcurrentqueue.Queue) error {
	// do some work

	// enqueue an item
	if err := queue.Enqueue("test value"); err != nil {
		return err
	}

	return nil
}
```

## History

### v0.7.0

- Prevents FIFO.DequeueOrWaitForNextElement to keep waiting for a waitChan while internal queues contain items

### v0.6.3

- Prevents FIFO.DequeueOrWaitForNextElement to add useless wait channels

### v0.6.2

- Prevents FIFO.DequeueOrWaitForNextElement to gets blocked when waiting for an enqueued element

### v0.6.1

- FixedFifo.Enqueue prevents to get blocked trying to send the item over an invalid waitForNextElementChan channel

### v0.6.0

- Added DequeueOrWaitForNextElementContext()

### v0.5.1

- FIFO.DequeueOrWaitForNextElement() was modified to avoid deadlock when DequeueOrWaitForNextElement && Enqueue are invoked around the same time.
- Added multiple goroutine unit testings for FIFO.DequeueOrWaitForNextElement() 

### v0.5.0

- Added DequeueOrWaitForNextElement()

### v0.4.0

- Added QueueError (custom error)

### v0.3.0

- Added FixedFIFO queue's implementation (at least 2x faster than FIFO for multiple GRs)
- Added benchmarks for both FIFO / FixedFIFO
- Added GetCap() to Queue interface
- Removed Get() and Remove() methods from Queue interface

### v0.2.0

- Added Lock/Unlock/IsLocked methods to control operations locking

### v0.1.0

- First In First Out (FIFO) queue added


goconcurrentqueue

**Please use [v2](v2), the generic version, if you have golang 1.18 or above.**

# Overview
Deque is a highly optimized double-ended queue, which is
much efficient compared with `list.List` when adding or removing elements from
the beginning or the end.

# Benchmark
```
PushBack/Deque<harden>       100000000       12.0 ns/op       8 B/op      0 allocs/op
PushBack/Deque                20000000       55.5 ns/op      24 B/op      1 allocs/op
PushBack/list.List             5000000      158.7 ns/op      56 B/op      1 allocs/op

PushFront/Deque<harden>      195840157        9.2 ns/op       8 B/op      0 allocs/op
PushFront/Deque               30000000       49.2 ns/op      24 B/op      1 allocs/op
PushFront/list.List            5000000      159.2 ns/op      56 B/op      1 allocs/op

Random/Deque<harden>          65623633       15.1 ns/op       0 B/op      0 allocs/op
Random/Deque                  50000000       24.7 ns/op       4 B/op      0 allocs/op
Random/list.List              30000000       46.9 ns/op      28 B/op      1 allocs/op
```

# Getting Started
```
go get -u github.com/edwingeng/deque
```

# Usage
``` go
dq := deque.NewDeque()
dq.PushBack(100)
dq.PushBack(200)
dq.PushBack(300)
for !dq.Empty() {
    fmt.Println(dq.PopFront())
}

dq.PushFront(100)
dq.PushFront(200)
dq.PushFront(300)
for i, n := 0, dq.Len(); i < n; i++ {
    fmt.Println(dq.PopFront())
}

// Output:
// 100
// 200
// 300
// 300
// 200
// 100
```

# Harden the element data type
``` bash
./harden.sh <outputDir> <packageName> [elemType]
```


Doubly-ended heap (min-max heap) with O(log n) access to both minimum and maximum elements

# deheap

[![Go Reference](https://pkg.go.dev/badge/github.com/aalpar/deheap.svg)](https://pkg.go.dev/github.com/aalpar/deheap)
[![Go Report Card](https://goreportcard.com/badge/github.com/aalpar/deheap)](https://goreportcard.com/report/github.com/aalpar/deheap)
[![codecov](https://codecov.io/gh/aalpar/deheap/graph/badge.svg)](https://codecov.io/gh/aalpar/deheap)

A doubly-ended heap (min-max heap) for Go. Provides O(log n) access to both
the minimum and maximum elements of a collection through a single data
structure, with zero external dependencies.

```
go get github.com/aalpar/deheap
```

## Why a doubly-ended heap?

A standard binary heap gives you efficient access to one extremum — the
smallest or the largest element — but not both. Many practical problems need
both ends simultaneously:

**Scheduling and resource allocation.** Operating system schedulers and job
queues routinely need the highest-priority task (to run next) and the
lowest-priority task (to evict or age). A doubly-ended priority queue avoids
maintaining two separate heaps and the bookkeeping to keep them synchronized.

**Bounded-size caches and buffers.** When a priority queue has a capacity
limit, insertions must discard the least valuable element. With a min-max
heap, both the insertion (against the max) and the eviction (from the min, or
vice versa) are logarithmic — no linear scan required.

**Median maintenance and order statistics.** Streaming median algorithms
typically partition data into a max-heap of the lower half and a min-heap of
the upper half. A single min-max heap can serve double duty, simplifying the
implementation.

**Network packet scheduling.** Rate-controlled and deadline-aware packet
schedulers (e.g., in QoS systems) need to dequeue by earliest deadline and
drop by lowest priority, both efficiently.

**Search algorithms.** Algorithms like SMA\* (Simplified Memory-Bounded A\*)
maintain an open set where the node with the lowest f-cost is expanded next
and the node with the highest f-cost is pruned when memory is exhausted.

## API

`deheap` provides two API surfaces.

### Generic API (Go 1.21+)

For `cmp.Ordered` types — `int`, `float64`, `string`, and friends — use the
type-safe generic API directly:

```go
import "github.com/aalpar/deheap"

// Construct from existing elements.
h := deheap.From(5, 3, 8, 1, 9)

// Or build incrementally.
h := deheap.New[int]()
h.Push(5)
h.Push(3)

// O(1) access to both extrema.
fmt.Println(h.Peek())    // smallest
fmt.Println(h.PeekMax()) // largest

// O(log n) removal from either end.
min := h.Pop()
max := h.PopMax()

// Remove by index.
val := h.Remove(2)

// Update an element and restore heap order.
h.Push(10)
h.Push(20)
// ... mutate the element at index 0 ...
h.Fix(0)

// Check if the heap is valid.
fmt.Println(h.Verify()) // true
```

### Interface API

For custom types, implement `heap.Interface` and use the package-level
functions. This is the original v1 API and remains stable.

```go
import "github.com/aalpar/deheap"

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

h := &IntHeap{2, 1, 5, 6}
deheap.Init(h)
deheap.Push(h, 3)
min := deheap.Pop(h)
max := deheap.PopMax(h)

// Update an element and restore heap order.
(*h)[0] = 42
deheap.Fix(h, 0)

// Check if the heap is valid.
fmt.Println(deheap.Verify(h)) // true
```

## Implementation

The underlying data structure is a **min-max heap** stored in a flat slice
with no pointers and no additional bookkeeping. Nodes on even levels
(0, 2, 4, ...) satisfy the min-heap property with respect to their
descendants, and nodes on odd levels (1, 3, 5, ...) satisfy the max-heap
property. The root is always the minimum; the maximum is one of its two
children.

Level parity is determined by bit-length of the 1-based index, computed via
`math/bits.Len` — a single CPU instruction on most architectures. Insertions
bubble up through grandparent links; deletions bubble down through
grandchild links, with a secondary swap against the binary-tree parent when
the element crosses a level boundary.

The generic API implements the same algorithms directly on `[]T` with
native `<` comparisons, eliminating interface dispatch, adapter allocation,
and boxing overhead.

### Complexity

| Operation | Time     | Space |
|-----------|----------|-------|
| `Push`    | O(log n) | O(1) amortized |
| `Pop`     | O(log n) | O(1) |
| `PopMax`  | O(log n) | O(1) |
| `Remove`  | O(log n) | O(1) |
| `Fix`     | O(log n) | O(1) |
| `Peek`    | O(1)     | O(1) |
| `PeekMax` | O(1)     | O(1) |
| `Init`    | O(n)     | O(1) |
| `Verify`  | O(n)     | O(1) |

Storage is a single contiguous slice — one element per slot, no child
pointers, no color bits, no auxiliary arrays. Memory overhead beyond the
elements themselves is the slice header (24 bytes on 64-bit systems).

### Benchmarks

Measured on Apple M4 Max (arm64), Go 1.23:

**Generic API** (`Deheap[T]` — direct `<` comparisons, no interface dispatch):

| Operation   | ns/op  | B/op | allocs/op |
|-------------|--------|------|-----------|
| Push        | 12     | 45   | 0         |
| Pop         | 225    | 0    | 0         |
| PopMax      | 225    | 0    | 0         |

**Interface API** (v1 — `heap.Interface`):

| Operation   | ns/op  | B/op | allocs/op |
|-------------|--------|------|-----------|
| Push        | 21     | 54   | 0         |
| Pop         | 288    | 7    | 0         |
| PopMax      | 282    | 7    | 0         |

**Standard library** (`container/heap`) for comparison:

| Operation   | ns/op  | B/op | allocs/op |
|-------------|--------|------|-----------|
| Push        | 22     | 55   | 0         |
| Pop         | 208    | 7    | 0         |

The generic API is faster than `container/heap` on Push. Pop is ~8% slower
due to examining up to four grandchildren per node (vs two children in a
binary heap), but provides O(log n) access to both extrema. The v1 interface
API pays the same `heap.Interface` dispatch cost as `container/heap`. All
operations are zero-allocation in steady state.

#### Benchmark descriptions

The benchmarks compare deheap's two API surfaces against each other and
against `container/heap`. Baseline measurements isolate the cost of slice
operations from heap logic. All benchmarks use a heap of 10,000 `int`
elements to ensure the working set fits in L1 cache while exercising the
full tree depth.

Sample run (Apple M4 Max, Go 1.23):

```
$ go test -bench . -benchmem
goos: darwin
goarch: arm64
pkg: github.com/aalpar/deheap
cpu: Apple M4 Max
BenchmarkMin4-16              	261428533	         4.784 ns/op	       0 B/op	       0 allocs/op
BenchmarkBaselinePush-16      	1000000000	         6.411 ns/op	      42 B/op	       0 allocs/op
BenchmarkPush-16              	44383689	        23.16 ns/op	      50 B/op	       0 allocs/op
BenchmarkPop-16               	 5666707	       326.3 ns/op	       7 B/op	       0 allocs/op
BenchmarkPopMax-16            	 5644575	       319.7 ns/op	       7 B/op	       0 allocs/op
BenchmarkPushPop-16           	 5098502	       297.2 ns/op	      65 B/op	       1 allocs/op
BenchmarkHeapPushPop-16       	 6203408	       256.5 ns/op	      56 B/op	       1 allocs/op
BenchmarkHeapPop-16           	 8475319	       234.7 ns/op	       7 B/op	       0 allocs/op
BenchmarkHeapPush-16          	46837188	        21.57 ns/op	      48 B/op	       0 allocs/op
BenchmarkOrderedPush-16       	100000000	        12.38 ns/op	      45 B/op	       0 allocs/op
BenchmarkOrderedPop-16        	 8680756	       249.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkOrderedPopMax-16     	10103798	       237.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkOrderedPushPop-16    	 8926204	       233.2 ns/op	      44 B/op	       0 allocs/op
PASS
```

| Benchmark | What it measures |
|-----------|-----------------|
| `OrderedPush` | Generic `Deheap[int].Push`: append + bubble-up with direct `<` comparisons. |
| `OrderedPop` | Generic `Deheap[int].Pop`: remove minimum and bubble-down with direct `<`. |
| `OrderedPopMax` | Generic `Deheap[int].PopMax`: remove maximum and bubble-down with direct `<`. |
| `OrderedPushPop` | Generic push-then-drain throughput. |
| `Min4` | Cost of `min4`, the internal function that finds the extremum among up to 4 grandchildren during bubble-down. |
| `BaselinePush` | Raw slice append with no heap ordering — establishes the floor cost of memory allocation and copying. |
| `Push` | `deheap.Push` (v1): append + bubble-up via `heap.Interface`. |
| `Pop` | `deheap.Pop` (v1): remove the minimum element and bubble-down via `heap.Interface`. |
| `PopMax` | `deheap.PopMax` (v1): remove the maximum element and bubble-down via `heap.Interface`. |
| `PushPop` | v1 push-then-drain throughput. |
| `HeapPushPop` | Same push-then-drain pattern using `container/heap` for direct comparison. |
| `HeapPop` | `container/heap.Pop` in isolation, comparable to `Pop` above. |
| `HeapPush` | `container/heap.Push` in isolation, comparable to `Push` above. |

## Testing

The test suite includes 54 test functions covering internal helpers,
algorithmic correctness, edge cases (empty, single-element, two-element
heaps), and large-scale randomized validation. Six native Go fuzz targets
(`testing.F`) exercise both API surfaces under arbitrary input. Tests are run
against Go 1.21, 1.22, and 1.23 in CI.

```bash
go test ./...          # run all tests
go test -bench . ./... # run benchmarks
go test -fuzz .        # run fuzz tests
```

## Requirements

- Go 1.21 or later (generic API)
- Go 1.13 or later (interface API only)
- Zero external dependencies

## References

1. M.D. Atkinson, J.-R. Sack, N. Santoro, and T. Strothotte. "Min-Max
   Heaps and Generalized Priority Queues." *Communications of the ACM*,
   29(10):996–1000, October 1986.
   https://doi.org/10.1145/6617.6621

2. J. van Leeuwen and D. Wood. "Interval Heaps." *The Computer Journal*,
   36(3):209–216, 1993.

3. P. Brass. *Advanced Data Structures*. Cambridge University Press, 2008.

## License

MIT — see [LICENSE](LICENSE).


deheap

Simple, in memory, zero dependency and battle tested, thread-safe deferred queue

D(EFERRED) Queue
======================

[![Go](https://github.com/vodolaz095/dqueue/actions/workflows/go.yml/badge.svg)](https://github.com/vodolaz095/dqueue/actions/workflows/go.yml)
[![PkgGoDev](https://pkg.go.dev/badge/github.com/vodolaz095/dqueue)](https://pkg.go.dev/github.com/vodolaz095/dqueue?tab=doc)
[![Go Report Card](https://goreportcard.com/badge/github.com/vodolaz095/dqueue)](https://goreportcard.com/report/github.com/vodolaz095/dqueue)


It was a test task i finished in 2 hours in 2017 year, i polished code a little, created
example with contexts and added 100% unit tests coverage in 2023.

What does it do?
======================
With this package we can make deferred queue of tasks to be executed, like
`execute this in 3 minutes`, `execute that in 15 seconds from now` and so on.
Then, we can consume this tasks by concurrent goroutines and they (tasks) will be
provided to consumers in proper order, like first task will be `that` to be executed in
15 seconds from now.

It is worth notice, that any element of queue can be of different type, and typecasting can be slow.
If you need something less agile and more performant, you can see generic based alternative - https://github.com/vodolaz095/dgqueue

Basic usage
=====================

Make queue handler:
```go
handler := dqueue.New() // import "github.com/vodolaz095/dqueue"

// payload can be anything - number, string, buffer, struct...
something := "task"

// Create tasks to be executed in future
handler.ExecuteAt(something, time.Now().Add(time.Minute))
handler.ExecuteAfter(something, time.Minute)

// Extract task ready to be executed
task, ready := handler.Get()
if ready { // task is ready
    fmt.Printf("Task %s is ready to be executed at %s",
		task.Payload.(string), 
		task.ExecuteAt.Format(time.Kitchen),
	)
} else {
	fmt.Println("No tasks are ready to be executed")
}
// Count tasks left
tasksInQueue := handler.Len()

// Extract all tasks, so, we can, for example, save all delivery queue  before closing application
tasks:= handler.Dump()

// Prune queue:
handler.Prune()
```

Concurrent consumers example
======================
See full example at [example.go](example%2Fexample.go)

```go

handler := dqueue.New() // import "github.com/vodolaz095/dqueue"

// Publish tasks
something := "task" // payload can be anything - number, string, buffer, struct...
handler.ExecuteAt(something, time.Now().Add(time.Minute))
handler.ExecuteAfter(something, time.Minute)

// make global context to be canceled when application is stopping
wg := sync.WaitGroup{}
mainCtx, mainCancel := context.WithTimeout(context.Background(), 3*time.Second)
defer mainCancel()

// Start concurrent consumers
wg := sync.WaitGroup{}
for j := 0; j < 10; j++ {
    wg.Add(1)
    go func(workerNumber int, initialCtx context.Context) {
        ctx, cancel := context.WithCancel(initialCtx)
        defer cancel()
        ticker := time.NewTicker(time.Millisecond)
        for {
            select {
            case t := <-ticker.C:
                task, ready := handler.Get()
                if ready { // task is ready
                    err := ProcessTask(task)
                    if err != nil { // aka, requeue message to be delivered in 1 minute
                      handler.ExecuteAfter(something, time.Minute)
                    }
                }
                break
            case <-ctx.Done():
                fmt.Printf("Closing worker %v, there are %v tasks in queue\n", workerNumber, handler.Len())
                wg.Done()
                ticker.Stop()
                return
            }
        }
    }(j, mainCtx)
}
wg.Wait()

// See tasks left, so they can be restored somehow when application is restarted
tasks := handler.Dump()

```


dqueue

hatchet

A generic, thread-safe doubly linked list with full iterator support and an intrusive singly linked list for embedded use; a feature-rich replacement for container/list

# Linked List Implementation in Go

[![Go Report Card](https://goreportcard.com/badge/github.com/koss-null/list)](https://goreportcard.com/report/github.com/koss-null/list)
[![Go Reference](https://pkg.go.dev/badge/github.com/koss-null/list.svg)](https://pkg.go.dev/github.com/koss-null/list)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Coverage](https://raw.githubusercontent.com/koss-null/list/master/coverage.svg?raw=true)](coverage.svg)

This repository contains:
- a **generic-based**, **thread-safe** implementation of a *doubly linked list* with **iterators support**.  
- a **generic-based** implementation of **intrusive** *singly linked list*.  
  
It was created to address the lack of iterators, async and generic support in Go's default `container/list` package.  


## Features

This linked list implementation provides the following features:

- **Generics**: The linked list can store elements of any type, thanks to Go's support for generics.
- **Iterators**: The `Begin` and `End` methods allow you to iterate over the list from the head to the tail and vice versa, respectively.
- **Node Access**: The `Head`, `Tail`, `Next`, and `Prev` methods provide access to the nodes of the list.
- **Node Manipulation**: The `PushBack`, `PushFront`, `PopBack`, and `PopFront` methods allow you to add and remove nodes from the list.
- **List Information**: The `Size` and `Empty` methods provide information about the list.
- **Intrusive List Support**: The implementation allows you to embed the linked list structure directly within your own structs, enabling efficient memory usage and manipulation without the need for separate node types.

## Doubly Linked List
  
Doubly linked list is created with: 
  
- `NewSyncLinked[T]()`: Creates a new **synced** linked list (all operations are blocking).
- `list.Linked[T]{}`: Creates a new **unsynced** linked list  
  
Here is a list of available methods with their descriptions:
  
  
- `PushBack(val T)`: Adds a new node with the given value at the end of the list.
- `PushFront(val T)`: Adds a new node with the given value at the beginning of the list.
- `PopBack() (T, bool)`: Removes the last node from the list and returns its value and a boolean indicating success.
- `PopFront() (T, bool)`: Removes the first node and returns its value and a boolean indicating success.
- `Head() *Node[T]`: Returns the first node of the list.
- `Tail() *Node[T]`: Returns the last node of the list.
- `Size() int`: Returns the number of nodes in the list.
- `Empty() bool`: Checks if the list is empty.
- `Begin(yield func(T) bool)`: Iterates over the list from the head to the tail.
- `End(yield func(T) bool)`: Iterates over the list from the tail to the head.
- `Val() T`: Returns the value of the node.
- `Next() *Node[T]`: Returns the next node.
- `Prev() *Node[T]`: Returns the previous node.

## Intrusive Singly Linked List

Intrusive Singly Linked List is created with: 
  
```go
type S struct { // suppose this is your struct
    a, b int // define your struct innies
    *list.List[S] // embed the List structure inside your package
}
```
  
Here is a list of available methods with their descriptions:
  
  
- `Next() *T`: returns a pointer to the next element in the linked list.
- `SetNext(next *T)`: assigns the 'next' pointer to the provided element, effectively making 'next' the subsequent element in the list.
- `InsertNext(elem *T)`: InsertNext() inserts the provided element 'elem' as the subsequent element in the list. The element that was previously next becomes the next element of 'elem'.
- `RemoveNext()`: detaches the next element from the list. The element following the next element (if it exists) becomes the new next element.
  
## Usage Example
  
Here is a simple usage example: [try here](https://go.dev/play/p/xQwBpUEaT3r)

```go
import (
	"fmt"
	"github.com/koss-null/list"
)

func foo() {
	// Create a new linked list
	ll := list.Linked[int]{}

	// Add elements to the list
	ll.PushBack(1)
	ll.PushBack(2)
	ll.PushBack(3)
	// The list contains: 1, 2, 3

	// Print the elements of the list
	for val := range ll.Begin {
		fmt.Println(val)
	}

	// Remove an element from the list
	val, ok := ll.PopBack()
	if ok {
		fmt.Printf("Popped value: %d\n", val)
		// Prints: Popped value: 3
	}

	// Print the size of the list
	fmt.Printf("List size: %d\n", ll.Size())
	// Prints: 2
}
```

## Intrusive List Usage Example

This library also supports **intrusive** singly linked lists if you want to imbed it in your own structure. Here is the example: [try here](https://go.dev/play/p/NMTOWaMQFaY)

```go
import (
	"fmt"
	"github.com/koss-null/list"
)

type S struct {
	a, b int
	*list.List[S]
}

func NewS(a, b int) *S {
    return &S{a: a, b: b, List: &list.List[S]{}}
}

func foo() {
	// Create a new linked list
	head := NewS(1, 2)
	cur := head

	// Add elements to the list
	cur.SetNext(NewS(3, 4))
	cur = cur.Next()
	cur.SetNext(NewS(5, 6))

	// Print the elements of the list
	for node := head; node != nil; node = node.Next() {
		fmt.Println(node.a, node.b)
	}
	// 1 2 3 4 5 6

	// Remove an element from the list
	head.RemoveNext()

	// Print the elements of the list after removal
	for node := head; node != nil; node = node.Next() {
		fmt.Println(node.a, node.b)
	}
	// 1 2 5 6
}
```

## Contributing 

Contributions are welcome! Please feel free to submit a Pull Request.


The Best Go Libraries For Data Structures and Algorithms - Queues (9)

memlog

queue

deque

goconcurrentqueue

deque

deheap

dqueue

hatchet

list