Making Generic Linked list placing next pointer at beginning of structure

Question

I am reading one of the books and stuck at one particular question.

Definition of a struct for linked list :::

typedef struct LinkedList{
  LinkedList* next;
  int data;
}

Book says "Placing the next pointer at the beginning of the structure or class makes it easy to write generic list-handling routines no matter what the data holds."

I am not able to understand how placing the next pointer on top will help here.

Also, to make a generic list, wouldn't we need the data type as generic or say void*?

Answer 1

The book you're looking at, Programming Interviews Exposed, is (as far as I can tell) not a book on C++, but rather a book meant to prepare you to answer the kinds of questions that might be asked at a typical technical interview. I wouldn't take anything in the book as a best C++ practice unless it's labelled as such (and perhaps not even then).

The advice to put the next pointer first in a linked list node structure comes from languages like C, where you can't rely on real, compiler-supported inheritance. The idea is, in fact, to implement something like inheritance yourself by piggybacking data onto the linked list node structure. Consider:

typedef struct LinkedList {
  LinkedListNode* next;
  int type;
}

typedef struct Person {
  LinkedList listNode;
  char name[64];
  int age;
}

typedef struct Address {
  LinkedList listNode;
  char streetAddress[128];
  char city[32];
  char state[2];
  char zip[10];
}

typedef struct Employee {
  Person person;
  int department;
  int salary;
}

LinkedList here is a base type -- not good for much by itself, but useful as a starting point for nodes with more data. You don't have to know anything about the other types in order to perform linked list operations on a node... you can cast any node pointer to LinkedList* and access the information you need. So, you can have a list of Person and list of Address, and both can be manipulated with the same set of routines. Likewise, you can cast a Employee* to a Person* and use any operations that you've written for Person on Employee as well. If you assign appropriate constants to LinkedList's type field, you can even mix PersonNode and use the type field to determine the type of each node later.

This was a useful way to program 20+ years ago. It still works, of course, but most people would choose to let the compiler manage inheritance for them if they have the option, and all modern object-oriented langauges do offer that option.

Lesson: Understand the technique in case you come across it in old code, but choose a different implementation for your new code if you can.