linked list question

[degamer106]

I wrote a program up with linked lists that creates a circular list containing 9 nodes. Each node contains a number (ranging from 1-9) as an item.

My question is...in the while loops, how does

x = x->next

cause the pointer to move across the list?

#include <stdio.h>
#include <stdlib.h>

#define FLAG 1

typedef struct node* link;

struct node {
	int item;
	link next;
}; // node containing an item and a link

int main(void)
{
	int i = 2;
	int cnt = 1;
	int N = 9; 
	int num;

	link t = (link)malloc(sizeof *t);
	link x = t;
	
	t->item = 1;
	t->next = t;

	for (;i <= N; i++)
	{
		x = (x->next = (link)malloc(sizeof *x));
		x->item = i;
		x->next = t;
	}

	puts("Enter a number between 1-9");
	scanf("%d", &num);
	while (x->item != num)
		x = x->next;

	t = x;	
	while (FLAG == 1)
	{
		if (t == x->next)
		{
			printf("\nTotal # of %d nodes\n", cnt);
			break;
		}
		x = x->next;
		printf("%d ", x->item);
		cnt++;
	}

	return 0;
}

[Clinton Portis]

I think the theory behind using while loops in linked list traversal.. goes something like this:

1. check the head pointer... if(head_ptr) then x = head_ptr ;
2. now.. assign the head_ptr to x, x = head_ptr;
3. x now points to the first node of the list.
4. traverse the list, while(x){ x = x->next; };

by continously re-assigning 'x' with the address of the next node.. you can traverse the list as desired.. until you find what you are looking for.. or until you have displayed all nodes.. or whatever you are wanting to do.

Also, by using while(x) you know the loop is going to execute until x = NULL.. which (at least in a singly linked list) emphasizes the importance of keeping the last node pointing to NULL. This might be a problem with a circularly linked list though.. because your last node will probably hold the address of the head node (thus the circular nature of the linked list) With this in mind, you would probably want to lean towards using a for(;;) loop instead.. and traverse the list until node_count < max_number_of_nodes ; for example.

[dubeyprateek]

when we write

while(x=x->next)

what happens
x starts pointing to what x->next was pointing
after that it is checked wheather while(x) is a true conition , it is true if x is not pointing to null, this is how it traverse the list.

[degamer106]

I think I addressed the question incorrectly and I failed to mention that this was a circular linked list.

After the list is generated (a circular list with 9 numbers) and there is a link between each node in the list, how does

x = x->next;

know where to point to next? Can we just assume that x->next points to the next node in the list? I really don't "see" where it is pointing.

In the very first for loop, it was made clear with

x=x->next=(malloc(sizeof(*x));

which directs x and x->next to point to a new node. Also,

x->next = t;

in the same loop, causes x->next to point to where t is pointing.

[Lerner]

Each address for each node in the circle is (usually) obtained from malloc() or new or some similar process. Each node contains the address of the next node in the circle.

If "a points to b points to c points to a" it doesn't matter where the circle starts or stops you're only going to have the same three addresses in the same sequence-- a can only point to b and b can only point to c and c can only point to a. You do need to arbitrarily have some access into the circle but once you have a single address you can get all the others until you get back to the address you started with.

[degamer106]

So, after each node is created and linked with other nodes, the links in each node will be pointing to the next one no matter what?

I stepped through the debugger after reading your post and each node had a link (in this case named next) that led to the next node so erm I think it makes sense. :cry:

[Drowzee]

That's right. Typically, a linked list is presented pictorally as a box with an arrow coming out of it pointing to another box with an arrow pointing out of it, which in turn points to yet another box.

The box is the struct or class that contains the pointer to the address of the next box. These boxes may contain other information as well.

So, once you create a node, it has a 'next' pointer (or whatever you've called it) that you direct to point to the address in memory of the next node. Then, if x is a pointer to the first node, x->next points to the second.
Typically, you should do this in the form of

x->next = new <structname>;

Which creates the next node and hooks it into the list directly after the node pointed to by x.

If you use the line

x=x->next;

You move the pointer x to refer to the second node, and now, x->next refers to the third.

You can also call something like x->next->next->next, which refers to the third node in the list after the node pointed to by x.

[Lerner]

Message deleted.

[Drowzee]

In response to the deleted message:
True enough. You don't have to do node creation using

x->next = new <structname>;

I just prefer to do so here as an example, though my statement is a little misleading. You can create a new node without attaching it to an existing linked list, but I like to make sure that I'm not losing the pointers by implementing it this way to begin with.

Of course, for node insertion I'd do things slightly differently, but I'd still be using x->next = new struct in most cases.

[Lerner]

I agree that any node added to a list is likely to originate as a result of a call to the new operator (assuming C++ instead of C) and I agree that any node added to the list will eventually be added by assignment to an existing pointer (except of course the initial node added to a list). I initially had interpreted the node->next = new <structname> line to mean always adding a new node to the end of a list when I realized it could be interpretted more generally, so I "deleted" the message. I have to admit that I haven't seen the process of assigning a new address directly to a list before. I have always seen a new address assigned to a temp holding node, then initializing the temp holding node member(s) with the desired value(s) and then adding the temp holding node in the desired location of the list; but that may be more my lack of worldly sophistication than any feature of reality. Sorry about the confusion.

[Drowzee]

I'm fairly confident with making/destroying linked lists (one of my few strengths compared to other inexperienced coders), but I see what you mean.

For the first node you'd certainly use a method of creating the head node pointer then linking it to the first node, but after that, you can use a temporary pointer to point to the new nodes and link if you're wanting to perform an insertion rather than an append. For supporting inserts, that's actually a bit clearer. Otherwise, you would create pointers to nodes before and after the insert point to keep track of the rest of the list while you added nodes, which is trivially more expensive in terms of memory.