Comments 7
использование связного списка для сбора диагностики выделений динамической памяти в вашем коде
интересно, какой консистенции выделения производит динамическая память в нашем коде.
Надо быть очень осторожным используя великий и могучий язык, могущество иногда боком выходит.
fat node method и подход с "версиями" можно перенести на другие структуры/коллекции для реализации CoW (Copy-On-Write).
В копилку применений: https://en.wikipedia.org/wiki/Dancing_Links
Главная фишка XOR листа в том, что его можно обходить в любом направлении. А не в мифической безопасности из-за "зашифрованных" адресов. Как и в односвязном списке, нельзя удалить произвольную ноду по указателю на нее. И более того, даже вставка или обход с произвольной ноды уже невозможны.
Кстати по аналогии с развёрнутым списком существует "развёрнутое" дерево: https://en.wikipedia.org/wiki/2–3–4_tree
Причём для случая с 2-4 листами у вершины в одном "слое" дерева получается сразу два "слоя" красно-чёрного дерева (чёрная вершина и её красные дети, если они есть)
Интересно, насколько широко такие списки и деревья используются и насколько они быстрее благодаря попаданию нескольких элементов в одну кеш-линию.
Многообразие связных списков