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