Зачем мне когда-либо использовать DoublyLinkedList в PHP?

Question

Недавно я столкнулся с некоторыми структурами данных PHP-SPL, и я просматривал первую, двусвязный список .У меня есть приблизительное представление о том, что такое связанный список, и теперь я вижу, что такое двухсвязный список, но у меня вопрос: что бы я сделал с этим?

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

Answer 1

В отличие от односвязного списка, двусвязный список может перемещаться по списку в любом направлении и выполнять вставку и удаление объекта в середине списка в O (1) (при условии, что у вас уже есть доступ к месту в списке где это произойдет, в отличие от односвязных списков. Тем не менее, двусвязные списки уступают в других отношениях и явно не являются тем, с чем вы часто сталкиваетесь на практике.

Answer 2

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

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

Но может быть такая «промежуточная» область, где использование одной из структур данных Spl достаточно снижает использование памяти, чтобы быть достойным использования. (Я провел простой тест, и 1M целых чисел в массиве занимает 200 МБ. Двойной связанный список занимает 150 МБ. Время их перебора было очень сопоставимым.)

Answer 3

ИМХО, шансы встретить что-то подобное в дикой природе маловероятны, если только вы не работаете в такой компании, как Google или Facebook, где они имеют дело с безумными объемами данных и нуждаются в необходимости , чтобы оптимизировать обход списка, чтобы учесть удаление и добавление узла.Как правило, если ваше приложение медленное , вы, скорее всего, делаете что-то не так в другом месте (я знаю, что это не ваш вопрос, но я подумал, что просто добавлю это;)).

Для сайтов малого и среднего размера с требованиями к данным малого и среднего размера, я бы сказал, что массива будет достаточно (не говоря уже о том, чтобы его читали и понимали среднестатистические разработчики;)).