Структуры данных: связанные списки
Связанные списки — структура данных, элемент которой содержит собственные данные, так и одну или две ссылки на следующий и/или предыдущий элемент. Связанный список работает как массив, который растет и уменьшаться при необходимости из произвольной точки массива.
Наиболее используемые типы списков:
- Односвязный список
+-------+------+ +-------+-------+
| Hello | *---+--->| world | null +
+-------+------+ +-------+-------+- Двусвязный список
+----------+---------+ +----------+----------+
| | *---|------>| | |
| Hello | | | | world |
| | |<------|---* | |
+----------+---------+ +----------+----------+- Кольцевой список
. +-------<----------<--------------<--------+
| |
+-----+--+---+ +-----+------+ +-----+-----+ |
| 12 | *---+--->| 15 | *--+--->| 25 | *--+---+
+-----+------+ +-----+------+ +-----+-----+
Быстродействие
- Добавляет элемент в конец/начало списка — O(1)
- Удаляет первый элемент списка со значением, равным переданному — O(n)
- Поиск элемента — O(n)
- Копирование а массив — O(n)
- Получить количество — O(1)
Преимущества
- Элементы могут быть удалены или добавлены из середины списка
- Нет необходимости объявлять разvер списка при инициализации
- Эффективное удаление и добавление элементов
Недостатки
- Связанные списки не имеют возможности произвольного доступа к элементам — т. е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него.
- Для работы списков требуется динамическое выделение памяти, что может привести к утечкам памяти.
Ссылки
