Не знаю имеет ли смысл создавать связной список на PHP и других языках более высокого уровня. В C я могу понять, он там может пригодится, так как при объявлении массива в C изменить его длину потом невозможно, даже если это возможно, то нужно работать с выделением памяти, и перемещать данные в новую область памяти, сильно не углублялся в эту тему. А вот связной список решает эту проблему в C и по мере добавления данных выделяется новая память для хранения нового узла.
В PHP можно создавать массив любой длинны насколько я знаю, но возможно стандартные настройки задают ограничения. Есть ли смысл создавать связной список, если PHP и так предоставляет собственные средства? В PHP я могу спокойно объявить массив и добавлять в него данные, в начало, конец или хоть в середину.
Другие языки программирования и технологии
Нужно ли вообще создавать связной список в более высокоуровневых языках как PHP?
Раз в PHP уже есть встроенный список https://www.php.net/manual/ru/class.spldoublylinkedlist.php, значит это кому-то нужно. Проблема массива в том, что вставка в его средину - это очень затратная операция. И если требуется много таких действий, код будет работать очень медленно.
Советую заглянуть в https://www.php.net/manual/ru/book.spl.php - узнаешь много нового о том, что "из коробки" есть в PHP.
Советую заглянуть в https://www.php.net/manual/ru/book.spl.php - узнаешь много нового о том, что "из коробки" есть в PHP.
"В C я могу понять, он там может пригодится, так как при объявлении массива в C изменить его длину потом невозможно, даже если это возможно, то нужно работать с выделением памяти, и перемещать данные в новую область памяти, сильно не углублялся в эту тему. "
Вообще-то даже в C можно заюзать какую-то библиотеку, содержащую уже готовый контейнер. Библиотека выбирается исходя из окружения (платформа, ОС). Такое есть даже в ядре NT. Хотя этот контейнер может быть как раз на связном списке реализован. Но всяко ведь лучше, чем свой собственный список. Готовый контейнер может обладать потокобезопасностью, к примеру. И да, все это на чистом Си!
А лучше C++. Там полно контейнеров, например vector по сути есть динамический массив без выделения памяти (точнее, все действия с памятью у него под капотом)
Вообще-то даже в C можно заюзать какую-то библиотеку, содержащую уже готовый контейнер. Библиотека выбирается исходя из окружения (платформа, ОС). Такое есть даже в ядре NT. Хотя этот контейнер может быть как раз на связном списке реализован. Но всяко ведь лучше, чем свой собственный список. Готовый контейнер может обладать потокобезопасностью, к примеру. И да, все это на чистом Си!
А лучше C++. Там полно контейнеров, например vector по сути есть динамический массив без выделения памяти (точнее, все действия с памятью у него под капотом)
При объявлении массива в Си при необходимости изменить его длину его всегда можно перевыделить и скопировать данные в новое место, а старую память освободить. Динамические массивы именно так и работают, просто в языках высокого уровня это реализовано "под капотом" на уровне стандартной библиотеки.
Связный список - совершенно другая структура данных, применяющаяся как раз тогда, когда динамический массив не применим, а не потому, что нам лень ручками реализовать вектор в условиях его отсутствия.
Из основных отличий - в списке доступ к произвольному элементу по его номеру осуществляется за O(n), а не за O(1), как в массиве, зато удаление или добавление элемента куда-нибудь в середину работает за O(1) и не портит ссылки на элементы справа и слева.
Собсна, пыху я не знаю, но что-то вот такое вот гуглится:
https://www.php.net/manual/ru/class.spldoublylinkedlist.php
Связный список - совершенно другая структура данных, применяющаяся как раз тогда, когда динамический массив не применим, а не потому, что нам лень ручками реализовать вектор в условиях его отсутствия.
Из основных отличий - в списке доступ к произвольному элементу по его номеру осуществляется за O(n), а не за O(1), как в массиве, зато удаление или добавление элемента куда-нибудь в середину работает за O(1) и не портит ссылки на элементы справа и слева.
Собсна, пыху я не знаю, но что-то вот такое вот гуглится:
https://www.php.net/manual/ru/class.spldoublylinkedlist.php
Женя Людин
Это я знаю.
На счёт того что вставка в середину выполняется за O(1) я сомневаюсь, ибо чтобы что-то вставить с связной список, особенно в конец или в середину необходимо пройтись от начала списка до нужного места, а именно до середины, а это уже время O(n). Но в любом случае вставка в связном списке происходит быстрее, чем в массивах.
На счёт того что вставка в середину выполняется за O(1) я сомневаюсь, ибо чтобы что-то вставить с связной список, особенно в конец или в середину необходимо пройтись от начала списка до нужного места, а именно до середины, а это уже время O(n). Но в любом случае вставка в связном списке происходит быстрее, чем в массивах.
Женя Людин
В конец можно добавить за время и O(1) если всё оптимизировать и хранить указатель на конец списка, а вот в середину или в определенное указанное время навряд ли.
Женя Людин
ошибка "но и это уже O(1)" исправленная версия "но и это уже O(n)"
Похожие вопросы
- Нужно ли учить assembler или лучше потратить время на изучение высокоуровневых языков?
- Почему JS более общий язык, чем PHP? Хотя придумывался только для работы в браузере. Будет ли когда-нибудь с PHP также?
- Высокоуровневый язык программирования чем отличаеца от Низкоуровневый язык программирования? подробнее ?
- Как высокоуровневый язык компилируется в машинный код?
- Что такое wordpress и чем он отличается от языков типа php?
- Насколько язык программирования PHP дружелюбен к новичку?
- Каковы преимущества и недостатки связных списков по сравнению с массивами в C++
- для выучения языка программирования php нужно математика?
- Что нужно знать чтобы создавать сайты профессионально?
- Если я хочу изучить язык программирования PHP, полезно ли предварительно изучить язык C++ ?
Да я знаю php.net самый лучший PHP-шный учебный ресурс, но я его использую в качестве справочного материала, а мне нужен учебник в котором будет описываться не только теория, но и задания к каждым пройденным темам для закрепления.