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

在本文中，我介绍了一种传统的双向链表 ADT 实现方案和一种替代实现方案，包括插入、遍历和删除操作。我还提供了每种方案的时间和内存测量结果，以比较其优缺点。替代实现方案基于指针距离，因此在本文讨论中我称之为指针距离实现方案。每个节点将仅携带一个指针字段，用于来回遍历列表。在传统实现方案中，我们需要保留一个指向列表中下一个项目的正向指针和一个指向前一个项目的反向指针。传统节点的开销为 66%，而指针距离实现方案的开销为 50%。如果我们使用多维双向链表，例如动态网格，则节省的开销将更大。

本文不提供对双向链表的传统实现的详细讨论，因为几乎每本数据结构和算法书籍中都讨论了它们。传统实现和距离指针实现甚至以相同的方式使用，以获得可比较的内存和时间使用统计数据。

我们像这样定义指针距离实现的节点

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

ptrdiff 指针字段保存指向下一个节点的指针与指向前一个节点的指针之间的差值。指针差值是通过使用异或捕获的。此类列表的任何实例都有一个 StartNode 和一个 EndNode。StartNode 指向列表的头部，EndNode 指向列表的尾部。根据定义，StartNode 的前一个节点是 NULL 节点；EndNode 的下一个节点也是 NULL 节点。对于单例列表，前一个节点和下一个节点都是 NULL 节点，因此 ptrdiff 字段保存 NULL 指针。在双节点列表中，StartNode 的前一个节点为 NULL，下一个节点为 EndNode。StartNode 的 ptrdiff 是 EndNode 和 NULL 节点的异或：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() 例程未找到给定的元素，它将不会插入新元素。

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() 例程遍历列表，直到包含给定元素的节点。如果我们找到它，我们将节点放置在找到的节点之后。由于下一个节点具有指针差值，我们通过与找到的节点进行异或运算来消除它。接下来，我们与新节点进行异或运算，因为新节点将成为它的前一个节点。按照相同的逻辑修复当前节点，我们首先通过与下一个当前节点进行异或运算来消除指针差值。然后，我们与新节点进行另一次异或运算，这为我们提供了正确的指针差值。最后，由于新节点将位于找到的当前节点和下一个节点之间，我们通过对它们进行异或运算来获得它的指针差值。

当前的删除实现会擦除整个列表。对于本文，我们的目标是展示已实现原语的动态内存使用情况和执行时间。为双向链表的所有已知操作提出一套规范的原语操作应该不难。

由于我们的遍历取决于拥有指向两个节点的指针，因此我们无法在找到下一个节点后立即删除当前节点。相反，一旦找到下一个节点，我们总是删除前一个节点。此外，如果当前节点是结尾，当我们释放当前节点时，我们就完成了。如果应用于节点的 NextNode() 函数返回空节点，则该节点被视为结尾节点。

一个用于测试此处讨论的实现的示例程序可从 Linux Journal FTP 站点获得（ftp://ftp.linuxjournal.com/pub/lj/listings/issue129/6828.tgz）。在我的奔腾 II（349MHz、32MB 内存和 512KB 二级缓存）上，当我运行指针距离实现时，创建 20,000 个节点需要 15 秒。这是插入 20,000 个节点所需的时间。遍历和删除整个列表甚至不需要一秒钟，因此在该粒度下的性能分析没有帮助。对于系统级实现，人们可能希望以毫秒为单位测量时间。

当我们在 10,000 个节点上运行相同的指针距离实现时，插入仅需三秒钟。遍历列表和删除整个列表都不到一秒钟。对于 20,000 个节点，整个列表使用的内存为 160,000 字节，对于 10,000 个节点，使用的内存为 80,000 字节。在 30,000 个节点上，运行插入需要 37 秒。同样，完成遍历或删除整个列表都不到一秒钟。我们看到这种时间安排在某种程度上是可预测的，因为此处使用的动态内存（堆）随着节点数量的增加而越来越多地被使用。因此，从动态内存中查找内存槽花费的时间越来越长，呈非线性，而是超线性的方式增长。

对于传统实现，插入 10,000 个节点需要相同的三秒钟。正向和反向遍历都不到一秒钟。10,000 个节点占用的总内存为 120,000 字节。对于 20,000 个节点，插入需要 13 秒。遍历和删除分别不到一秒钟。20,000 个节点占用的总内存为 240,000 字节。在 30,000 个节点上，运行插入需要 33 秒，运行遍历和删除不到一秒钟。30,000 个节点占用的总内存为 360,000 字节。

在不严重影响时间效率的情况下，可以实现内存高效的双向链表。巧妙的设计将为两种实现方案提供一套规范的原语操作，但对于那些可比较的原语，时间消耗不会有显着差异。