Given only a pointer to a node to be deleted in a singly linked list, how do u delete it?

Discussion in 'C Programming' started by ac.c.2k7@gmail.com, Apr 14, 2007.

  1. Guest

    Hello Everyone,

    The solution to this is to copy the data from the next node into this
    node and delete the next node!.
    1. But if the node to be deleted is the last node. Then what should we
    do ?
    2. If the list is Head node?
    3 If the list is circular then what all conditions we need to check?

    Thanks,
    kaka
     
    , Apr 14, 2007
    #1
    1. Advertising

  2. said:

    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.


    No, the solution is to re-design the interface to the deletion routine
    so that you get sufficient information supplied to you to enable you to
    do the job properly.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Apr 14, 2007
    #2
    1. Advertising

  3. On Apr 14, 10:38 am, "" <> wrote:
    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.


    Not necessarily. You could mark the node for future deletion and then
    check if the next node was marked previously and delete that one since
    you have the pointer to it.

    > 1. But if the node to be deleted is the last node. Then what should we
    > do ?


    Just mark it.

    > 2. If the list is Head node?


    Since you have the pointer to it, you can delete it immediately.

    > 3 If the list is circular then what all conditions we need to check?


    You need to check if the head node is the next node and adjust it
    accordingly.

    Hope this helps....karl m
     
    Karl Malbrain, Apr 14, 2007
    #3
  4. On Apr 14, 10:38 am, "" <> wrote:
    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.
    > 1. But if the node to be deleted is the last node. Then what should we
    > do ?


    If you use an empty "stopper" node at the end of your list, you'll
    never get the "last" node for deletion and your solution works fine.

    > 2. If the list is Head node?


    Set a new head and delete it.

    Hope this helps, more..... karl m
     
    Karl Malbrain, Apr 14, 2007
    #4
  5. Re: Given only a pointer to a node to be deleted in a singly linkedlist, how do u delete it?

    On 2007-04-14 19:38, wrote:
    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.


    Scan the list from head until you find the node to delete and delete it
    just like you'd delete any node in a single-linked list.

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Apr 14, 2007
    #5
  6. monty Guest

    HI friends
    Start from the header node and traverse the linked list
    storing two pointers
    the current node and previous node .If current node
    becomes deletion node
    delete it and attach the previous node to the next of
    current node.

    1 if header node is deletion node then simply delete it and point the
    next node to be the header node.
    2If last node is deletion node above process will work
    3. In case of circular list move until current node becomes deletion
    node.Remember start from previous note assignment thru
    header.
     
    monty, Apr 15, 2007
    #6
  7. monty said:

    > HI friends
    > Start from the header node and


    In other words, change the spec. Absolutely right.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Apr 15, 2007
    #7
  8. Snis Pilbor Guest

    On Apr 14, 1:38 pm, "" <> wrote:
    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.
    > 1. But if the node to be deleted is the last node. Then what should we
    > do ?
    > 2. If the list is Head node?
    > 3 If the list is circular then what all conditions we need to check?
    >
    > Thanks,
    > kaka


    People have already pointed out various ways to do this, so I won't
    further elaborate on them; what I will do is point out what's wrong
    with the above.
    In any program of significant size, you're liable to have other
    pointers besides those pertaining to the linked list itself, pointing
    to the "next node" (the one which your solution says to delete).
    You'd have to painstakingly find every last thing which can point to a
    node in your list, and handle it accordingly, or else after the "next"
    node is deleted, you may have other pointers floating around still
    pointing to it.

    Example: your "nodes" are soldiers in a battlefield videogame. The
    list is periodically run through to make all the soldiers do their
    thing. But the battlefield also has machineguns, and each machinegun
    actively targets a specific soldier-- which is handled by having the
    machinegun structure include a "struct soldier_data *target." A
    soldier dies, who was being targeted by a machinegun; the soldier is
    deleted from the list in the method you described, and now the
    machinegun's "target" pointer is pointing to undefined data. When it
    comes time for the machinegun to shoot, your program crashes (in best
    case scenario- or does even worse things, possibly).
     
    Snis Pilbor, Apr 15, 2007
    #8
  9. R Smith Guest

    "" <> wrote in
    news::

    > Hello Everyone,
    >
    > The solution to this is to copy the data from the next node into this
    > node and delete the next node!.
    > 1. But if the node to be deleted is the last node. Then what should we
    > do ?
    > 2. If the list is Head node?
    > 3 If the list is circular then what all conditions we need to check?
    >
    > Thanks,
    > kaka
    >


    This is really simple. If you start from the beginning of the list:

    if (begin_ll == delete_node) /* single entry */
    {
    free (begin_ll); /* and any data */
    begin_ll = (LNK_LST_NODE *) 0;
    return;
    }

    /* otherwise */

    for (prev = begin_ll; prev; prev = prev->next)
    {
    node = prev->next;
    if (node->next == delete_node)
    {
    prev->next = node->next->next; /* whether it's NULL or not
    doesn't matter */
    free (delete_node); /* free any malloc'd data first*/
    break;
    }
    }

    It will either become the end of the list or will simply point to the node
    after the delete_node.

    It helps to visualize this (though I've been out with the gang tonight and
    the vision is a little sketchy, but I believe it works). Draw the nodes on
    a piece of paper and think it through.
     
    R Smith, Apr 16, 2007
    #9
  10. Bill Pursell Guest

    On Apr 16, 3:52 am, R Smith <> wrote:
    > "" wrote the subject line and:


    > > The solution to this is to copy the data
    > > from the next node into this
    > > node and delete the next node!.


    >
    > This is really simple. If you start from
    > the beginning of the list:


    In the original statement of the question, you don't have
    access to the beginning of the list.
     
    Bill Pursell, Apr 16, 2007
    #10
  11. On 16 Apr, 08:24, "Bill Pursell" <> wrote:
    > On Apr 16, 3:52 am, R Smith <> wrote:
    >
    > > "" wrote the subject line and:
    > > > The solution to this is to copy the data
    > > > from the next node into this
    > > > node and delete the next node!.

    >
    > > This is really simple. If you start from
    > > the beginning of the list:

    >
    > In the original statement of the question, you don't have
    > access to the beginning of the list.


    Then make the list double-linked, unless this it the absolute most
    critical execution-path in the program there's no need to make it more
    complicated than that.

    --
    Erik Wikström
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Apr 16, 2007
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    931
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    609
    Method Man
    Sep 24, 2004
  3. sangram
    Replies:
    16
    Views:
    1,991
  4. Raj
    Replies:
    13
    Views:
    1,614
  5. Replies:
    10
    Views:
    744
    =?iso-8859-1?q?Erik_Wikstr=F6m?=
    Apr 16, 2007
Loading...

Share This Page