Почему Стек <T> и Очередь <T> реализован с массивом?
Я читаю C# 4.0 вкратце братьями Albahari, и я столкнулся с этим:
Стеки реализованы внутренне с массивом, это изменено как требуется, как с Очередью и Списком. (pg 288, абзац 4)
Я не могу не задаться вопросом почему. LinkedList обеспечивает O (1), голова и хвост вставляют и удаляют (который должен работать хорошо на стек или очередь). Массив изменяемого размера имеет O (1) амортизируемый, вставляют (если я помню право), но O (n) худший случай (я не уверен в, удаляют). И это, вероятно, использует больше пространства, чем связанный список (для больших стеков/очередей).
Существует ли больше к нему, чем это? Что оборотная сторона к реализации двунаправленного связанного списка?
2 ответа
но O (n) наихудший случай
наихудший случай с амортизацией по-прежнему O (1). Долгое и короткое время вставки усредняется - в этом весь смысл амортизированного анализа (и то же самое для удаления).
Массив также использует на меньше места, чем связанный список (который, в конце концов, должен хранить дополнительный указатель для каждого элемента).
Кроме того, накладные расходы намного меньше, чем при использовании связанного списка. В общем, реализация на основе массива просто (намного) более эффективна почти для всех случаев использования, даже если время от времени доступ будет занимать немного больше времени (фактически, очередь может быть реализована немного более эффективно, если взять преимущество страниц, которые сами управляются в связанном списке - см. реализацию C ++ std :: deque ).
Вот приблизительная оценка ресурсов памяти, используемых для стека из 100 System.Int32 s:
Для реализации массива потребуется следующее:
type designator 4 bytes
object lock 4
pointer to the array 4 (or 8)
array type designator 4
array lock 4
int array 400
stack head index 4
---
Total 424 bytes (in 2 managed heap objects)
A Для реализации связанного списка потребуется следующее:
type designator 4 bytes
object lock 4
pointer to the last node 4 (or 8)
node type designator 4 * 100 = 400
node lock 4 * 100 = 400
int value 4 * 100 = 400
pointer to next node 4 (or 8) * 100 = 400 (or 800)
-----
Total 1,612 bytes (in 101 managed heap objects)
Основным недостатком реализации массива будет копирование массива, когда его нужно расширить. Игнорируя все другие факторы, это будет операция O (n), где n - количество элементов в стеке. Это кажется довольно плохим, за исключением двух факторов: этого почти никогда не происходит, поскольку расширение удваивается при каждом приращении, а операция копирования массива сильно оптимизирована и работает потрясающе быстро. Таким образом, на практике расширение легко заменяется другими операциями со стеком.
Аналогично с очередью.