Другие языки программирования и технологии

Нужно ли вообще создавать связной список в более высокоуровневых языках как PHP?

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

В PHP можно создавать массив любой длинны насколько я знаю, но возможно стандартные настройки задают ограничения. Есть ли смысл создавать связной список, если PHP и так предоставляет собственные средства? В PHP я могу спокойно объявить массив и добавлять в него данные, в начало, конец или хоть в середину.
ЖЛ
Женя Людин
51
Раз в PHP уже есть встроенный список https://www.php.net/manual/ru/class.spldoublylinkedlist.php, значит это кому-то нужно. Проблема массива в том, что вставка в его средину - это очень затратная операция. И если требуется много таких действий, код будет работать очень медленно.

Советую заглянуть в https://www.php.net/manual/ru/book.spl.php - узнаешь много нового о том, что "из коробки" есть в PHP.
СС
Сергей Седых
65 674
Лучший ответ
Женя Людин спасибо
Женя Людин "Кузнецов, Симдянов Самоучитель PHP 7 (2018)" нормальный учебник для освоения основ PHP?

Да я знаю php.net самый лучший PHP-шный учебный ресурс, но я его использую в качестве справочного материала, а мне нужен учебник в котором будет описываться не только теория, но и задания к каждым пройденным темам для закрепления.
"В C я могу понять, он там может пригодится, так как при объявлении массива в C изменить его длину потом невозможно, даже если это возможно, то нужно работать с выделением памяти, и перемещать данные в новую область памяти, сильно не углублялся в эту тему. "

Вообще-то даже в C можно заюзать какую-то библиотеку, содержащую уже готовый контейнер. Библиотека выбирается исходя из окружения (платформа, ОС). Такое есть даже в ядре NT. Хотя этот контейнер может быть как раз на связном списке реализован. Но всяко ведь лучше, чем свой собственный список. Готовый контейнер может обладать потокобезопасностью, к примеру. И да, все это на чистом Си!

А лучше C++. Там полно контейнеров, например vector по сути есть динамический массив без выделения памяти (точнее, все действия с памятью у него под капотом)
Иван Решетнев
Иван Решетнев
92 464
При объявлении массива в Си при необходимости изменить его длину его всегда можно перевыделить и скопировать данные в новое место, а старую память освободить. Динамические массивы именно так и работают, просто в языках высокого уровня это реализовано "под капотом" на уровне стандартной библиотеки.

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

Собсна, пыху я не знаю, но что-то вот такое вот гуглится:
https://www.php.net/manual/ru/class.spldoublylinkedlist.php
Vitaly Popov
Vitaly Popov
36 956
Женя Людин Это я знаю.

На счёт того что вставка в середину выполняется за O(1) я сомневаюсь, ибо чтобы что-то вставить с связной список, особенно в конец или в середину необходимо пройтись от начала списка до нужного места, а именно до середины, а это уже время O(n). Но в любом случае вставка в связном списке происходит быстрее, чем в массивах.
Женя Людин В конец можно добавить за время и O(1) если всё оптимизировать и хранить указатель на конец списка, а вот в середину или в определенное указанное время навряд ли.
Женя Людин ошибка "но и это уже O(1)" исправленная версия "но и это уже O(n)"

Похожие вопросы