Why do so many example linked lists put the next pointer at the end of each node instead of at the beginning?

I've seen quite a few example C implementations of linked lists on this site, and most of them place the next pointer at the end of each node like so...

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

Why do they implement them like that instead of like this?

struct node {
   struct node *next;
};

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

The latter way of implementing linked lists allows your insertion and deletion code work on any kind of node as well as allowing you to create a generic list type while the former way forces you to implement each kind of list from scratch.

For example, here is an (incomplete) implementation of a singly linked list using both kinds of nodes:

struct intList {
   struct intNode1 *head;
};

struct list {
   struct node *head;
};

Now, obviously any operation on a generic list that needs to compare it's nodes will need a function pointer to a comparison function, but that can often be hidden away in the implementation of a less generic 开发者_StackOverflow社区interface for a list. For instance:

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

You can of course free a list without knowing what kinds of nodes it has:

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

PS. It's a bit late (i.e. it's early in the morning but I haven't slept yet) as I write this. so feel free to edit this question to be more clear.

---

Because textbooks on datastructures are mostly meant to teach concepts to beginners. That kind of 'optimization' just adds a lot of noise to the beginner's ear. It is what you do with your knowledge after school, that separates you from the rest...

---

I don't know about anyone else but I do it simply so, when I want to write the data portion to a file, I just write the bit sans the pointers at the end (including prev pointer if it's a doubly linked list).

Very rarely do I have a linked list where the types of each node can be different and almost certainly never when teaching the concepts of lists and other abstract data types to beginners.

---

The advantage of putting the pointer at the end is that the node and the payload have the same address. This may not seem much of an advantage now, but think back to before ANSI C. Yes I'm talking about a time when the compiler didn't even try to check the data type of pointers.

When you wanted to pass the payload to a function you could just pass the pointer, saving several bytes of typing (and valuable disk space!).

---

Some linked lists put the Next pointer at the end of the structure, some don't. I don't really see this as an issue.

To be honest, I'm not sure I ever ran across a case in C where a linked list maintained different node types. But doing something like you describe could be used if that's what you needed to do.

Note that most C programmers today use C++, which would allow you to use inheritance to accomplish the same thing. Using inheritance, it wouldn't matter where the Next member was placed within the class.