double linked list delete problem

Discussion in 'C Programming' started by PRadyut, Jun 8, 2005.

  1. PRadyut

    PRadyut Guest

    in this code the delete function does not delete the last node of the
    double linked list

    the code
    ----------------------------------------------------------------


    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    struct dnode
    {
    struct dnode *prev;
    int data;
    struct dnode *next;
    };
    void display(struct dnode *);
    void add(struct dnode **, int );
    void deletel(struct dnode **, int );
    int main()
    {
    struct dnode *p=NULL;
    add(&p, 2);
    add(&p, 3);
    add(&p, 4);
    add(&p, 5);
    add(&p, 7);
    add(&p, 8);
    add(&p, 9);
    add(&p, 1);
    add(&p, 10);
    add(&p, 9);
    display(p);
    deletel(&p, 9);
    deletel(&p, 9);
    display(p);
    getch();
    return 0;
    }
    void add(struct dnode **s, int num)
    {
    struct dnode *p, *r;
    p=*s;
    r=(struct dnode*)malloc(sizeof(struct dnode));
    r->data=num;
    if(*s==NULL)
    {
    r->next=NULL;
    r->prev=NULL;
    *s=r;
    (*s)->next=p;
    }
    else
    {
    while(p->next!=NULL)
    p=p->next;
    r->prev=p;
    r->next=NULL;
    p->next=r;
    }
    }
    void display(struct dnode *s)
    {
    while(s)
    {
    printf("%d\n", s->data);
    s=s->next;
    }
    printf("\n");
    }

    void deletel(struct dnode **s, int num)
    {
    struct dnode *p;
    p=*s;
    if(*s==NULL)
    printf("list is empty");
    else
    {
    while(p->next!=NULL)
    {
    if(p->data==num)
    {
    if(p==*s)
    {
    (*s)->prev=NULL;
    *s=p->next;
    free(p);
    return;
    }
    else
    {
    if(p->next==NULL)
    {
    p->prev->next=NULL;
    }
    else
    {
    p->prev->next=p->next;
    p->next->prev=p->prev;
    }
    free(p);
    }
    return;
    }
    p=p->next;
    }
    printf("element %d not found", num);
    }
    }

    -----------------------------------------------------------

    any help

    thanks
    Pradyut
    http://pradyut.tk
    http://groups.yahoo.com/group/d_dom/
    http://groups-beta.google.com/group/oop_programming
    India
    PRadyut, Jun 8, 2005
    #1
    1. Advertising

  2. PRadyut

    pete Guest

    PRadyut wrote:

    > void deletel(struct dnode **s, int num)
    > {
    > struct dnode *p;
    > p=*s;
    > if(*s==NULL)
    > printf("list is empty");
    > else
    > {
    > while(p->next!=NULL)
    > {
    > if(p->data==num)
    > {
    > if(p==*s)
    > {
    > (*s)->prev=NULL;
    > *s=p->next;
    > free(p);
    > return;
    > }
    > else
    > {
    > if(p->next==NULL)
    > {
    > p->prev->next=NULL;
    > }
    > else
    > {
    > p->prev->next=p->next;
    > p->next->prev=p->prev;
    > }
    > free(p);
    > }
    > return;
    > }
    > p=p->next;
    > }
    > printf("element %d not found", num);
    > }
    > }


    /* Use 4 spaces instead of tabs */

    void deletel(struct dnode **s, int num)
    {
    struct dnode *n;

    n = *s;
    if (n == NULL) {
    puts("list is empty");
    } else {
    if (n -> data == num) {
    *s = n -> next;
    free(n);
    if (*s != NULL) {
    (*s) -> prev = NULL;
    }
    } else {
    n = n -> next;
    while (n != NULL) {
    if (n -> data == num) {
    n -> prev -> next = n -> next;
    if (n -> next != NULL) {
    n -> next -> prev = n -> prev;
    }
    free(n);
    n = *s;
    break;
    } else {
    n = n -> next;
    }
    }
    if (n == NULL) {
    printf("element %d not found\n", num);
    }
    }
    }
    }

    --
    pete
    pete, Jun 9, 2005
    #2
    1. Advertising

  3. PRadyut

    Guest

    On 8 Jun 2005 06:59:44 -0700, "PRadyut" <> wrote:

    >in this code the delete function does not delete the last node of the
    >double linked list


    Did you mean the deletel function?

    >
    >the code
    >----------------------------------------------------------------
    >
    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >#include <conio.h>
    >struct dnode
    >{
    > struct dnode *prev;
    > int data;
    > struct dnode *next;
    >};
    >void display(struct dnode *);
    >void add(struct dnode **, int );
    >void deletel(struct dnode **, int );
    >int main()
    >{
    > struct dnode *p=NULL;
    > add(&p, 2);
    > add(&p, 3);
    > add(&p, 4);
    > add(&p, 5);
    > add(&p, 7);
    > add(&p, 8);
    > add(&p, 9);
    > add(&p, 1);
    > add(&p, 10);
    > add(&p, 9);
    > display(p);
    > deletel(&p, 9);
    > deletel(&p, 9);
    > display(p);
    > getch();
    > return 0;
    >}
    >void add(struct dnode **s, int num)
    >{
    > struct dnode *p, *r;
    > p=*s;
    > r=(struct dnode*)malloc(sizeof(struct dnode));


    You should not cast the return from malloc. It can rarely help and
    frequently hurt. But you should check for success before you
    dereference the pointer.

    > r->data=num;
    > if(*s==NULL)


    At this point, we know *s is NULL. That means p is NULL also.

    > {
    > r->next=NULL;
    > r->prev=NULL;
    > *s=r;


    At this point *s is the same as r. r->next is NULL so (*s)->next must
    be also. p is still NULL.

    > (*s)->next=p;


    Why are you setting (*s)->next to NULL when it already is?

    > }
    > else
    > {
    > while(p->next!=NULL)
    > p=p->next;
    > r->prev=p;
    > r->next=NULL;
    > p->next=r;
    > }
    >}
    >void display(struct dnode *s)
    >{
    > while(s)
    > {
    > printf("%d\n", s->data);
    > s=s->next;
    > }
    > printf("\n");
    >}
    >
    >void deletel(struct dnode **s, int num)
    >{
    > struct dnode *p;
    > p=*s;
    > if(*s==NULL)
    > printf("list is empty");
    > else
    > {
    > while(p->next!=NULL)


    Here is your problem. If num is the value in the last p->data, then
    the corresponding p->next must be NULL and you will not enter the
    following code. You need to rework this into the form
    while (p!=NULL)

    > {
    > if(p->data==num)
    > {
    > if(p==*s)


    In general, it is not a robust design to assume that *s points to the
    head of the list. A user might want to "delete the node with num if it
    occurs after the node I give you". But it is true in the code you
    posted.

    > {
    > (*s)->prev=NULL;
    > *s=p->next;
    > free(p);
    > return;
    > }
    > else
    > {
    > if(p->next==NULL)


    Based on your incorrect while, this cannot be. After you fix the
    while, this is code you need.

    > {
    > p->prev->next=NULL;
    > }
    > else
    > {
    > p->prev->next=p->next;
    > p->next->prev=p->prev;
    > }
    > free(p);
    > }
    > return;
    > }
    > p=p->next;
    > }
    > printf("element %d not found", num);
    > }
    >}
    , Jun 9, 2005
    #3
    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. Chris Ritchey
    Replies:
    7
    Views:
    475
    emerth
    Jul 10, 2003
  2. Sydex
    Replies:
    12
    Views:
    6,472
    Victor Bazarov
    Feb 17, 2005
  3. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  4. fool
    Replies:
    14
    Views:
    501
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    664
    John Carson
    Oct 2, 2006
Loading...

Share This Page