在Java中实现XOR LinkedList（单指针双向链表）是否可行？

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

- Mayur Kulkarni

---

在Java中，通常无法对指针执行算术运算，因为它们始终被视为对象的引用，而不是数字。 - khelwood

我很好奇在Java中实现任何双向链表的方式是什么，它是否已经在幕后执行像OP一样的操作？ - Tim Biegeleisen

这个问题在我参加微软面试时被问到，我很震惊，因为使用单指针实现双向链表是可能的。 - Mayur Kulkarni

请阅读此处：https://web.archive.org/web/20160301084747/www.params.me/2011/06/xor-linked-list-in-java.html - Gershon Papi

是的，你可以使用元素对作为数据和下一个项目的索引（或使用XOR技巧）。 - harold

Answer 1

不，Java完全不能这样做--你不能获取对象的地址或从其他值计算对象的引用。这使得垃圾回收器可以在不干扰程序的情况下移动对象。

在C++中这也是一个非常糟糕的想法。

如果您担心链接列表中的内存开销，可以每个节点存储多个项目。如果一个节点具有prev、next和items[16] 引用，并始终确保您的节点至少半满，则平均使用的内存将少于异或列表。

- Matt Timmermans

---

请问您能否详细说明一下，如果在每个节点中存储多个项目，那么这本身不会产生额外的开销吗？我不太明白这一点。 - Mayur Kulkarni

通常情况下，Java中的链表节点有3个引用（prev、next、item）和一个对象头，因此它的大小为4个引用。这意味着每添加一个项目就会增加4个字的开销。XOR列表每添加一个项目需要3个字。每个节点有16个项目，所有节点至少半满（8个项目存在）时，每个节点有21个字，但您可以通过至少8个项目来除以21/8（小于3），从而得到每个项目的开销。 - Matt Timmermans

哦，我忘记在每个节点中存储计数和/或起始单词，所以是22/8。仍然更小。 - Matt Timmermans