Array of pointers confusion with skip list

Question

I think I have a basic understanding of how skip lists work, but being new to them in addition to being a C-beginner has me confused on a few points, especially the initialization of the list. Here's the code I'm trying to follow:

#define MAXSKIPLEVEL 5

typedef struct Node {
    int data;
    struct Node *next[1]; 
} Node;

typedef struct SkipList {
    Node *header;
    int level;
} SkipList;


// Initialize skip list
SkipList* initList() {

    SkipList *list = calloc(1, sizeof(SkipList));

    if ((list->header = calloc(1, sizeof(Node) + MAXSKIPLEVEL*sizeof(Node*))) == 0) {
        printf("Memory Error\n");
        exit(1);
    }

    for (int i = 0; i < MAXSKIPLEVEL; i++)
        list->header->next[i] = list->header;

    return list;
}

I haven't done anything with arrays of pointers yet in C, so I think I'm getting a bit caught up with how they work. I have a few questions if someone would be kind enough to help me out.

First, I did sizeof(int) and got 4, sizeof(Node*) and got 8, so I expected sizeof(Node) to equal 12, but it ended up being 16, why is this? Same confusion with the size of SkipList compared to the sizes of its contents. I took the typedef and [1] out to see if either of them was the cause, but the size was still 16.

Second, why is the [1] in struct Node *next[1]? Is it needed for the list->header->next[i] later on? Is it okay that next[i] will go higher than 1? Is it just because the number of pointers for each node is variable, so you make it an array then increase it individually later on?

Third, why does list->header->next[i] = list->header initially instead of NULL?

Any advice/comments are greatly appreciated, thanks.

Answer 1

For your first question - why isn't the size of the struct the size of its members? - this is due to struct padding, where the compiler, usually for alignment reasons, may add in extra blank space between or after members of a struct in order to get the size up to a nice multiple of some fundamental size (often 8 or 16). There's no portable way to force the size of the struct to be exactly the size of its members, though most compilers have some custom switches you can flip to do this.

For your second question - why the [1]? - the idea here is that when you actually allocate one of the node structs, you'll overallocate the space so that the memory at the end of the struct can be used for the pointers. By creating an array of length one and then overallocating the space, you make it syntactically convenient to access this overallocated space as though it were a part of the struct all along. Newer versions of C have a concept called flexible array members that have supplanted this technique; I'd recommend Googling it and seeing if that helps out.

For your final question - why does list->header->next[i] initially point to list->header rather than NULL? - without seeing more of the code it's hard to say. Many implementations of linked list structures use some sort of trick like this to avoid having to special-case on NULL in the implementation, and it's entirely possible that this sort of trick is getting used here as well.