Проблема: двусвязный список более эффективен с точки зрения памяти. Вместо каждого узла, содержащего следующее и предыдущее поля, он содержит поле с именем both (в нашем случае addr), которое является операцией XOR для следующего узла и предыдущего узла. Реализуйте связанный список XOR; у него есть insert (элемент), который добавляет элемент в конец, и get (index), который возвращает узел по индексу.
Решение:
Что нужно знать, прежде чем понимать следующее решение.
- Каждый объект хранится по адресу памяти, и любой указатель (ссылка) является способом доступа к этому объекту.
- В C ++ вы можете преобразовать любой адрес в целое число, просто приведя его к подходящему типу данных.
- После преобразования адреса в целое число теперь вы можете выполнять математические и логические операции с этими адресами. Как XOR, сложение, вычитание и т. Д.
- Если R = A xor B, то A = R xor B, также B = R xor A.
Note: To XOR two addresses or take sum we need to convert these memory address to integers which not possible in Java. And in C++ we can cast any pointer i.e (void)*, (Node *), (int *) to any 4/8 byte dataType depending on your machine (4 for 32bit and 8 for 64bit). uintptr_t is available in C++ to handle pointers but we can also use long.
Ниже приведены 3 реализации двусвязного списка.
- Первый - это простой двусвязный список с двумя указателями.
- Второй, как упоминалось в проблеме, - это двусвязный список, созданный с помощью операции XOR.
- Третий основан на сложении и вычитании значения адреса памяти.
Решение:
Проблема От:
Активный репозиторий вносит свой вклад:
Как решение:
