CODEWITHSUNDEEP
cpointerslinked-listnodes
Parveez Ahmed
Parveez Ahmed

Reputation: 1417

What is the size and lifetime of a node in a linked-list implementation in C?

In a linked-list implementation in C (or C++), what is the size of the node and lifetime of pointer variable? For example: 

struct node
{
  int data;
  struct node *next;
}*ptr=NULL;

Now I want to know the size of the node: is it 4 bytes, and if so, how? Secondly, how long does the pointer live: throughout the execution of the program? Lastly, is it proper to call *ptr an instance variable or data member or an object?

Upvotes: 1

Views: 4194

Answers (3)

Edwin Buck
Edwin Buck

Reputation: 70909

It is not possible to generally know the size of the node. However, you can know the size of the node at compile time, for a specific platform and set of libraries.

sizeof(struct node)

will tell you the size of the node. Note that it might not be the actual size of all of the members within the node combined. Occasionally, padding is necessary to have the members within the struct align on memory alignment boundaries necessary for proper operation.

In addition, pointers do not have a specific size. They are large enough to accommodate the required memory address, but that's the only requirement that they must satisfy. There are dramatic differences in pointer size between 32-bit and 64-bit environments, and even if not shifting between two supported bit-ness environments on the same hardware, different hardware platforms may have different memory requirements to store a pointer value.

Where you get the "4 bytes to store a pointer" is from the popular misconception that all computers that use C are Intel CPUs, in the Pentium family of chips, which can only run 32-bit code. It was an untrue assumption back then, and it's equally untrue to assume it now.

Even after that is taken into account, arrays of the struct might require between-array-element padding for correct memory alignment. As a result, even if you know the size of the struct, you cannot assure that an array of X elements will fit in a memory area of X * sizeof(struct node) bytes.

Use sizeof(...) to find the answer you seek, but make sure that pretty much everything you want to take the size of is in the sizeof(...) operator.

As far as the life of the pointer, it lives as long as the program is running; however, the value stored in node->next might not actually reference a meaningful address. node->next is designed to hold an address, but there are far too many ways to trick node->next to point to addresses that do not specify the beginning of a pattern of bits which satisfy the needs of a struct node.

This "problem" with the C language was fixed to some degree in subsequent languages meant to "improve" upon C, by making pointer-type operations impossible. Instead the languages allowed the safe sub-set of pointer operations, which meant that you really didn't have a pointer (so they called it a reference). Java and C# are two such languages, but there are many that deny the truly dangerous operations on pointers.

It is not proper to call a pointer an instance of a variable, because it really is a variable that holds a memory address. There is no strict requirement that the memory address it holds contains a bit pattern that will satisfy the "type" of the pointer. It's just one of those legacy C issues, which C++ preserved in order to be compatible with C. Also, an instance variable tends to suggest object-oriented terminology, and C cannot (in its default form) provide object-oriented guarantees, so applying object-oriented-programming terminology to C is inappropriate.

Likewise, a struct is not a class, and members of the struct are subject to slightly different rules than members of a class. The biggest "slightly different" rule is that members of a struct are generally publicly accessible, unless you actually take great care to hide the declaration of the struct from the rest of the program (which will require a lot of C gymnastics to do and make your program still work).

Upvotes: 4

Gibbs
Gibbs

Reputation: 22964

Sizeof is a compile time operation . Node is a structure . So size of node is the summation of all the members size in the structure . So u have an integer and a pointer . Size of node is size of integer + size of pointer . Lifetime : memory is allocated dynamically . Until you call free , node lives . If u perform a delete operation , Good programmer style us used to free the memory allocated for that node .

Upvotes: 0

Lidong Guo
Lidong Guo

Reputation: 2857

  1. The size of node depends on your computer and compiler. Use sizeof(struct node); to get it. It is not 4 bytes. In a 32-bit environment, it is 8 (4 bytes for int and 4 bytes for struct node *).

  2. The ptr lives throughout the execution of program. ptr is a global variable.

  3. ptr is an instance variable while *ptr means the memory ptr points at.

Upvotes: 2

Related Questions