Что такое примеры реального мира того, когда Связанные списки должны использоваться?
мы не можем полностью удалить этот родительский (с индексом), НО вы можете установить их на null, используя transform () , как это;
$data = DeliveryPartner::when($filter, function ($q) use ($request) {
})
->with(['orders' => function ($query) {
$query
->where('delivery_partner_invoice_id', '=', '')
->orWhereNull('delivery_partner_invoice_id')
->whereIn('status', ['payment-accepted', 'completed', 'full-refund', 'partial-refund']);
}])->get()->transform(function($item){
if(!$item->orders->count() ){
return;
}
return $item;
});
Примечание: это не будет полностью удалите этих родителей, но это сделает их пустыми.
16 ответов
Реальным примером была бы очередь FIFO. Основанный на простом массиве список довольно плох для этого, потому что необходимо добавить в одном конце и удалить с другой стороны, и одна из тех операций будет O (n) с основанным на массиве списком (если Вы не добавите дополнительную логику для работы с запуском И индексом конца), в то время как оба - O (1) со связанным списком без дополнительного усилия.
Профессионалы связанного списка:
- Динамическая память аннулирует фрагментацию
- Быстрая вставка / удаление
- Быстрый доступ к первому элементу (и конец, если реализовано двунаправленный)
- Эффективное использование памяти
Недостатки связанного списка:
- Медленное пересечение
Из моей головы я реализовал бы стеки, очереди и messagepumps, использующий связанные списки. Я также реализовал бы datatree, использующий мультиссылочные связанные списки для быстрой вставки / удаление.
Для проблем, где количество максимальных узлов ограничиваются к 100 или ниже или так, связанные списки являются разумным решением. То же может быть верным для вещей как пузырьковая сортировка и других вещей, которые, как думают, являются субоптимальными.
Стеки и Очереди являются примерами связанных списков.
Как сказано уже связанные списки очень полезны, когда необходимо вставить и удалить элементы.
Например, чтобы помочь отладить управление памятью в моем коде I недавно implemeneted список ссылок между всей моей ссылкой считаемые объекты так, чтобы в конце программы (когда ссылки должны были все поразить нуль и удалить объекты) я видел точно, что все еще оставили, useually приведя ко мне способность найти отдельный объект в корне проблемы.
CPython реализует что-то similir с крупным связанным списком почти между каждым когда ее созданный с отладкой.
Как daustin777 указывает, связанные списки - все вокруг Вас, и Вы даже не можете знать это. Но практичность вопроса - то, что они позволяют, чтобы некоторые довольно основные операции были выполнены с относительной простотой и гибкостью. Например, не к виду, просто подкачайте указатели вокруг. Должен вставить или удалить в произвольных местах? Вставьте или удалите свои указатели в рамках списка. Потребность выполнить итерации форвардов и назад... связанного списка. В то время как не точно бизнес-пример, я надеюсь, что это разъясняет его достаточно, чтобы Вы применили его к своей собственной экономической модели реального мира.
Отвечая на тег на 'Структуры данных', на низком уровне, такие как блок, связанные списки являются идеальным способом сохранить списки переменной длины других структур данных. Нет никаких издержек для поддержания длины списка или конца, и не существует потребность в элементах списка фиксированного размера. Последняя причина также относится к высокоуровневым языкам.
Как, возможно, лучший пример реального мира в .NET рассматривают MultiCastDelegate.
Связанные списки, реализованные таким образом, где список, объединяющий аспект в цепочку, поддерживается непосредственно в тип, а не как отдельный контейнер, могут быть чрезвычайно мощными и эффективными. Они прибывают однако с разнообразием торговли offs.
Один очевидный является дублированием кода, необходимо испечь эту логику в каждом типе. Методы, такие как расширение базового класса, обеспечивающего указатель, грязны (Вы теряете строгий контроль типов без дженериков), и часто недопустимый с точки зрения производительности.
Другой - это, Вы ограничены одной реализацией на тип. Вы не можете превратить отдельно связанную структуру во вдвойне связанную, не вставляя дополнительное поле в каждый экземпляр и обновив все соответствующие нормы.
Неизменный связанный список является очень ценной структурой, так как можно 'совместно использовать структуру' с другими списками с тем же хвостом. Большинство функциональных языков включает неизменный тип связанного списка как одну из их фундаментальных структур данных, и эти типы используются повсеместно.
Они происходят все время, где угодно объект имеет свойство, которое указывает на другой объект того же типа. В CLR исключения формируют связанный список, из-за InnerException свойство.
Стеки и очереди являются очень ясными примерами связанных списков, но как другой уже упомянули их, я хотел бы добавить несколько других примеров:
DOM хранит узлы как связанные списки. Простой образец JavaScript, который является действительно тем же на любом языке:
for (var node = parent.firstChild; node != null; node = node.nextSibling) {
// ..
}
Я предположил бы, что Java-разработчик столкнулся с XML в какой-то момент.
Деревья являются другой пользой примеры связанных списков, даже при том, что они не простые одномерные. Кто-то, кто сделал большую разработку Java, вероятно, столкнулся с TreeMaps и TreeSets.
Все обсуждение кажется немного глупым мне. Связанные списки являются фундаментальной структурой данных, которая используется везде. Единственная причина, что можно было бы думать, что он не столкнулся с ними, состоит в том, что Вы не должны действительно волноваться о реализации структур данных на сегодняшних высокоуровневых языках, но конечно они все еще там.
Навязчивые связанные списки являются интересными зверями для разработки игр. Например, это - несколько обычная практика, чтобы иметь навязчивое отдельно - или вдвойне связанный список "рендеринга":
class Renderable /* or class Object, whatever */
{
// ...
Renderable * m_pNext;
Renderable * m_pPrev; // or not, if singly-linked
// ...
}
Поскольку Renderables входят, и из существования они могут зарегистрировать себя в этом списке - не вызывая выделения памяти. Если их глубина рендеринга или приоритет изменяются, они могут удалить и повторно ввести себя и т.д.
То, когда это прибывает время для рендеринга, все, что необходимо сделать, является находкой заголовок списка и zip через, называя соответствующий метод!
(Существуют, конечно, много вариаций на эту тему, с несколькими отдельными списками, и т.д. И у Вас не должно быть навязчивого списка для создания этой работы, я просто нахожу навязчивые интересными.)
Связанные списки (соединенный с хеш-таблицей) действительно полезны для Кэшей LRU.
Каждый Получать потребности ударить узел к передней стороне списка, операция, которая является действительно дешевой со связанными списками.
Связанные списки предлагают несколько преимуществ перед сопоставимыми структурами данных, такими как статические или динамично расширяющиеся массивы.
- Доза LinkedLists не требует непрерывных блоков памяти и поэтому может помочь уменьшить фрагментацию памяти
- LinkedLists поддерживают эффективное удаление элементов (динамические массивы обычно вызывают сдвиг во всех элементах).
- LinkedLists поддерживают эффективное добавление элементов (динамические массивы могут вызвать перераспределение + копия, если деталь добавляет, превышает токовую нагрузку),
Любое место, где эти преимущества были бы значительно ценны к программе (и недостатки LinkedList были незначительны) будет местом для использования LinkedList.
Я написал расширение BIOS (в основном, драйвер устройства для BIOS, написанный на сборке) для контроллера хоста USB. - Реализация высокого уровня, казалось бы, абстрактная структура данных, такая как связанный список в сборке, не так сильно, как это звучит. - Контроллер обслуживает запросы ввода / вывода для клавиатуры и диска, используя связанный список пакетов в основной памяти. Я поддерживал пул бесплатных пакетов в другом связанном списке. Выполнение ввода / вывода в основном включал в себя схватывание бесплатного пакета из начала свободного списка, настроив пакет, добавив пакет в список устройств и повторно добавляя пакет в начало свободного пула, когда вводной / вывод. Связанные списки находятся быстрыми молнией для перемещения вокруг таких объектов, особенно когда объекты большие, поскольку объекты на самом деле не должны двигаться. Только их указатели должны быть обновлены.
Очередь на основе массива потребовала бы:
- с использованием указателя индекса начала / конечного индекса, который быстро, но требует фиксации размера очереди, чтобы производителю должен дождаться, когда очередь потребителя заполнена и блокировка Очередь, в то время как весь пакет заполнен, если есть более одного производителя
- , сдвигая все элементы в очереди, когда вы вставляете / удалите, что медленно для больших объектов
, поэтому связанные списки - это хороший способ реализации произвольно длинная в первую очередь очередь крупных объектов.
Другое дело, чтобы быть осторожным, это то, что для небольших объектов или где вы распределите объекты из обычной кучи вместо пользовательского бесплатного бассейна, массивы могут быть быстрее, потому что копирование на самом деле не так медленно, если это не так часто, и Повторное распределение из кучи, что связанный список потребуется каждый раз, когда добавляется новый элемент, является медленным.
Конечно, вы можете имитировать и измерить ваш конкретный сценарий с помощью некоторых тестовых кодов, чтобы найти ответ. Мне нравится бегать петли несколько миллионов раз со связными списками и массивами, с небольшими и большими объектами, а время, как долго каждый занимается в реальном времени. Иногда вы будете удивлены.
Связанный список является важной структурой данных для Dancing Links , который является методом, используемым для эффективной реализации алгоритма X , который представляет собой алгоритм поиска с возвратом для поиска всех решений NP- полное точное покрытие задачи, к которой естественно сводятся многие сложные задачи.