go-collections: структуры данных для Go с поддержкой дженериков

Введение

Язык программирования Go предоставляет базовые контейнеры, но часто разработчикам необходимы более специализированные структуры данных. Пакет go-collections предлагает реализации распространенных структур данных с поддержкой дженериков, что делает код более выразительным и удобным.

В этой статье мы подробно рассмотрим возможности пакета go-collections, его установку и примеры использования различных структур данных.

!В комментариях написали, что нужно упомянуть, что это моя библиотека, иначе я каким-то образом ввожу людей в заблуждение!

---

1. Установка

Для установки пакета используйте систему модулей Go:

go get github.com/idsulik/go-collections

После установки вы можете импортировать необходимые структуры данных в своем коде.

---

2. Обзор структур данных

Пакет go-collections предоставляет следующие структуры данных:

Deque (Двухсторонняя очередь)

Описание:

Deque (Double-ended queue) — это структура данных, которая позволяет добавлять и удалять элементы как с начала, так и с конца. Реализована на основе циклического буфера, что позволяет эффективно использовать память и поддерживать амортизированную константную сложность операций.

Конструктор:

func New[T any](initialCapacity int) *Deque[T]

Методы:

• PushFront(item T): Добавляет элемент в начало очереди.

• PushBack(item T): Добавляет элемент в конец очереди.

• PopFront() (T, bool): Удаляет и возвращает элемент из начала очереди.

• PopBack() (T, bool): Удаляет и возвращает элемент из конца очереди.

• PeekFront() (T, bool): Возвращает элемент из начала очереди без удаления.

• PeekBack() (T, bool): Возвращает элемент из конца очереди без удаления.

• Len() int: Возвращает количество элементов в очереди.

• IsEmpty() bool: Проверяет, пуста ли очередь.

• Clear(): Очищает очередь.

Сложность:

• Амортизированная сложность: O(1) для всех методов.

• Наихудший случай: O(n) при необходимости расширения буфера.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/deque"
)

func main() {
    d := deque.New[int](0)
    d.PushBack(1)
    d.PushFront(2)

    front, _ := d.PopFront()
    back, _ := d.PopBack()

    fmt.Println(front) // Вывод: 2
    fmt.Println(back)  // Вывод: 1
}

Set (Множество)

Описание:

Set — это неупорядоченная структура данных, которая хранит только уникальные значения. Множества обеспечивают быстрый доступ, добавление и удаление элементов, используя хеш-таблицы для управления уникальностью.

Конструктор:

func New[T comparable]() *Set[T]

Методы:

• Add(item T): Добавляет элемент в множество.

• Remove(item T): Удаляет элемент из множества.

• Has(item T) bool: Проверяет наличие элемента.

• Clear(): Очищает множество.

• Len() int: Возвращает количество элементов.

• IsEmpty() bool: Проверяет, пусто ли множество.

• Elements() []T: Возвращает срез всех элементов.

• AddAll(items ...T): Добавляет несколько элементов.

• RemoveAll(items ...T): Удаляет несколько элементов.

• Diff(other *Set[T]) *Set[T]: Разница множеств.

• Intersect(other *Set[T]) *Set[T]: Пересечение множеств.

• Union(other *Set[T]) *Set[T]: Объединение множеств.

• IsSubset(other *Set[T]) bool: Проверяет, является ли подмножеством.

• IsSuperset(other *Set[T]) bool: Проверяет, является ли надмножеством.

• Equal(other *Set[T]) bool: Проверяет равенство множеств.

Сложность:

• Сложность для Add, Remove, Has, Len, IsEmpty, AddAll, RemoveAll: O(1) в среднем случае, благодаря хеш-таблицам.

• Сложность для Elements: O(n), где n — количество элементов в множестве.

• Сложность для операций Diff, Intersect, Union, IsSubset, IsSuperset, Equal: O(n), где n — количество элементов в наибольшем множестве.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/set"
)

func main() {
    s := set.New[int]()
    s.Add(1)
    s.Add(2)
    s.Add(2) // Дубликат не добавится

    fmt.Println(s.Elements()) // Вывод: [1 2]
}

LinkedList (Односвязный список)

Описание:

Односвязный список — это линейная структура данных, в которой элементы связаны последовательно, где каждый элемент (узел) содержит значение и ссылку на следующий элемент. Односвязные списки позволяют добавлять и удалять элементы с начала и конца списка.

