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; }
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; } }
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.
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.
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 } }
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 ?
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; }
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.
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!!!
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.
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?
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.
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);
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
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?
You dont need to iterate to find the long link. You always know. Its just 2 nodes behind. Unless its first or second node.
