XOR-связный список - История изменений

Patarakin в 09:08, 19 октября 2022

2022-10-19T09:08:38Z

← Предыдущая версия		Версия от 12:08, 19 октября 2022
Строка 19:		Строка 19:
	<–> A⊕C <-> B⊕D <-> C⊕E <-></code>		<–> A⊕C <-> B⊕D <-> C⊕E <-></code>

	~~== Недостатки ==~~
	Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного [[Сборка мусора (программирование)\|сборщика мусора]], затруднения при отладке программы<ref>{{Cite web \|url=http://www.iecc.com/gclist/GC-faq.html#GC,%20C,%20and%20C++ \|title=GC FAQ - draft<!-- Заголовок добавлен ботом --> \|access-date=2012-12-17 \|archive-date=2013-01-09 \|archive-url=https://web.archive.org/web/20130109032120/http://www.iecc.com/gclist/GC-faq.html#GC,%20C,%20and%20C++ \|deadlink=no }}</ref>.

	~~== Использование ==~~
	Используется довольно редко, так как существуют хорошие альтернативы, как, например, [[развёрнутый связный список]].
	~~== См. также ==~~
	* [[Алгоритм обмена при помощи исключающего ИЛИ]]
	* [[Тип данных]]
	~~== Примечания ==~~
	~~{{примечания}}~~

	~~== Ссылки ==~~
	* [https://web.archive.org/web/20110812164603/http://blog.wsensors.com/?p=177 Пример реализации на C++.] 15 April 2011
	* Prokash Sinha, [http://www.linuxjournal.com/article/6828 A Memory-Efficient Doubly Linked List] // LinuxJournal, Dec 01, 2004
	* [http://www.ijfcc.org/papers/276-E1045.pdf 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
	~~{{compu-prog-stub}}~~

	~~[[Категория:Связные списки]]~~
	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:52Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>InternetArchiveBot: Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.7

2022-05-23T07:58:09Z

Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.7

Новая страница

'''XOR-связный список''' — [[структура данных]], похожая на обычный [[двусвязный список]], однако в каждом элементе хранится только один ''составной'' [[Адрес (информатика)|адрес]] — результат выполнения операции [[XOR]] над адресами предыдущего и следующего элементов списка.

Для того, чтобы перемещаться по списку, необходимо иметь адреса двух последовательных элементов.

Выполнение операции XOR над адресом первого элемента и составным адресом, хранящимся во втором элементе, даёт адрес элемента, следующего за этими двумя элементами.

Выполнение операции XOR над составным адресом, хранящимся в первом элементе, и адресом второго элемента даёт адрес элемента, предшествующего этим двум элементам.

== Сравнения ==
=== C двусвязным списком ===
Классический двусвязный список хранит отдельно адреса предыдущего и следующего элемента списка, для хранения которых требуется два указателя:
<code>
... A B C D E ...
–> next –> next –> next –>
<– prev <– prev <– prev <–</code>
Накладные расходы XOR-связного списка в два раза меньше, так как в нём хранится только один «адрес» — XOR указателей на предыдущий и следующий элементы:
<code>
... A B C D E ...
<–> A⊕C <-> B⊕D <-> C⊕E <-></code>

== Недостатки ==
Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного [[Сборка мусора (программирование)|сборщика мусора]], затруднения при отладке программы<ref>{{Cite web |url=http://www.iecc.com/gclist/GC-faq.html#GC,%20C,%20and%20C++ |title=GC FAQ - draft |access-date=2012-12-17 |archive-date=2013-01-09 |archive-url=https://web.archive.org/web/20130109032120/http://www.iecc.com/gclist/GC-faq.html#GC,%20C,%20and%20C++ |deadlink=no }}</ref>.

== Использование ==
Используется довольно редко, так как существуют хорошие альтернативы, как, например, [[развёрнутый связный список]].
== См. также ==
* [[Алгоритм обмена при помощи исключающего ИЛИ]]
* [[Тип данных]]
== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20110812164603/http://blog.wsensors.com/?p=177 Пример реализации на C++.] 15 April 2011
* Prokash Sinha, [http://www.linuxjournal.com/article/6828 A Memory-Efficient Doubly Linked List] // LinuxJournal, Dec 01, 2004
* [http://www.ijfcc.org/papers/276-E1045.pdf 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
{{compu-prog-stub}}

[[Категория:Связные списки]]
[[Категория:Структуры данных]]