异或双向链表是什么？

异或双向链表的特点是在内存使用上更有效率

为了使小型设备具有成本效益，制造商通常需要考虑减小内存大小。一种选择是找到我们日常实现中使用的抽象数据类型（ADTs）的替代实现。一个这样的ADT是双链表结构。

在这篇文章中，一个传统的实现和替代实现的双链表ADT，插入，遍历和删除操作。我还提供了每种方法的时间和内存度量，以比较它们的优缺点。另一种实现是基于指针距离的，因此在本文中我称之为指针距离实现。每个节点只携带一个指针字段来来回遍历列表。在传统的实现中，我们需要保持一个指向列表中下一项的前向指针和一个指向上一项的后向指针。传统节点的开销为66%，指针距离实现的开销为50%。如果我们使用多维双链表，比如动态网格，节省的成本会更大。

这里不详细讨论双链表的常规实现，因为几乎每本数据结构和算法书都会讨论双链表。传统的和距离指针实现甚至以相同的方式使用，以具有可比较的内存和时间使用统计信息。

节点定义

我们将指针距离实现的节点定义为：

typedef int T;
typedef struct listNode{
	T elm;
	struct listNode * ptrdiff;
};

ptrdiff指针字段保存指向下一个节点的指针和指向上一个节点的指针之间的差异。使用异或捕获指针差异。这种列表的任何实例都有一个StartNode和一个EndNode。StartNode指向列表的头部，EndNode指向列表的尾部。根据定义，StartNode的前一个节点是空节点；EndNode的下一个节点也是空节点。对于单例列表，前一个节点和下一个节点都是空节点，因此ptrdiff字段保存空指针。在双节点列表中，StartNode的前一个节点为空，下一个节点为EndNode。StartNode的ptrdiff是EndNode和NULL node:EndNode的异或。并且，EndNode的ptrdiff是StartNode。

遍历

特定节点的插入和删除取决于遍历。我们只需要一个简单的例程来来回遍历。如果我们提供StartNode作为参数，并且因为前面的节点为NULL，那么我们的遍历方向被隐式地定义为从左到右。另一方面，如果我们提供EndNode作为参数，则隐式定义的遍历方向是从右到左。目前的实现不支持从列表中间遍历，但它应该是一个简单的增强。下一个节点定义如下：

typedef listNode * plistNode;
plistNode NextNode( plistNode pNode,
                    plistNode pPrevNode){
    return ((plistNode)
      ((int) pNode->ptrdiff ^ ( int)pPrevNode) );
}

给定一个元素，我们通过对下一个节点和前一个节点进行异或运算来保持该元素的指针差。因此，如果我们对前一个节点执行另一个异或，我们将得到指向下一个节点的指针。

插入

给定一个新节点和一个现有节点的元素，我们希望在具有给定元素的遍历方向上的第一个节点之后插入新节点（清单1）。在现有的双链表中插入节点需要指针固定三个节点：当前节点、当前节点的下一个节点和新节点。当我们提供最后一个节点的元素作为参数时，这种插入会退化为列表末尾的插入。我们以这种方式构建列表以获得计时统计数据。如果InsertAfter（）例程没有找到给定的元素，它将不会插入新元素。

清单1。函数插入新节点

void insertAfter(plistNode pNew, T theElm)
{
   plistNode pPrev, pCurrent, pNext;
   pPrev = NULL;
   pCurrent = pStart;

   while (pCurrent) {
      pNext = NextNode(pCurrent, pPrev);
      if (pCurrent->elm == theElm) {
         /* traversal is done */
         if (pNext) {
            /* fix the existing next node */
            pNext->ptrdiff =
                (plistNode) ((int) pNext->ptrdiff
                           ^ (int) pCurrent
                           ^ (int) pNew);

            /* fix the current node */
            pCurrent->ptrdiff =
              (plistNode) ((int) pNew ^ (int) pNext
                         ^ (int) pCurrent->ptrdiff);

            /* fix the new node */
            pNew->ptrdiff =
                (plistNode) ((int) pCurrent
                           ^ (int) pNext);
         break;
      }
      pPrev = pCurrent;
      pCurrent = pNext;
   }
}

首先，我们使用NextNode（）例程将列表遍历到包含给定元素的节点。如果我们找到它，我们就把这个节点放在这个找到的节点之后。因为下一个节点有指针差，所以我们通过与找到的节点进行异或运算来分解它。下一步，我们对新节点执行排他ORing，因为新节点将是它的前一个节点。通过遵循相同的逻辑修复当前节点，我们首先通过与下一个当前节点进行异或运算来消除指针差异。然后，我们对新节点执行另一个排他ORing，这为我们提供了正确的指针差异。最后，由于新节点将位于找到的当前节点和下一个节点之间，因此我们通过独占地对它们进行ORing来获得它的指针差。

删除

当前的delete实现将删除整个列表。在本文中，我们的目标是显示所实现原语的动态内存使用情况和执行时间。对于一个双链表的所有已知操作，找出一组规范的基本操作应该不难。

因为我们的遍历依赖于指向两个节点的指针，所以我们不能在找到下一个节点后立即删除当前节点。相反，我们总是在找到下一个节点后删除上一个节点。而且，如果当前节点是结束节点，当我们释放当前节点时，我们就完成了。如果应用于某个节点的NextNode（）函数返回空节点，则该节点被视为结束节点。

内存和时间的使用

站点上的清单2提供了一个测试这里讨论的实现的示例程序。在我的奔腾II（349MHz，32MB的RAM和512KB的二级缓存）上，运行指针距离实现时，创建20000个节点需要15秒。这是插入20000个节点所需的时间。遍历和删除整个列表甚至不需要一秒钟，因此在这个粒度上进行分析是没有帮助的。对于系统级实现，可能需要以毫秒为单位度量计时。

当我们在10000个节点上运行相同的指针距离实现时，插入只需要3秒钟。遍历列表和删除整个列表的时间都不到一秒钟。对于20000个节点，用于整个列表的内存是160000字节，对于10000个节点，是80000字节。在30000个节点上，运行插入需要37秒。同样，遍历或删除整个列表所需的时间不到一秒。在某种程度上可以预见，我们会看到这种计时，因为随着节点数量的增加，这里使用的动态内存（heap）正在被越来越多地使用。因此，从动态内存中找到一个内存插槽需要越来越长的时间，这是一种非线性的、相当于超线性的方式。

对于传统的实现，插入10000个节点需要同样的3秒钟。向前和向后遍历所用的时间都不到一秒钟。10000个节点占用的总内存为120000字节。对于20000个节点，插入需要13秒。逐个遍历和删除不到一秒钟。20000个节点占用的总内存为240000字节。在30000个节点上，运行插入操作需要33秒，运行遍历和删除操作需要不到一秒的时间。30000个节点占用的总内存为360000字节。

结论

一个双链表的内存高效的实现是有可能的，而不影响很多时间效率。一个聪明的设计将为两个实现提供一组规范的原语操作，但是对于那些可比较的原语，时间消耗不会有显著的不同。