When doing a linked list of chars with just a single character do you think it's better to use pointers in your struct like this?

Typedef struct String_Node
{
    Struct String_Node* next;
    Struct String_Node* prev;
    int id;
    char* c;
} String_Node_t;

Or better to not use a pointer with the char like this?

Typedef struct String_Node
{
    Struct String_Node* next;
    Struct String_Node* prev;
    int id;
    char c;
} String_Node_t;

To access the char using a pointer the pointer must be dereferenced, which is additional work for the processor. The size of a pointer is also larger so might consume more memory, but it depends on how it's laid out in memory. As the char is inside a struct, and I would expect the struct to aligned to an addressable space, the difference between a pointer size and char size isn't going to be an issue. I'd guess your example without a pointer is going to be slightly more efficient.

Edited 3 Years Ago by LaxLoafer

Either one would work, and neither will negate the very clear issue of having two pointers and an integer for every character stored in the list. This is excessive memory usage that can and probably should be mitigated by storing an array of characters in each node rather than a single character.

Edited 3 Years Ago by deceptikon

the difference between a pointer size and char size isn't going to be an issue.

sizeof(char) == 1
sizeof(char*) == 4 (except Turbo C compilers where it could be either 2 or 4)

That's quite a bit of difference, especially if there are thousands of nodes in the linked list.

That's quite a bit of difference, especially if there are thousands of nodes in the linked list.

But don't compilers typically like to pad structs so that they are aligned a certain way (Like making the size a multiple of four)? Assuming an environment where sizeof(int) == 4 and the size of a pointer is four, wouldn't the latter struct have three bytes of padding on the end, making them effectively the same size?

That being said, the one without the char* is more desirable. Having an extra pointer like that just means more to allocate, more to clean up, and more to dereference.

Edited 3 Years Ago by Tumlee

But don't compilers typically like to pad structs so that they are aligned a certain way (Like making the size a multiple of four)?

Typically, yes, though how padding is added and how much greatly depends on the compiler. It also depends on the ordering of the structure's members.

Of more concern than char versus char* is that each node only holds a single character, yet there's memory allocated for two links and an integer ID on top of that character. It may be easier to reason about such a linked list, but it's terribly wasteful of memory.

This article has been dead for over six months. Start a new discussion instead.