为什么这么多示例链表将下一个指针放在每个节点的末尾而不是开头？

Question

我在这个网站上看到了很多链表的 C 实现示例，其中大多数都像这样将下一个指针放在每个节点的末尾...

struct intNode1 {
   int data;
   intNode1 *next;
};

为什么他们这样实现而不是这样实现？

struct node {
   struct node *next;
};

struct intNode2 {
   struct node node;
   int data;
};

后一种实现链表的方法允许您的插入和删除代码在任何类型的节点上工作，并允许您创建通用列表类型，而前一种方法则迫使您从头开始实现每种类型的列表。

例如，这是使用两种节点的单链表的（不完整）实现：

struct intList {
   struct intNode1 *head;
};

struct list {
   struct node *head;
};

现在，显然，需要比较其节点的通用列表上的任何操作都需要一个指向比较函数的函数指针，但这通常可以隐藏在列表的不太通用的接口的实现中。例如：

/* Returns zero if successful or nonzero otherwise */
int list-insertInt(struct list *list, int n) {
   struct intNode2 * newNode;
   if(!(newNode = malloc(sizeof *newNode)) {
      return -1;
   }
   newNode->data = n;
   return list-insertNode(list, (struct node *)newNode);
}

/* Assumes that the list contains only int nodes. */
int list-containsInt(struct list *list, int n) {
   struct intNode2 *current = (intNode2 *)list->head;
   while (current) {
      if(current->data == n) {
         return true;
      }
      current = current->next;
   }
   return false;
}

您当然可以释放一个列表，而不知道它有什么类型的节点：

void list-free(struct list *list) {
   struct node *current = list->head;
   struct node *next;
   while(current) {
      next = current->next;
      free(current);
      current = next;
   }
}

PS。有点晚了（即，现在是凌晨，但我还没有'我还没睡）就在我写这篇文章的时候。所以请随意编辑这个问题以使其更加清晰。

Answer 1

因为数据结构教科书主要是为了向初学者教授概念。这种“优化”只会给初学者增加很多噪音。正是你放学后运用所学知识所做的事情，将你与其他人区分开来......

Answer 2

我不知道其他人怎么想，但我这样做很简单，当我想将数据部分写入文件时，我只需在末尾写入没有指针的位（包括 prev 指针，如果这是一个双向链表）。

我很少有一个链表，其中每个节点的类型可以不同，并且在向初学者教授列表和其他抽象数据类型的概念时几乎肯定不会有这样的链表。

Answer 3

将指针放在末尾的好处是节点和有效负载具有相同的地址。现在看来这似乎没什么优势，但回想一下 ANSI C 之前的情况。是的，我说的是编译器甚至没有尝试检查指针的数据类型的时代。

当您想要将有效负载传递给函数时，您只需传递指针即可，从而节省几个字节的输入（以及宝贵的磁盘空间！）。

Answer 4

有些链表将 Next 指针放在结构的末尾，有些则不然。我真的不认为这是一个问题。

老实说，我不确定我是否遇到过 C 语言中链表维护不同节点类型的情况。但是，如果您需要做的话，可以使用您所描述的方法。

请注意，当今大多数 C 程序员都使用 C++，这将允许您使用继承来完成同样的事情。使用继承，Next 成员放置在类中的位置并不重要。