September 18th, 2012, 02:18 AM

How to acces two subsequent nodes in a linked list?
Hi,
Just like we can access two elements in a for loop or in an array as i and i+1, assuming we have the for loop like:
for (int i = __ ; ___ ; i++)
, is there a similar way in which I can access the subsequent nodes of a linked list?
What I would like to do is to find the difference between the data field of one node and the next one but I do not know how to do that. The outline of my function is like:
node* ProcessCluster(struct node *q) {
struct node *temp;
temp = q;
while(temp>link!=NULL) {
// Access two subsequent elements here. Can I modify
// temp = temp>next in some way to access the current and
// the next element too?
}
}
September 18th, 2012, 02:42 AM

If I understood you correctly it's just a matter of double indirection
temp>link basically is a pointer to the next node wich can be dereferenced to access it's data (temp>link>data), or you can add another indirection to access the one element after the next ( i + 2 )
temp>link>link which also can be dereferenced, etc. I think you get the idea
c Code:
while ( temp>link != NULL ) {
/* assuming data is of basic type */
int diff = temp>data  temp>link>data;
.....
}
September 18th, 2012, 02:49 AM

Thanks for the prompt answer! Much appreciated.
September 18th, 2012, 05:57 AM

Hi Nebelung,
I have another question that I would like to ask, given your knowledge of linked lists.
I have a linked list of structs that stores (x,y) coordinates of start points and end points like:
Code:
struct cluster
{
float startcoord_x;
float startcoord_y;
float endcoord_x;
float endcoord_y;
};
struct node
{
cluster CLUST;
struct node* link;
};
So I am now trying to see if the distance between one point and the next is small, and if it is, then I "merge" the two nodes by rewriting the end point of the current point with the end point of the next
That is, if my list is like
Start_x Start_y End x_ End_y
10 10 20 20
22 22 30 30
and after processing, it should be like
Start_x Start_y End x_ End_y
10 10 30 30
I have done a program that can do the linked list creation, deletion and everything else, but I am now at the part where I need to find the distance from one point to the next (done) and then update/rewrite the node..and this is the part where I am stuck here. My code so far is
Code:
node* ProcessCluster(struct node **q) {
struct node *temp;
struct node *dummy;
temp = *q;
float diff = 0.0 ;
while(temp>link!=NULL) {
// Calculate distance from *end* of *current* cluster to *start* of *last* cluster
diff = sqrt(pow((temp>CLUST.endcoord_x  temp>link>CLUST.startcoord_x),2)+ pow((temp>CLUST.endcoord_y  temp>link>CLUST.startcoord_y),2));
// If distance is less than 150mm, join the two clusters
if (diff <= 100.0){
printf("Distance to next cluster is %f \n", diff);
// 1. Change the *end coordinate of CURRENT cluster* to *end coordinate of next cluster*
temp>CLUST.endcoord_x = temp>link>CLUST.endcoord_x;
temp>CLUST.endcoord_y = temp>link>CLUST.endcoord_y;
// 2. "Delete" the next node
delete temp;
dummy = temp>link>link;
free(temp);
temp = dummy;
}
temp=temp>link;
}
return temp;
}
I am completely stumped at the part labelled 2. And I have a number of problems. First, even if I comment out the entire contents of the inside of the while loop and print my list, it only shows the first node. So the way in which I am looping is changing my list. Then, I am not sure of the part where I "delete" my next node by changing the pointer of current node to point to the node after the next.
Could you give me any hints?
September 18th, 2012, 07:42 AM

> dummy = temp>link>link;
You need to be careful here, because if you're deleting say the last node of your linked list, then you're in trouble here.
> while(temp>link!=NULL)
Likewise, if the list is empty to begin with.
September 18th, 2012, 08:21 AM

Originally Posted by JamesA1
for (int i = __ ; ___ ; i++)
Code:
for (struct whatever *curr = ___; curr; curr = curr>next)
But I prefer the while option.
September 18th, 2012, 08:47 AM

I'll incorporate the astute remarks made by salem.
1. I advice you not to use float but instead use double (this was discussed a number of times in this forum and other places).
2. Although it is not directly related to you question I think that it is beneficial to define a coordinate structure it greatly enhances the readability and maintainabillity of your code.
3. It is better to avoid magic numbers define some constant to represent the minimal distance.
4.
c Code:
dummy = temp>link>link;
free(temp);
temp = dummy;
.....
temp=temp>link;
notice that after the removal of the next node you move to the one after the next (temp = dummy) and after you get out of the "if" block you again advance the temp pointer which results in double advance, I doubt that this is really what you want, so insted you should restore the link after the deletion like so:
4. Also notice what would happen if we are two elements before the end of the list and we delete the next node and think why we should add an additional condition in the while loop.
All the aforementioned ideas are incorporated into the following code (notice that I haven't compiled it so there might be errors)
c Code:
typedef struct coord
{
double x;
double y;
} Coord;
typedef struct cluster
{
Coord startCoord;
Coord endCoord;
} Cluster;
typedef struct node
{
Cluster cluster;
struct node* link;
} Node;
double computeEuclidDist (const Coord a, const Coord b)
{
return sqrt ( pow(a.x  b.x, 2) + pow(a.y  b.y, 2) );
}
/* constants */
const double MIN_DIST = 150;
....
Node* ProcessCluster(Node **q)
{
if (*q == NULL  (*q)>link == NULL) {
fprintf(stderr, "The list must contain at least two clusters\n");
return *q;
}
Node *temp = *q;
Node *dummy;
double dist;
while(temp != NULL && temp>link != NULL) {
// Calculate distance from *end* of *current* cluster to *start* of *last* cluster
dist = computeEuclidDist (temp>cluster.endCoord, temp>link>cluster.startCoord);
// If distance is less than 150mm, join the two clusters
if (dist <= MIN_DIST){
fprintf(stdout, "Distance to next cluster is %f \n", dist);
// 1. Change the *end coordinate of CURRENT cluster* to *end coordinate of next cluster*
temp>cluster.endCoord = temp>link>cluster.endCoord;
// 2. "Delete" the next node
dummy = temp>link>link;
free (temp>link);
temp>link = dummy;
}
temp=temp>link;
}
return temp;
}
Last edited by nebelung; September 18th, 2012 at 10:37 AM.
September 19th, 2012, 03:24 AM

Thanks so much for your reply nebelung.
I have learnt more from forums like these than from my classes!
I am currently implementing the function!