C++

Forum

 
Linked list of structures

Jonathan100 (92)
Hello!

in C we define node :
struct Node {
int data;
struct Node* next;
};

Does next pointer is pointing to the data of the next node?

If i write:
int d = *next;
i will get the data?
jonnin (11437)
No.

the pointer is not automatically handled; you have to get memory for it first.
typically you have a load of functions to assist in using your list, like insert, delete all, delete 1, copy, whatever.

here you need
Node x;
x.data = ..;
x.next = malloc(..)
*x.next.data = ... //next is ALSO not the data, its a whole new NODE object.
You can see this if you re-read your code: next is a pointer to a NODE, not an int.
Last edited on
seeplus (6591)
next is a pointer pointing to the memory address held. In order for next to be de-referenced (*) then first next has to be set to a valid memory address of type Node. It doesn't automatically point to the data of the next node. This 'feature' has to be part of the code that initialises a variable of type Node. Often next would be set to the value obtained from an appropriate malloc()/calloc() statement.

Commonly you would have a variable (say head) pointing to the first usage of Node (the head node) with next set to NULL and then subsequently next would hold the address of the malloc()/calloc() value etc.

Consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <stdio.h>
#include <stdlib.h>

struct Node {
	int data;
	struct Node* next;
};

int main() {
	struct Node* head = calloc(1, sizeof(struct Node));

	head->data = 1;

	struct Node* newnode = calloc(1, sizeof(struct Node));

	newnode->data = 2;

	head->next = newnode;

	for (struct Node* h = head; h != NULL; h = h->next)
		printf("%i ", h->data);

	putchar('\n');

	for (struct Node* h = head; h != NULL; ) {
		struct Node* n = h->next;

		free(h);
		h = n;
	}
}


which displays:


1 2

Last edited on
Jonathan100 (92)
You can see this if you re-read your code: next is a pointer to a NODE, not an int.

i don't understand exactly what do you mean by "next is a pointer to a NODE"

if the first memory addresses in the node allocated to the data (as i assume)
it is not mean that next pointer also point to the data?
seeplus (6591)
i don't understand exactly what do you mean by "next is a pointer to a NODE"


next is of type struct Node* - ie a pointer to a type of struct Node
Jonathan100 (92)
OK, and what data this pointer is pointing to?
Last edited on
keskiverto (10402)
A pointer to Node does point to Node object.

Lets test:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <stdio.h>
#include <stdlib.h>

struct Node {
	int data;
	struct Node* next;
};

int main() {
	struct Node bbb;
	bbb.data = 2;
	bbb.next = NULL;

	struct Node aaa;
	aaa.data = 1;
	aaa.next = &bbb;

	printf("aaa %p %i %p\n", &aaa, aaa.data, aaa.next);
	printf("bbb %p %i %p\n", &bbb, bbb.data, bbb.next);
	printf("ccc %p %i %p\n", &aaa.data, aaa.next->data, &aaa.next);
}

aaa 0x500d70 1 0x500d78
bbb 0x500d78 2 0
ccc 0x500d70 2 0x500d74

On this platform the address of member data seems identical to address of the whole object.
However, type of aaa.next is struct Node* (an address), while type of aaa.next->data is int.
jonnin (11437)
this is the whole point of the linked list structure.

you have
head{data = 42 or whatever, next}
where next points to {data = 31, next}
and that ones next points to {data, next}... each one has the data you defined (can be a lot of data, here its just an int) and a next. Its a chain of the same things over and over until it hits a null pointer as a sentinel to stop the chain.
Its not just a chain of the data, its a chain of the whole node, because each one needs that next field.

maybe look at a more normal struct.
struct foo
{
int i;
double d;
float f;
};
foo *fp = malloc(...);
fp->d = 3.14;
fp is a pointer, of type foo, that holds a struct with 3 variables.

now, an important concept: a pointer is just a variable. there are special functions that work with it, but its just an integer, really. That the integer it holds happens to be an offset in ram isnt terribly important for the moment (its important, but not for what I am trying to say).

so when you add a pointer to your struct, its JUST A VARIABLE just like i,d, or f. It works the same way.

struct foo
{
int i;
double d;
float f;
bar * bp; //just a variable.
};
malloc and so forth, your fp now just has fp->bar which you can do pointer stuff to, but fp itself, THAT just holds 1 more field, nothing special about it, right?

now move it up one last time, this time, make it a pointer of the same type as the struct it is in. this is weird, but its legal, and you did that:
struct foo
{
int i;
double d;
float f;
foo *next; //STILL just a variable.
};

nothing has changed, really, except now you can trundle along forever (assuming you allocated memory for all these, of course).
fp->next->next->next->next->next.d = 3.14; ... each of those nexts is a foo.
Last edited on
kbw (9488)
Does next pointer is pointing to the data of the next node?
No.

A linked list is a "linked list of nodes". The data doesn't matter.

What's a node? The data with the links (pointers). The list can be single-threaded, where you just point to the next node, double-threaded where you can go forwards or backwards, or complex multi, where you can simultaneously maintain a fixed number of different sort orders.

The node will typically look like:
1
2
3
4
5
6
7
8
9
10
 
struct Data { // can be anything, here I've used a filename/time
    char name[PATH_MAX];
    struct timespec modify_time;
};

struct Node {
    struct Data data;
    struct Node* prev;
    struct Node* next;
};

prev/next will point to a Node or null.

Finally, picture/thousand words: https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/Linkedlist.png
Last edited on
mbozzi (3932)
it is not mean that next pointer also point to the data?

C++ allows a pointer to an object with standard-layout class type to be converted into a pointer to the first data member of that class.

If you plan on making use of this property, it would make sense to assert that the class type is actually standard-layout:
static_assert(std::is_standard_layout_v<Node>);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <stdio.h>
#include <stdlib.h>
#include <type_traits>

struct Node { 
	int data;
	struct Node* next;
};

static_assert(std::is_standard_layout<Node>::value); 

int main() {
	Node n { 42, nullptr }; 
	
	int data = *reinterpret_cast<int*>(&n); // okay, see [basic.compound]/4
	
	printf("%d\n", data); 
}

http://www.eel.is/c++draft/basic.compound#4
Last edited on
Topic archived. No new replies allowed.