Комментарии 31
Всё вперемешку. Ужас.
Очередь и стек — самостоятельные структуры данных? Ничего, что их можно реализовать и поверх массива, и поверх списка — с разными свойствами соответственно?
Мапа, сет, дерево, хэш-таблица на одном уровне? "Раньше я думал, что Карл Маркс и Фридрих Энгельс — муж и жена, а теперь я знаю, что это четыре разных человека" :-)
Рано вам кого-то учить.
- Не будет выделений/освобождений в куче на каждый чих — существенный выигрыш. И вообще нет кучи мелких кусочков памяти, выделенных в куче, всё лежит локально (и удобно попадает в кэш проца для задач, где стек используется активно)
- Если не выделить сразу сколько надо памяти — иногда (например, при каждом удвоении размера массива) придётся реаллоцировать, тут мы проиграем (в среднем быстродействие всё равно выше, чем у списка, но иногда операция добавления элемента может оказаться долгой — в некоторых задачах это неприемлемо)
В общем, редко когда имеет смысл делать очередь или стек на списке.
Кстати, напомню об ещё одной структуре для хранения вектора переменного размера: массив массивов (или список массивов). Позволяет объединить плюсы обоих подходов за счёт некоторого усложнения кода, но нужен редко.
Из той же серии, массивы предпочтительнее списков в играх для хранения объектов, потому что создание\удаление объектов на сцене редкая операция, а итерация по ним происходит каждый кадр понесколько раз.
Из смешного по теме: в C# класс List — на самом деле массив, реальный список — LinkedList. Вот до такой степени MS верит в преимущество массивов в большинстве случаев.
LinkedList ― это конкретно «связный список».
Просто «список», без уточнений ― это абстрактная упорядоченная коллекция нефиксированного размера, которая реализована может быть как угодно. Когда термин «список» встречается в описании какого-нибудь алгоритма, если нет уточнений, лучше его именно так абстрактно и понимать.
Глядите. Очередь/стек — это не конкретная структура, а объект, реализующий две операции: положить в очередь (push) и взять из очереди (pull). Для очереди порядок выдаются объекты в том же порядке — FIFO (First In First Out), для стека в обратном — LIFO (Last In First Out). Ну, есть ещё очередь с приоритетами — это когда первым выдаёт объект с наивысшим приоритетом.
Итого, если мы сделали нечто, умеющее правильно выполнять эти операции — это очередь :-)
Варианты реализации (на примере LIFO очереди):
- Связный список. Ну, тут всё просто: push добавляет объект к концу списка, pull берёт из начала (и выкидывает этот объект из списка). Сложность обеих операций O(1), но надо выделять память на каждый push.
- Массив. Если ограничить длину очереди — поверх массива делается кольцевой буфер: указатели на "голову" и "хвост" очереди.
- push — кладём элемент на место, куда указывает хвост, сдвигаем указатель на 1 элемент направо (возвращаясь к началу массива, если перешли за конец).
- pull — берём элемент из места, куда указывает голова, сдвигаем голову на 1 направо (опять же "закольцевав" движение)
- Сложность обеих операций опять же O(1), но нет выделения памяти на каждый чих — работает быстрее.
- В варианте 2 размер ограничен, если нужен неограниченный — при заполнении массива увеличиваем его — точнее, выделяем новый и копируем туда все данные. Удобно увеличивать размер ровно в два раза, тогда получаем амортизированную сложность (т.е. в среднем по куче операций) опять же O(1), но вот в худшем случае (когда увеличиваем массив) уже O(n).
Ну, можно придумать ещё кучу других реализаций, но это самые распространённые.
Как-то прожил и даже заработал на бублики, зная только половину. Скажу так: для начинающих слишком сложно, для продолжающих гуглится по мере необходимости. Заранее забивать себе всем этим голову нужды нет.
(особенно тщательно офигел от «заземления» «связного списка»… Я за свою трудовую биографию, кроме того, что был программистом, еще был и чуть-чуть энергетиком с группой допуска… Заземление связного списка — это сильно!
Я бы не додумался. Надо изучить электричество тщательно. Вдруг заземление, которое возводится в абсолют энергетиками, это действительно просто нулевой указатель?..)
Просто может где-нибудь сноску сделать что для того что-бы что-то удалить нужно это найти еще, а если вставлять то пройтись по всему списку сначала.
Извиняюсь за конфуз.
Если список связан только в одну сторону, как в примере, удалить элемент за О(1) можно только имея заранее приготовленную ссылку на предыдущий элемент (под итератором, к примеру). Если для удаления есть только ссылка на текущий элемент, взятая со стороны — или надо иметь двустороннюю связь, или удаляется за О(n), так как нам реально нужен предыдущий элемент списка.
// Предполагается, что список имеет вид
// struct node {
// node* next;
// std::unique_ptr<data> data;
// };
//
// Последний элемент списка имеет поле next == nullptr
// В конце списка может быть не более одного "мусорного" элемента с полем data == nullptr - он ничего не означает и с логической точки зрения элементом списка не является
// Единственный аргумент - удаляемый элемент списка
void erase(node& to_delete) {
if (to_delete.next == nullptr) {
// Нужно удалить последний элемент - превращаем себя в sentinel
to_delete.data = nullptr;
} else {
// Общий случай - перемещаем следующий элемент в себя, после чего уничтожаем следующий
to_delete.data = std::move(to_delete.next->data);
to_delete.next = to_delete.next->next;
delete to_delete.next;
}
}
А для не начинающих слишком раздражительно детская подача материалами, с попытками смехуечности и вот этого вот.
10 типов структур данных, которые нужно знать + видео и упражнения