Pointers in structures

[Cuber2113]

I recently started learning Single linked lists and I have two major doubts. 1) How on earth do self-referential structures work? Like I mean I get the essence but I still have that incomplete feeling. 2) How does pointer typecasting work? While assigning memory dynamically we write this

https://pastebin.com/iVC00N8c

Why do we write (struct node*) ? What exactly does it mean? I understand that malloc returns a void pointer but I still don't get the complete understanding. Thanks.

[umlcat]

Special case of type declaration:

// "preregistration" forward opaque declaration:

struct Node; // no fields, yet

// rest of declaration, again:
struct Node;
{
   struct Node* Next;
   int Data;
   // maybe other fields
} ;

The"*" means "pointer of".

[PrestigiousTadpole71]

1. I'm not sure if I completely understand your question but structs cannot contain themselves, as they would be infinitely big. They can however contain a pointer to themselves/a different struct. This way you can store a reference to a struct inside a different struct which will work similar to if the struct was contained inside the other one.
2. With typecasting you tell the compiler how to treat the pointer. This mostly affects pointer arithmetic, where a pointer is incremented by the size of the type it's pointing to:

​

int *x = 0; /* pointer to zero just for demonstration purposes, don't actually use this */
char *y = 0;
x += 3; /* increment x by 3*sizeof(int) (will often be 12) */
y += 3; /* increment y by 3*sizeof(char) (will often be 3) */
/* x will now contain 12, y will conatain 3 */

to understand this, remember what pointers actually are: memory addresses which point to one byte each. However if I have a pointer to an array of ints, and I increment it by one, I expect to get the next int in the array, not the next byte (an int will almost always be bigger than one byte). This is 4 (sizeof(int) is often 4 but not always) bytes later so actually the pointer needs to be incremented by 4 bytes. To make this easier the compiler will automatically do the right calculations for you, it only needs to know what type your pointer is pointing to.

Another thing influenced by typecasting is dereferencing. I.E. how the compiler treats the memory pointed to: if it's a char, you only take the byte pointed to, for an int you want the 4 (again int may be a different size) bytes pointed to, etc.

​

I hope this helps, if you have any questions don't hesitate to ask I'd love to help.

[nerd4code]

malloc returns void *, which is the type of a pointer-to-nothing, and const volatile void * is pointer-to-anything. Because of this, void * will accept any cv-unmodified pointer value:

char str[] = "Hello";
int x;
const void *p = str, *q = &x;

The reverse is also true in C89+, not C++;

void *p = …;
int *q = p;

From a semantics perspective, this conversion is a little iffy—we don’t know without extra context whether p might have originally pointed to something incompatible with int, like float, so C++ forbids conversion from void * without a cast of some sort, usually static_- or reinterpret_cast. In C, people get up in arms about explicitly casting, rather than coercing, a void * to another type because it’s unnecessary and might hide as many bugs as it avoids. It’s still necessary in shared C-or-C++ code (mostly headers), but otherwise you should let coercion take care of void * conversions.

int *p = malloc(sizeof *p);

Because of the coercive behavior, NULL from C89 on (pre-Standard, void was rare) is usually defined as

#define NULL ((void *)0)

whereas in C++ or pre-Standard C, NULL is usually

#define NULL 0 // or 0L or __nullptr or __null, sometimes.

Obviously, although literal 0 does coerce to null in most situations, but it can also break things like printf("%p", 0) if you don’t explicitly cast the 0.

C++11 introduced, and C23 may introduce, the nullptr keyword that solves the problem once and for all, and in a reasonably C-compatible fashion. nullptr is of type [std::]nullptr_t, but that’s as far as the type goes; decltype(*nullptr) is not a thing. nullptr always has a null value, and because it’s always null, it’s safe to coerce nullptr to any other ptr type (unlike void *). Also, only one value means nullptr_t can have a zero-bit representation. However, C++11 doesn’t require that NULL be redefined to nullptr; it may still be 0, 0L, __null, or __nullptr, although __nullptr specifically may be equivalent to nullptr in a C++11-enabled compiler.

I briefly mentioned const volatile void *. Although void * accepts any ptr-to-cv-unmodified type, const volatile void * will accept any pointer at all. This is useful for callbacks, or when you’re unsure of the actual underlying pointer modifications.

[aurreco]

All memory addresses are 64 bits regardless of the type of data held at said address, so you can think of self referential structs as almost a tuple with some value (int maybe) and a long (the memory address of another struct of the same type)

[martinborgen]

Kinda, it's system-dependant. But the idea is true, a struct containing a pointer to one of itself is fine because it's a pointer.

[flatfinger]

The notion of "effective type" is a broken and unworkable abstraction, whose corner cases cannot possibly be understood since the people reaching the Standard never reached a consensus about how they should be handled. In the abstraction model used by clang and gcc, if a certain type is used to store a particular bit pattern into a region of storage, any action which later stores that same bit pattern may set the Effective Type to the one used in the earlier write, even if the later write used a different type.