XOR-связный список: различия между версиями
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.7 |
Patarakin (обсуждение | вклад) м 1 версия импортирована |
||
(нет различий)
| |||
Версия от 10:30, 19 октября 2022
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранится только один составной адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка.
Для того, чтобы перемещаться по списку, необходимо иметь адреса двух последовательных элементов.
Выполнение операции XOR над адресом первого элемента и составным адресом, хранящимся во втором элементе, даёт адрес элемента, следующего за этими двумя элементами.
Выполнение операции XOR над составным адресом, хранящимся в первом элементе, и адресом второго элемента даёт адрес элемента, предшествующего этим двум элементам.
Сравнения
C двусвязным списком
Классический двусвязный список хранит отдельно адреса предыдущего и следующего элемента списка, для хранения которых требуется два указателя:
... A B C D E ...
–> next –> next –> next –>
<– prev <– prev <– prev <–
Накладные расходы XOR-связного списка в два раза меньше, так как в нём хранится только один «адрес» — XOR указателей на предыдущий и следующий элементы:
... A B C D E ...
<–> A⊕C <-> B⊕D <-> C⊕E <->
Недостатки
Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы<ref>Шаблон:Cite web</ref>.
Использование
Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.
См. также
Примечания
| {{#switch: {{{1}}}
| узкие = columns reflist-narrow
| широкие = columns reflist-wide
| #default = columns
}}
| {{#switch: {{{1}}}
| 1 =
| 2 | 3 = columns
| #default = columns reflist-narrow
}}
}}
| columns
}}
}}" style="{{#if:
| column-width:{{{colwidth}}};
| {{#if:
| {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие =
| #default = column-width:{{{1}}};
}}
}}
}}
}} list-style-type: {{#switch:
| upper-alpha
| upper-roman
| lower-alpha
| lower-greek
| lower-roman = {{{group}}}
| #default = decimal
}};">
<references group="" responsive="{{#if:
| 0
| {{#if:
| {{#iferror: {{#expr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие = 1
| #default = 0
}}
| {{#switch: {{{1}}}
| 1 = 0
| #default = 1
}}
}}
| 1
}}
}}"></references>Ошибка скрипта: Модуля «Check for unknown parameters» не существует.
Ссылки
- Пример реализации на C++. 15 April 2011
- Prokash Sinha, A Memory-Efficient Doubly Linked List // LinuxJournal, Dec 01, 2004
- Implementation of Enhanced Singly Linked List Equipped with DLL Operations: An Approach towards Enormous Memory Saving / International Journal of Future Computer and Communication, Vol. 3, No. 2, April 2014
