Ответ
Связный список (Linked List) — это базовая динамическая структура данных, состоящая из последовательности узлов (nodes).
Каждый узел содержит две части:
- Данные (Data): Полезная информация, которую хранит узел.
- Указатель (Next): Ссылка на следующий узел в последовательности. У последнего узла указатель равен
nil.
В двусвязном списке узел также содержит указатель на предыдущий узел (Prev).
Структура узла в Go:
// Узел для односвязного списка
type Node struct {
data int
next *Node
}Ключевые характеристики и отличия от массива/слайса:
| Характеристика | Связный список | Массив / Слайс |
|---|---|---|
| Хранение в памяти | Элементы хранятся вразброс, связаны указателями. | Элементы хранятся в непрерывном блоке памяти. |
| Доступ к элементу | Последовательный, O(n). Нужно пройти все узлы от начала. |
Прямой по индексу, O(1). |
| Вставка/Удаление | Эффективно в начале/конце (O(1)), если есть указатели на голову/хвост. |
Неэффективно в начале/середине (O(n)), требует сдвига элементов. |
| Размер | Динамический, легко изменяется во время выполнения. | В Go слайсы динамические, но расширение может вызвать переаллокацию всего массива. |
| Доп. память | Требует дополнительную память для хранения указателей. | Не требует доп. памяти на указатели между элементами. |
Вывод: Связные списки идеально подходят для задач, где часто выполняются операции вставки/удаления элементов, а доступ по индексу не требуется (например, реализации стека или очереди).