DaniWeb Forum Index > Software Development > C

C RSS

linked list question

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

linked list question

Apr 4th, 2006

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

Help with Code Tags

C Syntax (Toggle Plain Text)

x = x->next

cause the pointer to move across the list?

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
#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;
}
#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;
}

•

Join Date: Oct 2005

Posts: 287

Reputation: Clinton Portis is an unknown quantity at this point

Solved Threads: 29

Clinton Portis Clinton Portis is offline

Offline

Posting Whiz in Training

Re: linked list question

Apr 5th, 2006

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.

•

Join Date: Mar 2006

Posts: 176

Reputation: dubeyprateek is an unknown quantity at this point

Solved Threads: 22

dubeyprateek dubeyprateek is offline

Offline

Junior Poster

Re: linked list question

Apr 5th, 2006

when we write

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
while(x=x->next)
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.

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: linked list question

Apr 5th, 2006

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

Help with Code Tags

C Syntax (Toggle Plain Text)

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

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
x=x->next=(malloc(sizeof(*x));
x=x->next=(malloc(sizeof(*x));

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

Help with Code Tags

C Syntax (Toggle Plain Text)

x->next = t;

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

•

Join Date: Jul 2005

Posts: 1,673

Reputation: Lerner is a name known to all

Solved Threads: 261

Lerner

Offline

Posting Virtuoso

Re: linked list question

Apr 5th, 2006

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.

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: linked list question

Apr 5th, 2006

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:

•

Join Date: Jul 2005

Posts: 244

Reputation: Drowzee is an unknown quantity at this point

Solved Threads: 5

Drowzee

Offline

Posting Whiz in Training

Re: linked list question

Apr 7th, 2006

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

Help with Code Tags

C Syntax (Toggle Plain Text)

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

Help with Code Tags

C Syntax (Toggle Plain Text)

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.

Explainer of control logic and some basics.
"If you seek to drink from a fountain of knowledge, make sure your cup is big enough."

•

Join Date: Jul 2005

Posts: 1,673

Reputation: Lerner is a name known to all

Solved Threads: 261

Lerner

Offline

Posting Virtuoso

Re: linked list question

Apr 7th, 2006

Message deleted.

•

Join Date: Jul 2005

Posts: 244

Reputation: Drowzee is an unknown quantity at this point

Solved Threads: 5

Drowzee

Offline

Posting Whiz in Training

Re: linked list question

Apr 7th, 2006

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

Help with Code Tags

C Syntax (Toggle Plain Text)

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.

Explainer of control logic and some basics.
"If you seek to drink from a fountain of knowledge, make sure your cup is big enough."

•

Join Date: Jul 2005

Posts: 1,673

Reputation: Lerner is a name known to all

Solved Threads: 261

Lerner

Offline

Posting Virtuoso

Re: linked list question

#10

Apr 7th, 2006

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.