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

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

您当然可以在free不知道它具有哪种节点的情况下列出一个列表:

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

因为有关数据结构的教科书主要是为了向初学者传授概念.这种"优化"只会给初学者耳朵带来很多噪音.这是你放学后的知识,将你与其他人分开......