Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Linked lists (http://www.go4expert.com/forums/linked-lists-t1260/)

coolio2006 25Aug2006 14:15

Linked lists
 
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;
 

 }


shabbir 26Aug2006 12:15

Re: Linked lists
 
What is the problem you are facing when trying to delete the 2nd node.

coolio2006 26Aug2006 13:01

Re: Linked lists
 
Quote:

Originally Posted by shabbir
What is the problem you are facing when trying to delete the 2nd node.

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;
 }


}


shabbir 26Aug2006 13:28

Re: Linked lists
 
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: C

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.

coolio2006 26Aug2006 13:40

Re: Linked lists
 
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.

coolio2006 26Aug2006 14:16

Re: Linked lists
 
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
 }


}


coolio2006 26Aug2006 15:15

Re: Linked lists
 
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 ?

coolio2006 26Aug2006 15:27

Re: Linked lists
 
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;
}


shabbir 26Aug2006 15:40

Re: Linked lists
 
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.

coolio2006 26Aug2006 15:49

Re: Linked lists
 
Quote:

Originally Posted by shabbir
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!!!


All times are GMT +5.5. The time now is 05:40.