Конструктор:

func New[T any]() *LinkedList[T]

Методы:

• AddFront(value T): Добавляет элемент в начало списка.

• AddBack(value T): Добавляет элемент в конец списка.

• RemoveFront() (T, bool): Удаляет и возвращает элемент из начала списка.

• RemoveBack() (T, bool): Удаляет и возвращает элемент из конца списка.

• Iterate(fn func(T) bool): Итерация по элементам списка.

• Size() int: Возвращает размер списка.

Сложность:

• Сложность для AddFront, AddBack, RemoveFront, Size: O(1) — операции выполняются за постоянное время, так как не требуют обхода списка.

• Сложность для RemoveBack: O(n), где n — количество элементов в списке, поскольку требуется пройти весь список до предпоследнего элемента.

• Сложность для Iterate: O(n), где n — количество элементов в списке, так как выполняется обход всех элементов.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/linkedlist"
)

func main() {
    list := linkedlist.New[int]()
    list.AddFront(1)
    list.AddBack(2)

    list.Iterate(func(value int) bool {
        fmt.Println(value)
        return true
    })
    // Вывод:
    // 1
    // 2
}

Queue (Очередь)

Описание:

Очередь — это структура данных типа FIFO (First-In, First-Out), в которой элементы добавляются в конец и удаляются из начала. Очередь обеспечивает базовые операции для управления элементами в порядке их поступления.

Конструктор:

func New[T any](initialCapacity int) *Queue[T]

Методы:

• Enqueue(item T): Добавляет элемент в конец очереди.

• Dequeue() (T, bool): Удаляет и возвращает элемент из начала очереди.

• Peek() (T, bool): Возвращает первый элемент без удаления.

• Len() int: Возвращает количество элементов.

• IsEmpty() bool: Проверяет, пуста ли очередь.

• Clear(): Очищает очередь.

Сложность:

• Сложность всех методов: O(1) амортизированная — благодаря использованию двусторонней очереди (Deque), операции выполняются за постоянное время.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/queue"
)

func main() {
    q := queue.New[int](0)
    q.Enqueue(1)
    q.Enqueue(2)

    item, _ := q.Dequeue()
    fmt.Println(item) // Вывод: 1
}

Stack (Стек)

Описание:

Стек — это структура данных типа LIFO (Last-In, First-Out), в которой последний добавленный элемент является первым, который будет удален. Стек поддерживает стандартные операции добавления и удаления элементов с верхушки.

Конструктор:

func New[T any](initialCapacity int) *Stack[T]

Методы:

• Push(item T): Добавляет элемент на вершину стека.

• Pop() (T, bool): Удаляет и возвращает элемент с вершины стека.

• Peek() (T, bool): Возвращает элемент с вершины без удаления.

• Len() int: Возвращает количество элементов.

• IsEmpty() bool: Проверяет, пуст ли стек.

• Clear(): Очищает стек.

Сложность:

• Сложность для Push, Pop, Peek, Len, IsEmpty: O(1) — операции выполняются за постоянное время.

• Сложность для Clear: O(n), где n — количество элементов в стеке, из-за необходимости обнуления всех ссылок в срезе.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/stack"
)

func main() {
    s := stack.New[int](0)
    s.Push(1)
    s.Push(2)

    item, _ := s.Pop()
    fmt.Println(item) // Вывод: 2
}

Trie (Префиксное дерево)

Описание:

Trie — это префиксное дерево, структура данных, которая поддерживает эффективную вставку и поиск слов и префиксов. Каждый узел дерева представляет символ, и пути в дереве образуют слова.

Конструктор:

func New() *Trie

Методы:

• Insert(word string): Добавляет слово в Trie.

• Search(word string) bool: Проверяет наличие слова.

• StartsWith(prefix string) bool: Проверяет наличие слов с заданным префиксом.

Сложность:

• Сложность всех методов: O(m), где m — длина слова или префикса. Операции зависят от длины входной строки, так как необходимо пройти по символам строки.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/trie"
)

func main() {
    t := trie.New()
    t.Insert("hello")
    t.Insert("helium")

    fmt.Println(t.Search("hello"))    // Вывод: true
    fmt.Println(t.StartsWith("he"))   // Вывод: true
    fmt.Println(t.Search("helix"))    // Вывод: false
}

Priority Queue (Приоритетная очередь)

Описание:

Приоритетная очередь — это структура данных, которая позволяет эффективно извлекать и удалять элементы с наивысшим (или наинизшим) приоритетом. Она поддерживает порядок элементов с использованием кучи (heap), что обеспечивает быстрый доступ к элементу с высшим приоритетом.

Конструктор:

func New[T any](less func(a, b T) bool) *PriorityQueue[T]

Параметры:

• less: Функция сравнения, определяющая приоритет элементов.

Методы:

• Push(item T): Добавляет элемент в очередь.

• Pop() (T, bool): Удаляет и возвращает элемент с наивысшим приоритетом.

• Peek() (T, bool): Возвращает элемент с наивысшим приоритетом без удаления.

• Len() int: Возвращает количество элементов.

• IsEmpty() bool: Проверяет, пуста ли очередь.

• Clear(): Очищает очередь.

Сложность:

• Сложность для Push, Pop: O(log n) — операции выполняются за логарифмическое время благодаря поддержанию свойств кучи при добавлении и удалении элементов.

• Сложность для Peek, Len, IsEmpty: O(1) — доступ к верхушке кучи и проверки выполняются за постоянное время.

• Сложность для Clear: O(n) — удаление всех элементов требует линейного времени, так как освобождается вся память.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/priorityqueue"
)

func main() {
    pq := priorityqueue.New[int](func(a, b int) bool {
        return a < b // Минимальный элемент имеет наивысший приоритет
    })

    pq.Push(3)
    pq.Push(1)
    pq.Push(2)

    item, _ := pq.Pop()
    fmt.Println(item) // Вывод: 1
}

Binary Search Tree (Двоичное дерево поиска)

Описание:

Двоичное дерево поиска (BST) — это структура данных, поддерживающая элементы в отсортированном порядке, что позволяет эффективно выполнять операции вставки, удаления и поиска. Каждая нода дерева имеет максимум два потомка: левый — для значений меньше текущего, и правый — для значений больше текущего.

Конструктор:

func New[T constraints.Ordered]() *BST[T]

Параметры:

• T constraints.Ordered: Тип данных, поддерживающий операции сравнения < и >.

Методы:

• Insert(value T): Вставляет значение в дерево.

• Remove(value T): Удаляет значение из дерева.

• Contains(value T) bool: Проверяет наличие значения.

• InOrderTraversal(fn func(T)): Обходит дерево в порядке возрастания.

• Len() int: Возвращает количество узлов.

• IsEmpty() bool: Проверяет, пусто ли дерево.

• Clear(): Очищает дерево.

Сложность:

• Сложность для Insert, Contains, Remove: O(h), где h — высота дерева. В худшем случае (несбалансированное дерево) сложность может быть O(n), где n — количество узлов, но в среднем случае для сбалансированных деревьев — O(log n).

• Сложность для InOrderTraversal: O(n) — необходимо обойти все узлы.

• Сложность для Len, IsEmpty: O(1) — получение текущего размера или проверки выполняются за постоянное время.

• Сложность для Clear: O(1) — ссылки на корень и размер просто обнуляются.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/bst"
)

func main() {
    tree := bst.New[int]()
    tree.Insert(2)
    tree.Insert(1)
    tree.Insert(3)

    tree.InOrderTraversal(func(value int) {
        fmt.Println(value)
    })
    // Вывод:
    // 1
    // 2
    // 3
}

Skip List (Список с пропусками)

Описание:

Skip List — это вероятностная структура данных, которая обеспечивает быстрый поиск, вставку и удаление элементов за счет использования нескольких уровней связей, что позволяет пропускать части списка. Skip List является альтернативой сбалансированным деревьям поиска и поддерживает элементы в отсортированном порядке.

Конструктор:

func New[T constraints.Ordered](maxLevel int, p float64) *SkipList[T]

Параметры:

• maxLevel: Максимальный уровень списка.

• p: Вероятность, определяющая уровень новых узлов (обычно 0.5).

Методы:

• Insert(value T): Вставляет значение.

• Delete(value T): Удаляет значение.

• Search(value T) bool: Ищет значение.

• Len() int: Возвращает количество элементов.

• IsEmpty() bool: Проверяет, пуст ли список.

• Clear(): Очищает список.

Сложность:

