Comments 9
Непонятно зачем эти приседания. Почему не сделать сам linked list классом?
Для коллекций полезно иметь value semantics, чтобы управлять мутабельностью. Немного расширю вопрос. Автор не очень доходчиво описал недостаток реализации через класс:
Почему одна ячейка? Экземпляр узла может быть создан в лубом доступном месте кучи.
Что значит «наблюдать»?
Это значит, что для многих узлов у нас есть общая ячейка памяти и куча ссылок на них. Они могут расти и с большими размера за ними сложно наблюдать.
Почему одна ячейка? Экземпляр узла может быть создан в лубом доступном месте кучи.
Что значит «наблюдать»?
Вот это поворот, не ожидал, что разработчики Swift такую ошибку сделают. Но теперь понятно, что автор хочет сделать. Эта «классная» особенность Swift делает разработку идиоматических коллекций раз в 10 сложнее. А если подумать про многопоточность и эффективность то наступает полный !"№%:.
Совет автору — не пытайтесь повторить в своих коллекциях дурные паттерны, даже если они исходят от создателей языка. immutable interface прошел тест временем, а COW это геморой на ровном месте, на который вы потратите 90% времени и который нужен в 0.001% случаев (если отказаться от value semantic коллекции).
Совет автору — не пытайтесь повторить в своих коллекциях дурные паттерны, даже если они исходят от создателей языка. immutable interface прошел тест временем, а COW это геморой на ровном месте, на который вы потратите 90% времени и который нужен в 0.001% случаев (если отказаться от value semantic коллекции).
Преимущество связного списка именно в возможности удаления и вставки за O(1). Немутабельный связный список не имеет смысла, как и копирование списка на каждое изменение.
Immutable interface и immutable linked list это две большие разницы. А вообще NSMurableArray порвёт самодельный linked list на всех, практически значимых, сценариях, там внутри как раз linked list из сегментов.
Зачем вам immutable interface, кода вы хотите менять состояние объекта? Можно конечно иметь методы возвращающие измененную копию, но это непрактично для данной задачи.
Вы, похоже, слабо представляете себе область применения связного списка. Это не только вставка/удаление элементов за O(1), но и, например, доступ к следующему/предыдущему элементам и манипуляции над ними без индекса за то же, константное, время.
Но нужно признать, что задачи, требующие применения связного списка, на iOS встречаются нечасто.
NSMurableArray — имеет как раз mutable interface, потому NSArray приходится копировать на каждый чих.А вообще NSMurableArray порвёт самодельный linked list на всех, практически значимых, сценариях
Вы, похоже, слабо представляете себе область применения связного списка. Это не только вставка/удаление элементов за O(1), но и, например, доступ к следующему/предыдущему элементам и манипуляции над ними без индекса за то же, константное, время.
NSMutableArray такого интерфейса не предоставляет. То, что он использует связный список под капотом, не делает его связным списком.Но нужно признать, что задачи, требующие применения связного списка, на iOS встречаются нечасто.
Зачем вам immutable interface, кода вы хотите менять состояние объекта?
Immutable interface нужен чтобы кто- о мог произвести объект, а затем передать его куда-то зная, что его менять не будут. Внутри класса NSMutableArray а наружу торчит NSArray. Почти всегда этого достаточно и ничего копировать не нужно.
Но больше всего меня волнует вопрос зачем автор делает struct и парится с copy on write, когда можно сделать по аналогии с NSArray/NSMutableArray.
Это не только вставка/удаление элементов за O(1), но и, например, доступ к следующему/предыдущему элементам
i++ — взять следующий элемент от текущего. i -= 1 — взять предыдущий.
и манипуляции над ними без индекса за то же, константное, время.
Чем LinkedListNode i отличается принципиально от int i?
То, что он использует связный список под капотом, не делает его связным списком.
Я веду к тому, что разница настолько незначительная, что нет смысла делать свой список.
Внутри класса NSMutableArray а наружу торчит NSArray. Почти всегда этого достаточно и ничего копировать не нужно.
… когда можно сделать по аналогии с NSArray/NSMutableArray.
Код, который использует
NSArray, не может полагаться на его иммутабельность, поэтому обычно создается локальная копия исходного массива (для параметра метода — это обычно перебор, но для поля класса — обязательно). В этом плане value semantics в Swift намного более удобен, так как нельзя забыть скопировать структуру, она всегда копируется.i++ — взять следующий элемент от текущего. i -= 1 — взять предыдущий.
В linked list индексы не используются. Точнее linked list используют вместо массива там, где доступ по индексу неудобен или невозможен, но требуется доступ к соседним элементам имея ссылку на исходный элемент.
Я веду к тому, что разница настолько незначительная, что нет смысла делать свой список.
Несколько наивное заявление. Вам просто не попадалась соответсвующая задача. При этом, как правило, подобные задачи достаточно специфичны и требуют реализации списка с нуля. По этой же причине в стандартных библиотеках связные списки — редкость.
Расскажите пожалуйста, для решения какой прикладной задачи вам понадобился linked list? Сравнивали ли полученное решение с решением на стандартном массиве? В целом название статьи предполагает ответ на этот вопрос.
Sign up to leave a comment.
Linked List: Когда нужно писать свой Copy-on-write в iOS?