1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Linked lists

Discussion in 'C++' started by coolio2006, Aug 25, 2006.

  1. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Hi - i just needed some help. I'm constructing a circular linked list which means 1st node points to 2nd, and so on. The task i need to accomplish is that i need to remove one node (any node in the linked list). So lets say i have 8 nodes in my circular linked list and i want to remove the 4th node. We know that the 4th node points to the 5th node. Anyway, my current function has no problem with deleting any node except for the 2nd no. No matter what I try to do, I cannot delete the 2nd node. Here is my function: Im sorry if there isn't enough info here, but you can ask and i'll be happy to reply back. Thanks.



    Code:
    node* prev = current; // current is the head of the linked list – im making a pointer prev to 			//also point to head
    node* cur; // just another pointer
    
    
    
    
     cur = prev;  // let cur also point to the head of the linked list
    
     for (int i=1; i <= size(); i++) // size is the size of the linked list
    
     {
     if (prev -> num == x ) // x is the node I want to delete – so if the first node contains the                  //data (num is the data field of the node) – then do the following
      {
    
      cur -> shortlink = prev -> shortlink ;
      delete cur;
      length--;
      }
      cur = prev;
      prev = prev -> shortlink;
      
    
     }
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    What is the problem you are facing when trying to delete the 2nd node.
     
  3. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I'm not too sure what the problem is but it won't allow me to delete the 2nd node. I tried another piece of code but now when i try to delete node 1, it deletes node 8 (the last node), and if i delete node 8, nothing happens.
    The code is here: Keep in mind that current is the head pointer pointing to the first node. Disregard my linker and longlinker pointer, that's doing something else. x is the node which the user chooses to delete. Shortlink is the pointer that points the node to the next node.

    Code:
    void ring::remove(int x)
    {
    node* prev = current -> shortlink;
    node* cur = current;
    node* linker = current;
    node *longlinker = current;
    
    
    
     //cur = prev;
     for (int j = 1; j < length; j++)
     {
     linker = linker -> shortlink;
     }
     
     for (int k = 1; k < length; k++)
     {
     longlinker = longlinker -> shortlink;
     }  
    
     for (int i=1; i < length ; i++)
    
    
     {
     if (prev -> num == x)
      {
      cur -> shortlink = prev -> shortlink ;
      linker = prev -> shortlink;
      longlinker -> longlink= prev -> longlink;
      delete prev;
      length--;
      }
      cur = prev;
      prev = prev -> shortlink;
     } 
    
    
    }
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    Probably you are missing some operation to find the exact node as its deleting the other ones.

    Here is the code to delete a node.
    Code:
    node* del(node *current)
    {
    	/***************************************************/
    	/***** FUNCTION FOR DELETION OF SPECIFIED NODE *****/
    	/***************************************************/
    	int rno;                         /* Roll number for deleting a node*/
    	node *newnode,*temp;
    	printf("\nEnter the number whose node you want to delete\n");
    	scanf("%d",&rno);
    	newnode=current;
    	if(current->roll_no==rno)
    	{
    		/***  Checking condition for deletion of first node  ***/
    		newnode=current; /*  Unnecessary step  */
    		current=current->next;
    		free(newnode);
    		return(current);
    	}
    	else
    	{
    		while(newnode->next->next!=NULL)
    		{
    			/***  Checking condition for deletion of   ***/
    			/*** all nodes except first and last node  ***/
    			if(newnode->next->roll_no==rno)
    			{
    				temp=newnode->next;
    				newnode->next=newnode->next->next;
    				free(temp);
    				return(current);
    			}
    			newnode=newnode->next;
    		}
    		if(newnode->next->next==NULL && newnode->next->roll_no==rno)
    		{
    			/***  Checking condition for deletion of last node  ***/
    			free(newnode->next->next);
    			newnode->next=NULL;
    			return(current);
    		}
    	}
    	printf("\nMatch not found\n");
    	return(current);
    }
    Also first node needs special care.
     
  5. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Is that deleting the nth node (which can be any random node) or a particular one?
    Nevermind that question actually.
    Ok i sort of understand that but not all that much to apply it to my scenario. My linked list has no end node, so therefore no "NULL" - could you help me please?
    Could you have a look at my code and see if i'm doing something stupid in there which i've missed.
     
    Last edited: Aug 26, 2006
  6. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I've properly commented my code so hopefully this will help you a little further:

    Code:
    void ring::remove(int x)
    {
    node* prev = current -> shortlink; // current is pointing to the first node in the linked list 
    node* cur = current; // cur now also points to the first node in the linked list
    node* linker = current; // as does linker
    
    
    
    
     //cur = prev;
     for (int j = 1; j < length; j++) // this loop is to determine that if the first node gets deleted - then linker will point to the last node
     {
     linker = linker -> shortlink;
     }
     
    
     for (int i=1; i < length ; i++)
    
    
     {
     if (prev -> num == x) // if the first node holds true for this condition
      {
      current = current -> shortlink; // so if the if condition was met - then current now points to the 2nd node 
      cur -> shortlink = prev -> shortlink ; // cur now also points to the 2nd node - 
      linker = prev -> shortlink; // this ensures that the last node doesn't point to 1 anymore, but actually to 2
      delete prev; // delete the reference to the 1st node - technically now, nothing should be pointing to the 1st node
      length--; -- decrease the size of the list to n-1
      }
      cur = prev;
      prev = prev -> shortlink; // if the if statement wasn't satisfied - move prev along to point to the 2nd node
     } 
    
    
    }
     
  7. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    What does "free" mean in the code you gave me ? Is it just delete?
    If so, how can you delete something like newnode -> next -> next ?
     
  8. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    This is my attempt at that code to try and make it in terms of fitting it into mine, but no node is getting deleted but rather nodes are merely just getting rearranged. Could someone help please?

    Code:
    node *newnode = current;
    node *temp;
    node *start = current;
    
    if (current -> num == x)
    {
    current = current -> shortlink;
    delete newnode;
    }
    
    else
    
    while (newnode -> shortlink -> num != start -> num)
    {
    if (newnode -> shortlink -> num == x)
    {
    temp = newnode -> shortlink;
    newnode -> shortlink = newnode -> shortlink -> shortlink;
    delete temp;
    }
    newnode = newnode -> shortlink;
    }
    if (newnode -> shortlink -> shortlink -> num == length && newnode -> shortlink -> num  == x)
    {
    delete newnode -> shortlink -> shortlink;
    newnode -> shortlink = start;
    }
     
  9. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    Thats a general concept of deleting a node and NULL means last node if your one is cyclic you can check the value of the next pointer to be equal to the header and that means you have travelled the complete list to find the data.

    Yes free is actually similar to delete in C++. and we can delete any node using newnode -> next -> next because in the structure next means the address to the next node and we can delete the next to next node.

    I hope this clears your queries to some extent.

    Regarding your code you mentioned
    Code:
    for (int j = 1; j < length; j++) // this loop is to determine that if the first node gets deleted - then linker will point to the last node
     {
     linker = linker -> shortlink;
     }
    But I dont see any thing related to deleting but it just loops through all the element and breaks assigning wrong value to your variable linker.
     
  10. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0

    for (int j = 1; j < length; j++) // this loop is to determine that if the first node gets deleted - then linker will point to the last node
    {
    linker = linker -> shortlink;


    That piece of code is correct. What's thats doing is, it's getting the node before the node deleted and making it point to the node after the deleted node. So if i delete node 1, then node 8 will point to 2 and not 1.
    Ah!!! I notice my problem now - i'm not decreasing the length variable when a node is getting deleted - stupid me!!

    OH ITS WORKING LIKE A DREAM - Mate, you got no idea how much i appreciate your help!!! I've been tossing all over the house for 2 days tryin to figure this crap out!!!
     
    Last edited: Aug 26, 2006
  11. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    But I see an error. It just cycles through all the element without doing anything. In the process of cycle it changes the linker as you are looping one time less than total nodes.
     
  12. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I have another question. If i remove all the nodes in the linked list, how would i go about actually displaying that there's nothing left?
     
  13. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Ok where exactly do you see that?
     
  14. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    If counter is zero output a message
    In the loop I pointed out.
     
  15. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I have a slight issue yet again. The code is:

    Code:
    for (int z = 1; z <= length; z++)
    {
    if (longlinker -> longlink -> num == number)
    {
    longlinker -> longlink -> num = number;
    }
    else
    {
    longlinker = longlinker -> shortlink;
    }
    Now, assume the linked list has 6 nodes. Each node has 2 links, one to it's next node, and one to it's 3rd node after itself. So, 1 points to 2 (shortlink) and 4(longlink), 2 points to 3 (shortlink) and 5 (longlink), and 3 points to 4 (shortlink) and 6 (longlink).

    Anyway i got an integer value "number" which is holding the correct information in it. I need to be able to make node 6 have a long link to itself when node 3 is deleted (as node 3 points to 6). The problem i'm having is that when i delete node 3, node 6 is still pointing to node 3 and not itself. The "num" you see there is the value of the longlink number each node has. Any ideas to see what i'm doing wrong?
    I know "number" is holding the correct value in there (which is 6 when 3 gets deleted), as i've tested it just before the for loop with a cout statement. Once it gets into the for loop, it cannot access "number" variable. Any ideas?
    Basically, all i'm trying to do is go through each node in the list, and if that node's longlink number equal to the number variable, then update the number.
     
    Last edited: Aug 26, 2006
  16. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0

    I've tried other pieces of code and changing it slightly, but the number variable refuses to go into my do/while loops, or my while or for loops. Why is that? "number" is declared in the function itself.

    The other code i came up with which is not working is:

    Code:
    do
    {
    cout << "your mom " << number << endl;
    if (longlinker -> num == number)
    longlinker -> longlink -> num = number;
    longlinker = longlinker -> shortlink;
    }
    while (longlinker -> shortlink -> num != start -> num);
     
  17. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Can anyone help me out please?
     
  18. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    734
    Likes Received:
    37
    Trophy Points:
    0
    I guess you are making the simple thing a bit more complex. If you ara using shortlink as well as long link deleting a node becomes a large process.

    As you mentioned in the example
    "3 points to 4 (shortlink) and 6 (longlink)"

    So now when deleting a node you need to keep in mind the following.

    1. Mark the node for deletion. Lets say its node 4
    2. Update the links that can point to the node we are deleting. In your case the short link as well as the long link. As we are deleting node 4 you need to first update node 3 for its short link and node 1 for its long link
    3. Now safely remove the node.

    Also if the if condition is not satisfied then it will not execute the if block. That means your number is never equal to longlinker -> longlink -> num
     
  19. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for your feedback coderzone. Just let me know if this approach is right (well i'm assuming it's not as it's not working). Assuming the linked list has 8 nodes and 3 k (k being the longlink).
    I find the node for deletion (lets say node 4). I make node 3 point to node 5 (that works well). Then what i'm doing is, i'm saving the actual longlink of node 4 (into the variable int number - which should store 7 - and it does with the testing i've done). Once i've saved my node number, i iterate through the list to see which nodes longlink is pointing to 4, and i update the longlink of that node to the value of 7. So technically, the node i've found through iteration that was long linking to 1 should now actual have the value 7.
    Now, i notice that the number variable is storing what i want it to store, but when i try and use that number variable in my for (or my do while loop) - it just cannot access it - i.e. the if statement doesn't recognise the data in number?
    Isn't that correct?
     
  20. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    734
    Likes Received:
    37
    Trophy Points:
    0
    You dont need to iterate to find the long link. You always know. Its just 2 nodes behind. Unless its first or second node.
     

Share This Page