How does 'next' work in linked list pointers?

[fsefsef23]

I have a homework question that instantiates 4 node pointers, *p, *q, *r, *t, and the first three have a number, 1, 2, and 3 respectively. I have to draw out (using 'blocks' and arrows) what the memory would look like when these lines of code occur:

p->next = q;
q->next = r;
t=r;
r->next = p;

r->next->next=r;

I don't really understand the usage of 'next' in regards to what it points to, nor do I get what the lines like "p->next = q" actually are changing to the values in terms of reassigning them. Any help or insight is very much appreciated!

[LevyDee]

From the looks of it, next is a pointer to the object type of what ever p, q, r and t point to. "next" is not a very common name for this that people use(i think). I like to use link. quick look at a simple object that is being used:

struct MyStruct
{
    MyStruct* next;
};

So when it says p->next = q, p's MyStruct pointer(next) now points to q.

Its kind've confusing at first. If you google something like "c++ linked list" you should be able to find some more information.

[Chilton]

Your node has a data area and a pointer, next, in this case. That pointer just holds the address of the node that follows the current one.

The node at the end of the list, its next pointer would be set to NULL/nullptr, indicating that it is indeed the end of the list.

[sashankalladi]

when you are creating a node you are allocating memory for data as well as for storing the address of next variable

[Saith]

From the looks of it, next is a pointer to the object type of what ever p, q, r and t point to. "next" is not a very common name for this that people use(i think). I like to use link. quick look at a simple object that is being used:

struct MyStruct
{
    MyStruct* next;
};

So when it says p->next = q, p's MyStruct pointer(next) now points to q.

Its kind've confusing at first. If you google something like "c++ linked list" you should be able to find some more information.

Nice job LevyDee with the explanation. To add a little to it, using LevyDee's example, you have objects that can link together to form a data structure. With any struct or class you can add other member variables to give more definition to each node (object). This is where they get the values of 1, 2, 3, etc from the previous pointers.

struct MyStruct
{
    int value; 
    MyStruct* next;
};

As you have been doing all along with structs, you add a value to the object by first creating an object and then giving that object a value.

MyStruct first, second, third;
first.value = 1;

The variable next is a pointer; as it was determined with the preceding MyStruct* data type. To use this pointer, you must make it point to another object of the same data type, MyStruct.

first.next = second;

This is important, the value of -next- of object -first- contains the address of the object -second-. This is handy as a node in a linked list are not adjacent to each other in memory. Nodes can be anywhere in memory, but to keep the linked grouped correctly the current node contains the address of the following node so the program knows where to go next; compared to an array where they are located one directly after another in memory.

If a pointer is not included, then a linked list would not be possible as the node would conclude to only a single object. To continue, you'd have to create a ton of other individual variables for the ton of individual objects that needed to be created, and then keep them all individually collected (imagine the number of parameters through a function) or find some other data structure to keep it all bundled together.

You'll be wondering why I used a . operator instead of the -> operator. This is due to the variable being a data type of type, MyStruct; not a pointer of MyStruct.

Code for a pointer of type MyStruct would look like this.

MyStruct *alpha, *beta, *omega;

alpha = new MyStruct;     // NOTE: Prior to adding values, an object first be made
alpha->value = 1;
alpha->next = &second;    // & is required as alpha is a pointer and second is an object

beta = new MyStruct;      // NOTE: Prior to adding values, an object first be made

second.value = 2;
second.next = *beta;      // points to the newly created object that is located on the heap

Hint: -> is dereferencing the pointer -to gain access- to the member variable of the object that the pointer is pointing to.

I could go on but I hope this clarifies some of what you are asking and give that insight to allow you to figure out the rest.

[LevyDee]

^ What he said lol