Data Structure Patterns

Teaching and books have a profound impact on how we think and solve problems.

In college when I learnt data structures, I was taught to embed the element in the data structure (list)

struct x {
 struct x *next, *prev;
 int element;
};

But I soon realized that I did not always want "int" as the type of the element, so I learnt the magical type void *

Here is another way to achieve the same thing

struct list {
 struct list *next, *prev;
};

struct y {
 int element;
 struct list l;
};

This way, I could embed the list in anything without building any type information in list. Cool right?

If tomorrow I decided to use a tree, I could simply change

struct y {
 int element;
 struct tree t;
};

This way the impact on my code for "y" is minimal. In the traditional approach, I would have to use

struct tree xt {
 int element;
 struct tree *left, *right;
};

and redo most of the code.

The moral of the story

Embed the data structure in the data type and not the other way around

Figure illustrating the differences b/w embedding the data type in the data structure versus embedding the data structure in the data type