Связный список - это линейная структура данных, в которой элементы не хранятся в смежных ячейках памяти. Вместо этого каждый элемент, называемый узлом, содержит данные и ссылку (или указатель) на следующий узел в последовательности.
Существуют различные типы связных списков:
- Односвязный список: Каждый узел содержит ссылку только на следующий узел.
- Двусвязный список: Каждый узел содержит ссылки как на следующий, так и на предыдущий узел.
- Циклический связный список: Последний узел ссылается на первый узел, образуя цикл.
Основные операции над связным списком:
- Вставка: Добавление нового узла в список.
- Удаление: Удаление узла из списка.
- Поиск: Поиск узла по значению.
- Обход: Последовательный доступ ко всем узлам списка.
Преимущества:
- Гибкость вставки и удаления элементов в любой позиции.
- Эффективное управление памятью, так как элементы не требуют непрерывных блоков.
Недостатки:
- Медленный произвольный доступ к элементам (требуется последовательный обход).
- Требуется дополнительная память для хранения ссылок.
Пример структуры узла в односвязном списке:
java