В чем смысл класса PHP SplDoublyLinkedList и, что более важно, Linked Lists в целом?

Ответ 1

Структуры данных SPL уменьшают потребление памяти и повышают производительность. Хорошие объяснения:

Структуры данных по своей природе не зависят от языка и существуют как набор логических концепций, основанных на математике. Эти контейнеры используют различные алгоритмы, чтобы повысить эффективность.

Например, если вам не нужны возможности хэш-карты ассоциативного массива, т.е. если вы не используете ключ массива для определенной цели и вам нужен только нумерованный массив - SplFixedArray (ранее SplFastArray, в настоящее время недокументированная) может быть подходящей заменой. Единственное предостережение состоит в том, что размер массива фиксирован, что означает, что вы должны указывать размер при создании экземпляра класса, и ошибка будет возникать, если вы попытаетесь сохранить больше, чем это число элементов. Это связано с тем, что в среднем он работает лучше, чем стандартные массивы PHP.

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

Внутри кода C, составляющего интерпретатор PHP, массивы реализуются как структура данных, называемая хеш-таблицей или хэш-картой. Когда значение, содержащееся в массиве, ссылается на его индекс, PHP использует хеширующую функцию для преобразования этого индекса в уникальный хеш, представляющий местоположение соответствующего значения в массиве.

Эта реализация хэш-карты позволяет массивам хранить произвольное количество элементов и обеспечивать доступ ко всем этим элементам одновременно, используя либо числовые, либо строковые ключи. Массивы чрезвычайно быстрые для возможностей, которые они предоставляют, и являются отличной структурой данных общего назначения.

В информатике список определяется как упорядоченный набор значений. Связанный список - это структура данных, в которой каждый элемент в списке включает ссылку на один или оба элемента по обе стороны от него в списке. Термин "дважды связанный список" используется для обозначения последнего случая. В SPL это принимает форму класса SplDoublyLinkedList.... Имеет смысл использовать списки, когда количество элементов, которые должны быть сохранены, заранее неизвестно, и к элементам требуется только доступ к последовательной позиции.

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/

Ответ 2

Согласно Wikipedia,

Основное преимущество связанного списка над обычным массивом состоит в том, что порядок связанных элементов может быть отличается от того, что данные элементы хранятся в памяти или на диске. По этой причине связанные списки позволяют вставка и удаление узлов на любом точка в списке, с постоянной количество операций.

С другой стороны, связанные списки по сами не допускают случайный доступ к данным или любой форме эффективного индексации. Таким образом, многие основные операции - например, получение последнего nodeсписок или найти node, что содержит заданную дату или местоположение место, где должен быть новый nodeвставка - может потребоваться большинство сканирования элементов списка.

Итак, чтобы ответить на ваш вопрос, я понятия не имею.:)

Ответ 3

В первую очередь SplDoublyLinkedList - это объекты, как таковые

• они могут быть расширены, поэтому вы можете переопределить их методы (вы можете, например, вернуть все строки в верхнем регистре и т.д.)
• интерфейсы, которые они реализуют, можно проверить, как в myfunc( SplDoublyLinkedList $var ) ...
• они передаются как ссылка по умолчанию
• и др.

Во-вторых, SplDoublyLinkedList принимают режимы итерации, поэтому вы можете удалять свои объекты на ходу и переключать направление без переупорядочения массива или усложнения кода:

SplDoublyLinkedList:: IT_MODE_LIFO (стиль стека)

SplDoublyLinkedList:: IT_MODE_FIFO (стиль очереди). Поведение итератор (один или другой)

SplDoublyLinkedList:: IT_MODE_DELETE (Элементы удаляются итератор)

SplDoublyLinkedList:: IT_MODE_KEEP (Элементы пройдены итератор)

Вышеуказанная цитата из http://simpletechinfo.com/SplDoublyLinkedList, которая содержит некоторые примеры кода.

Есть другие льготы (например, foreach не нужно делать копию в памяти всех данных и т.д.)

Ответ 4

Они там, потому что для них используются многие программисты, работающие с другими языками, где массивы имеют фиксированные размеры, и вы должны заботиться о управлении памятью.
Поэтому для PHP это еще один инструмент. Они реализованы потому, что многие алгоритмы и ретрансляция шаблонов в списках и поэтому их не нужно менять на php-массивы.

Ответ 5

Как отмечали другие, списки являются альтернативой фиксированным массивам, которые распространены на других языках. Но один важный аспект, который часто упускается из виду - вы можете очень эффективно вставлять или удалять элемент из любого места в списке.

Почему это важно? Скажем, у вас есть несколько элементов, которые вы хотите сохранить отсортированными в массиве, возможно, поэтому вам не нужно сортировать их позже или просто для минимизации времени поиска. В этом случае List может быть очень мощным инструментом. Особенно для очень больших наборов данных.

Ответ 6

Возможно, вы правы, и это просто не очень полезно.

Существует множество применений связанных списков в теории (в частности, танцевальных ссылок). Но большинство из них связано с хранением и клонированием своих итераторов в другом месте, доступом к содержимому более чем в двух направлениях или разделением и объединением списков. У SplDoublyLinkedList, похоже, не было таких.

Если это не для алгоритмов, одно из них - позволить объекту удалять ссылку на себя в некотором списке в постоянное время, освобождая его память и не перетасовывая список (путем хэширования или замены с последним пунктом) после вставки или удаление. Но для этого требуется хранить итератор списка в этих объектах.

Без этих функций они просто ведут себя как два уважения. Если вам нужен только доступ к элементам с помощью итератора, они похожи на два стека. Один из лучших способов в однопоточных простых случаях, запрещающий уже не завернутый в класс, - это просто использовать два стека (возможно, фиксированные массивы или оба конца одного и того же массива). Поп из одного стека и нажимайте его на другой, когда хотите, чтобы итератор перемещался, а верхняя часть одного стека - это текущий элемент. Если вам также нужно получить доступ к голове и хвосту, вам нужно будет заменить стеки на deques.

Но если вы хотите сами реализовать стеки или deques, не зная максимального размера или даже назначать узлы обычных связанных списков (на языке без таких библиотек, как в PHP), хороший способ - связать некоторые фиксированные массивы вместе, используя двунаправленные списки без этих функций. Как-то вам все равно понадобится.

Сама документация PHP, как и Java, предполагает, что они должны быть просто деком, поддерживающими некоторые дополнительные странные функции, даже не два двух (я думаю). Не используйте их, если вам действительно нужны дважды связанные списки.