How to acces two subsequent nodes in a linked list?

Dev Shed Forums Sponsor:

September 18th, 2012, 01:18 AM

JamesA1

Registered User

Join Date: Sep 2012

Posts: 12

Time spent in forums: 3 h 18 m 41 sec
Reputation Power: 0

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, 01:42 AM

nebelung

Contributing User

Join Date: Jun 2008

Posts: 222

Time spent in forums: 6 Days 20 h 45 m 40 sec
Reputation Power: 234

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:

Original - c Code
while ( temp->link != NULL ) { /* assuming data is of basic type */ int diff = temp->data - temp->link->data; ..... }

while ( temp->link != NULL )  {
   /* assuming data is of basic type */
   int diff = temp->data - temp->link->data;
   .....
}

September 18th, 2012, 01:49 AM

JamesA1

Registered User

Join Date: Sep 2012

Posts: 12

Time spent in forums: 3 h 18 m 41 sec
Reputation Power: 0

Thanks for the prompt answer! Much appreciated.

September 18th, 2012, 04:57 AM

JamesA1

Registered User

Join Date: Sep 2012

Posts: 12

Time spent in forums: 3 h 18 m 41 sec
Reputation Power: 0

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, 06:42 AM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,838

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 2 Days 17 h 9 m 51 sec
Reputation Power: 1774

> 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.

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

September 18th, 2012, 07:21 AM

bdb

Contributing User

Join Date: Aug 2012

Posts: 156

Time spent in forums: 1 Week 15 h 48 m 11 sec
Reputation Power: 32

Quote:

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, 07:47 AM

nebelung

Contributing User

Join Date: Jun 2008

Posts: 222

Time spent in forums: 6 Days 20 h 45 m 40 sec
Reputation Power: 234

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:

Original - c Code
dummy = temp->link->link; free(temp); temp = dummy; ..... temp=temp->link;

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:

c Code:

Original - c Code
temp->link = dummy;

temp->link = dummy;

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:

Original - 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 09:37 AM.

September 19th, 2012, 02:24 AM

JamesA1

Registered User

Join Date: Sep 2012

Posts: 12

Time spent in forums: 3 h 18 m 41 sec
Reputation Power: 0

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!

How to acces two subsequent nodes in a linked list?

Developer Shed Advertisers and Affiliates