Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Deleting nth node from linked list

c++ linked list delete

This topic has been archived. This means that you cannot reply to this topic.
6 replies to this topic

#1 jasonalien

jasonalien

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 194 posts

Posted 24 February 2013 - 11:29 AM

Hi, I'm trying to make some linked list functions. I found and tried to edit a function which is supposed to delete nth item in a linked list but it deletes (n+2)th item. Can you tell me how to solve this please? Thanks in advance

Here is the function :


ListNode* deleteList(ListNode* node,int n)
{
    ListNode *p, *mycurrent, *pre;
    p = node;
    pre = p;
    mycurrent = node;
    for(int i = 1; i < n; i++)
    {
        
        mycurrent=mycurrent->next;

        if(mycurrent->next==NULL)
        {
            node = p->next;
            delete p;
            return node;
        }

        mycurrent = mycurrent->next;
        p = pre->next;
        while(mycurrent->next)
        {
            p=p->next;
            mycurrent = mycurrent->next;
            pre= pre->next;
        }
        pre->next = p->next;
        delete p;
        return node;
    }

}

 



#2 0xDEADBEEF

0xDEADBEEF

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 790 posts

Posted 24 February 2013 - 11:40 AM

I looks a little complicated to me.

 

If you want to delete the n'th node, you have to walk over n-1 nodes, then set (n-1)->next to (n-1)->next->next.

 

somthing like:

Node *p = head;
for(int c=0;c<n-1 && p!=NULL;++c)
{
    p = p->next;
}
if(p!=NULL) {
    if( p->next!=NULL) {
        Node *todel = p->next;
        p->next = p->next->next;
        delete todel; //free(todel);
  } else {
        delete p; //If n = 0 && its the last element, delete it
  }
}

Creating SEGFAULTs since 1995.


#3 BlackRabbit

BlackRabbit

    CodeCall Legend

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3871 posts

Posted 24 February 2013 - 11:46 AM

Why does the loop start at 1? and why don't you have a positionate function :D

 

which would make it simpler, first call to positioning in the list, and then delete the current item, if not null



#4 jasonalien

jasonalien

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 194 posts

Posted 24 February 2013 - 12:10 PM

I solved it using this :


ListNode* deleteList(ListNode* node,int n)
{
    ListNode *first1, *n_th_node, *save;
    int count = 0;
    save = first1 = n_th_node = node;
    while(first1->next)
    {
        first1 = first1->next;
        count++;
        if(count == (n-1))
        break;
    }


    while ( first1->next != NULL )
    {
        first1 = first1->next;
        save = n_th_node;
        n_th_node = n_th_node->next;
    }

    save->next = n_th_node->next;
    free(n_th_node);
    return node;



}

But I couldn't understand what's happening here. Could you please explain this part to me (I'm pretty newbie at C++ and I'm a slow learner)?

    while ( first1->next != NULL )
    {
        first1 = first1->next;
        save = n_th_node;
        n_th_node = n_th_node->next;
    }

    save->next = n_th_node->next;
    free(n_th_node);
    return node;



#5 0xDEADBEEF

0xDEADBEEF

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 790 posts

Posted 24 February 2013 - 02:07 PM

Are you sure that's working??

 

Its appears to find the n-1 node, then scans to the end of the list whilst scanning from the start of the list. Once it gets to the end of the list it will delete the m'th item (where m is len - (n-1).)

 

That is a far to complicated a function.

 

Why don't you try writing out the steps you think you need todo to accomplish this task. Then we can help convert the steps into C++. Each step will be a code fragment, so you'll be able to understand what's going on. At the moment the code looks like there's a distinct lack of understanding.


Creating SEGFAULTs since 1995.


#6 Ritwik I the programmer

Ritwik I the programmer

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 244 posts

Posted 24 February 2013 - 06:29 PM

Bahadirtr, what your code does is first store the nth node in first1, and then in the 2nd for loop, store the last node in first1, size - n th node in save, and size - n +1 th node in  n_th_node. Then, as Evan said, it deletes the size - n + 1th node. i do not see how this would delete the nth node. What you simply need to do is traverse to the n-1 th node, set its link to the link of its link, and delete its previous link. Evan has already given you the code to do so.


I can believe, but why should I?


#7 jasonalien

jasonalien

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 194 posts

Posted 24 February 2013 - 09:08 PM

Evan's code solved my problem, thanks for explaining the code, that helped me to understand what it does better :)






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download