Рубрики

XOR Linked List — Двусвязный список с эффективным использованием памяти | Комплект 1

Обычный двусвязный список требует места для двух полей адреса для хранения адресов предыдущего и следующего узлов. Эффективно использующая память версия Doubly Linked List может быть создана с использованием только одного пробела для поля адреса с каждым узлом. Этот эффективный по памяти двусвязный список называется XOR Linked List или Memory Efficient, поскольку в списке используется побитовая операция XOR для экономии места для одного адреса. В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.

Рассмотрим приведенный выше двусвязный список. Ниже приведены обычные и XOR (или Memory Effiecient) представления двусвязного списка.

Обычное представительство:
Узел А:
prev = NULL, next = add (B) // предыдущий равен NULL, а следующий — адрес B

Узел Б:
prev = add (A), next = add (C) // предыдущий адрес A, а следующий адрес C

Узел С:
prev = add (B), next = add (D) // предыдущий адрес B, а следующий адрес D

Узел D:
prev = add (C), next = NULL // предыдущий адрес C, а next NULL

Представление списка XOR:
Давайте назовем адресную переменную в XOR представлении npx (XOR следующего и предыдущего)

Узел А:
npx = 0 XOR add (B) // битовая XOR нуля и адреса B

Узел Б:
npx = add (A) XOR add (C) // побитовый XOR адреса A и адреса C

Узел С:
npx = add (B) XOR add (D) // побитовый XOR адреса B и адреса D

Узел D:
npx = add (C) XOR 0 // битовая XOR адреса C и 0

Обход связанного списка XOR:
Мы можем пройти список XOR в прямом и обратном направлении. При обходе списка нам нужно запомнить адрес ранее доступного узла, чтобы вычислить адрес следующего узла. Например, когда мы находимся в узле C, у нас должен быть адрес B. XOR add (B) и npx of C дает нам add (D). Причина проста: npx (C) это «добавить (B) XOR добавить (D)». Если мы сделаем xor для npx (C) с помощью add (B), мы получим результат как «add (B) XOR add (D) XOR add (B)», что означает «add (D) XOR 0», что означает «add» (D)». Таким образом, у нас есть адрес следующего узла. Точно так же мы можем пройти список в обратном направлении.

Мы рассмотрели больше о XOR Linked List в следующем посте.

XOR Linked List — Двусвязный список с эффективным использованием памяти | Набор 2

Ссылки:
http://en.wikipedia.org/wiki/XOR_linked_list
http://www.linuxjournal.com/article/6828?page=0,0

Рекомендуемые посты:

XOR Linked List — Двусвязный список с эффективным использованием памяти | Комплект 1

0.00 (0%) 0 votes