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

2022-09-04 04:08:09

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;
}

答案 1

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

C++,这也是一个非常糟糕的主意。

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


答案 2

推荐