是否可以在Java中实现XOR LinkedList(带有单指针的DLL)

Question

XOR链表基本上是链表的有效版本,其存储前一节点和下一节点的地址以仅使用单个指针来实现双链表.我想知道是否有可能在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;
}

Answer 1

不,您根本无法在Java中执行此操作 - 您无法获取对象的地址或从其他值计算对象的引用.这允许垃圾收集器在不干扰程序的情况下移动对象.

在C++中这也是一个非常糟糕的主意.

如果您担心链表中的内存开销,则可以为每个节点存储多个项目.如果一个节点有prev,next和items [16]引用,并且你总是确保你的节点至少有一半满,那么它将比一般的XOR列表使用更少的内存.