Блог

контекст
Связанный список XOR — это более эффективный с точки зрения памяти двусвязный список. Вместо каждого узла, содержащего поля next и prev, он содержит поле с именем both, которое является XOR следующего узла и предыдущего узла. Реализуйте связанный список XOR; в нем есть add (элемент), который добавляет элемент в конец, и get (индекс), который возвращает узел с индексом.

 class Node {
    constructor(value){
        this.value = value;
        this.both = 0;
    }
}

class XORLinkedList {
    constructor(value){
        this.head = new Node(value);
    }

    add(element){
        let prev = this.head;
        // next of headNode will be currNode
        let currNode = null ^ this.head.both;
        while (currNode.both != 0){
            const next = prev ^ currNode.both;
            prev = currNode;
            currNode = next;
            }

        currNode.value = element;
        currNode.both = prev ^ null;
        }

    get(index) {
        let prev = null;
        let currNode = this.head;
        for (let i = 0; i < index; i  = 1) {
          const temp = currNode;
          currNode = prev ^ this.head.both;
          prev = temp;
        }
        return currNode;
      }
}

// Driver program
const XLList = new XORLinkedList(3);
XLList.add(5);
XLList.add(7);
console.log(XLList.get(1));
console.log('end');
  

 >>>node XORLinkedList.js
// returns nothing indefinitely, expected a node object with the value 5, prev of 3 and next of 7 and a end message
  

Xorlink-список создан в JS без явных указателей. Я тестирую методы add и get в программе драйвера, и я хочу знать, работает ли обход списка правильно или нет, потому что get ничего не возвращает