🦫Реализация односвязного списка в Golang

Связные списки — это фундаментальные структуры данных информатики и программирования, часто применяемые для хранения и управления набором данных, элементы которого не хранятся в смежных участках памяти. Рассмотрим реализацию односвязного списка на Go.

Введение в односвязные списки

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

У односвязного списка:

⬅️ В каждом узле содержатся данные.
⬅️ В каждом узле имеется ссылка — указатель next  — на следующий узел последовательности.
⬅️ В последнем узле обычно имеется ссылка nil, которой указывается на конец списка.

Узел — основа связного списка
В сердце связного списка находится понятие узла.

УЗЕЛ — ЭТО СТРОИТЕЛЬНЫЙ БЛОК ИЛИ КОНТЕЙНЕР, В КОТОРОМ СОДЕРЖАТСЯ: 1) СОХРАНЯЕМЫЕ ДАННЫЕ — ЧТО БЫ ВЫ НИ ВЫБРАЛИ — И 2) УКАЗАТЕЛЬ НА ТО, ЧТО СЛЕДУЕТ ДАЛЬШЕ.

Этой простой структурой формируется основа для создания односвязных — с последовательно связанными узлами — списков и двусвязных, где у узлов имеются ссылки на следующий и предыдущий узлы:

type Node struct {
data int
next *Node
}

type LinkedList struct {
head *Node
}

Структура Node здесь фундаментальный строительный блок односвязного списка. В ней инкапсулируются основные компоненты каждого узла списка:

▪️Поле data  — это хранимые в узле данные или значение. Мы задали ему целочисленный int, хотя на практике это может быть любой тип данных, необходимый конкретному приложению.
▪️Поле next  — это ссылка или указатель на следующий узел связанного списка. Ею узлы связываются в последовательную цепочку. Когда узел в списке последний, полем next указывается на nil  — конец списка.

Фактически структурой Node определяется, как выглядит отдельный элемент связного списка — с данными, которые в нем содержатся, и ссылкой на следующий элемент.

Структура LinkedList  — это связный список в целом, ею управляется набор узлов:

▪️Поле head  — ссылка или указатель на первый узел связного списка. Это точка входа в список, через которую получается доступ ко всей последовательности узлов для манипулирования ими.
Вместе структуры Node и LinkedList  — основа односвязного списка на Go. Структурой Node определяется то, как структурируются отдельные элементы, структурой LinkedList  — как эти элементы организуются в целостную структуру данных.

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

Вставка данных в связный список

📌Читать

@Golang_google

🖥 CspChan

Чистая реализация каналов Go на C89, включая блокирующие и неблокирующие селекты

https://github.com/rochus-keller/CspChan

@Golang_google

🖥 KubeGPT

Новый инструмент оповещения об ошибках Kubernetes на основе Go с интеграцией GPT для Slack!

📌 Github

@Golang_google

🖥 Dive

Полезный инструмент для изучения Docker-образа, содержимого слоев и поиска способов уменьшения размера Docker-образа
Docker/OC 🔥

https://github.com/wagoodman/dive

@Golang_google

👣 Go 1.22: интерактивные заметки c кодом

Основано на заметках о выпуске Go 1.22 от команды Go (лицензия 3-Clause BSD), с добавлением множества интерактивных примеров. Эта запись в блоге синхронизируется с исходным документом по мере его обновления.

Выход Go 1.22 запланирован на февраль 2024 года, но вы уже можете опробовать многие из его возможностей, не выходя из браузера. Читайте дальше и смотрите!

https://antonz.org/go-1-22/

#golang #programming

@Golang_google

🦦 Otter

Самая быстрая библиотека golang in-memory cache, основанная на алгоритме S3-FIFO. Раюотает во много раз быстрее, чем Ristretto.

Внутри используется хеш таблица, которая имеет мьютекс на каждый бакет + seq lock для чтения + каждый бакет помещается в две кеш линии, что предотвращает false sharing и это намногооо быстрее map с мьютексом и sync.Map.
Также исрользуется несколько трюков для избегания частых локов политики вытеснения: при чтении используются wait-free буфферы, которые иногда могут терять данные, но так как главная задача кеша - хранить наиболее частые элементы, то потери незначительны + реализация mpsc очереди при записи, которая значительно превосходит каналы по перфомансу и принцип из статьи bp-wrapper, который коротко можно назвать "batch, batch, batch" aka кеш не обновляет политику мгновенно, а только после наполнения небольшого буффера.

go get -u github.com/maypok86/otter

▪Github

@Golang_google

👣 SMTP-клиент Go CLI

Очень легкий CLI SMTP-клиент для удобной отправки писем из командной строки.

▪Github

@Golang_google

👣 DynamoMQ

DynamoMQ - это библиотека очередей сообщений, использующая DynamoDB в качестве хранилища, написанная на Go.

$ go install github.com/vvatanabe/dynamomq/cmd/dynamomq@latest

▪Github

@Golang_google

⚡️ Антипаттерны архитектуры

Откройте для себя распространенные антишаблоны архитектуры, узнайте, как их избегать и преодолевать "подводные камни" проектирования!

Антипаттерн (англ. anti-pattern) — это распространённый подход к решению класса часто встречающихся проблем, являющийся неэффективным, рискованным или непродуктивным. В отличие от шаблона проектирования, рассмотрение антипаттерна включает в себя как неправильное решение проблемы с его признаками и последствиями, так и выход из ситуации.

В этом проекте собраны ценные сведения, практические советы и примеры из реальных проектов для обучения и помощи в создании лучших программных архитектур и улучшать существующие.

▪Проект
▪Github

@Golang_google

🖥 Cursus Database System

Если бы у MongoDB и MySQL родился ребенок, то это был бы CursusDB. Шутки в сторону CursusDB - это распределенная документо-ориентированная in-memory база данных с открытым исходным кодом и SQL-подобным языком запросов, написанным на чистом GO.

▪Github
▪Документация

@Golang_google