#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    12
    Rep 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?

    }


    }
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2008
    Posts
    222
    Rep Power
    236
    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;
       .....
    }
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    12
    Rep Power
    0
    Thanks for the prompt answer! Much appreciated.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    12
    Rep 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?
  8. #5
  9. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    > 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
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2012
    Posts
    156
    Rep Power
    34
    Originally Posted by JamesA1
    for (int i = __ ; ___ ; i++)
    Code:
    for (struct whatever *curr = ___; curr; curr = curr->next)
    But I prefer the while option.
  12. #7
  13. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2008
    Posts
    222
    Rep Power
    236
    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:
    c Code:
    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:
    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.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    12
    Rep 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!

IMN logo majestic logo threadwatch logo seochat tools logo