• Сложность для Insert, Search, Delete: O(log n) в среднем случае — за счет вероятностного распределения уровней узлов и их связей.

• Сложность для Len, IsEmpty: O(1) — получение текущего размера или проверка выполняются за постоянное время.

• Сложность для Clear: O(1) — обнуляются ссылки на заголовочный узел и счетчики.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/skiplist"
)

func main() {
    sl := skiplist.New[int](16, 0.5)
    sl.Insert(1)
    sl.Insert(2)
    sl.Insert(3)

    fmt.Println(sl.Search(2)) // Вывод: true
    sl.Delete(2)
    fmt.Println(sl.Search(2)) // Вывод: false
}

Graph (Граф)

Описание:

Графы представляют собой сети узлов и ребер, подходящие для различных алгоритмов, таких как поиск путей и построение остовных деревьев.

Конструктор:

func New[T comparable](directed bool) *Graph[T]

Параметры:

• directed: Указывает, является ли граф ориентированным.

Методы:

• AddNode(value T): Добавляет узел.

• AddEdge(from, to T, weight float64): Добавляет ребро с опциональным весом.

• RemoveNode(value T): Удаляет узел и связанные ребра.

• RemoveEdge(from, to T): Удаляет ребро.

• Neighbors(value T) []T: Возвращает соседние узлы.

• HasNode(value T) bool: Проверяет наличие узла.

• HasEdge(from, to T) bool: Проверяет наличие ребра.

• GetEdgeWeight(from, to T) (float64, bool): Получает вес ребра.

• Traverse(start T, visit func(T)): Обходит граф от начального узла (BFS).

• Nodes() []T: Возвращает все узлы.

• Edges() [][2]T: Возвращает все ребра.

Сложность:

• Сложность для AddNode, AddEdge, RemoveNode, RemoveEdge: O(1) в среднем случае для операций с узлами и ребрами благодаря использованию хеш-таблиц.

• Сложность для Neighbors, HasNode, HasEdge, GetEdgeWeight: O(1) в среднем случае при доступе к элементам через хеш-таблицы.

• Сложность для Traverse: O(V + E), где V — количество узлов, E — количество ребер, так как необходимо пройти все узлы и ребра.

• Сложность для Nodes, Edges: O(V) и O(E) соответственно, так как требуется собрать все узлы или ребра.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/graph"
)

func main() {
    g := graph.New[string](false)
    g.AddNode("A")
    g.AddNode("B")
    g.AddEdge("A", "B", 1.0)

    fmt.Println(g.HasEdge("A", "B")) // Вывод: true
}

---

3. Практические примеры

Пример 1: Использование Priority Queue для планирования задач

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/priorityqueue"
)

type Task struct {
    name     string
    priority int
}

func main() {
    pq := priorityqueue.New[Task](func(a, b Task) bool {
        return a.priority < b.priority
    })

    pq.Push(Task{"Task1", 3})
    pq.Push(Task{"Task2", 1})
    pq.Push(Task{"Task3", 2})

    for !pq.IsEmpty() {
        task, _ := pq.Pop()
        fmt.Printf("Executing %s with priority %d\n", task.name, task.priority)
    }
    // Вывод:
    // Executing Task2 with priority 1
    // Executing Task3 with priority 2
    // Executing Task1 with priority 3
}

Пример 2: Поиск слов в Trie

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/trie"
)

func main() {
    dictionary := trie.New()
    words := []string{"go", "golang", "gopher", "goroutine"}

    for _, word := range words {
        dictionary.Insert(word)
    }

    fmt.Println(dictionary.Search("golang"))    // Вывод: true
    fmt.Println(dictionary.Search("python"))    // Вывод: false
    fmt.Println(dictionary.StartsWith("go"))    // Вывод: true
}

---

4. Заключение

Пакет go-collections предоставляет широкий набор структур данных с поддержкой дженериков, что упрощает разработку и повышает производительность приложений на Go. Благодаря понятному API и богатому функционалу, этот пакет становится незаменимым инструментом для разработчиков.

---

Если у вас есть вопросы или предложения, пишите в комментариях!
Просьба поставить 🌟 для репозитория, если вы думаете, что пакет полезный.

p.s. Если вам нужна какая-то другая структура данных, то можете создать pull request или же напишите в комментариях, что вам нужно и я добавлю в репозиторий