Возможно ли реализовать XOR LinkedList в Java (DLL с одним указателем)

Связанные списки XOR - это в основном эффективная версия связанного списка, в которой хранятся адреса предыдущих и следующих узлов для реализации Doubly Linked List с использованием только одного указателя. Мне было интересно, возможно ли реализовать на Java, поскольку у него нет указателей. В C это можно сделать с помощью

 /* Insert a node at the begining of the XORed linked list and makes the
    newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node));
    new_node->data = data;

    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);

    /* If linked list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }

    // Change head
    *head_ref = new_node;
}

Ответы

Ответ 1

Нет, вы не можете сделать это в Java вообще - вы не можете получить адрес объекта или вычислить ссылку на объект из других значений. Это позволяет сборщику мусора перемещать объекты, не мешая программе.

Это также очень плохая идея в С++.

Если вас беспокоит нехватка памяти в связанном списке, вы можете сохранить несколько элементов за node. Если node содержит ссылки prev, next и items [16], и вы всегда убедитесь, что ваши узлы по меньшей мере наполовину заполнены, тогда он будет использовать меньше памяти, чем обычный XOR-список.

Ответ 2

Пока вы не можете использовать raw-указатели в Java, мы можем оставаться близкими к духу связанного списка XOR. Указатель - это просто индекс в массив байтов, который является памятью, массивы java просто добавляют смещение и масштабируют индекс. Если полезная нагрузка - это один int, мы можем легко использовать int[] как "память" и избегать некоторых странных преобразований. Это все еще немного раздражает, потому что нам также нужно реализовать собственный распределитель, но это проще в этом ограниченном контексте, потому что все блоки будут иметь одинаковый размер.

Итак, вот попытка. Не испытано. Это более важно, чтобы вы поняли эту идею.

int[] memory = new int[1024]; // enough for 512 nodes
int free; // pointer to free list

int insert(int head, int data) throws Exception
{
    int node = alloc();
    memory[node] = head;  // normal link here (xored with zero)
    memory[node + 1] = data;
    memory[head] ^= node; // old head gets a xor-link
    return node;          // return new head
}

void init()
{
    // put nodes in free list
    free = 2;
    for (int i = 2; i < memory.length - 2; i += 2)
        memory[i] = i + 2;
}

int alloc() throws Exception
{
    if (free == 0)
        throw new Exception(); // throw a better one
    int res = free;
    free = memory[free];
    return res;
}

void free(int ptr)
{
    memory[ptr] = free;
    free = ptr;
}