deletion in link list

Discussion in 'C Programming' started by ratika, Dec 3, 2007.

  1. ratika

    ratika Guest

    can anyone tell me how to delete a certain node in a doubly circular
    link list
    ratika, Dec 3, 2007
    #1
    1. Advertising

  2. ratika

    Mark Bluemel Guest

    ratika wrote:
    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    Carefully...
    Mark Bluemel, Dec 3, 2007
    #2
    1. Advertising

  3. ratika

    Chris Dollin Guest

    ratika wrote:

    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    (a) Yes, someone can [1].

    (b) This is not a C question: comp.programming would be a better choice.

    (c) You don't have books or chums or unsuccessful web searches? You haven't
    tried it yourself /at all/? Trying first will help you understand the
    problem; if you ask /then/, trying helps you to describe the problem,
    us to understand it, and you to understand the answers.

    (d) To remove a node X from its circular list, make its predecessor's
    forward link point to X's successor, and vice-versa. Watch out for
    the degenerate case.

    (e) /Write test cases/.

    (f) Reorder as applicable.

    [1] Programmers [2] are notable for their literal [3] interpretation of
    questions.

    [2] OK, /some/ programmers [3].

    [3] And maybe it's rhetorical, not literal [4].

    [4] Or a cover for the control messages to the mind-control satellites [4].

    [4] There is no footnote 4.

    --
    Chris "someone" Dollin

    Hewlett-Packard Limited registered office: Cain Road, Bracknell,
    registered no: 690597 England Berks RG12 1HN
    Chris Dollin, Dec 3, 2007
    #3
  4. ratika

    ravi Guest

    On Dec 3, 4:36 pm, ratika <> wrote:
    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    Let ptr holds the address of the node to be deleted then

    (ptr->back)->next = ptr->next;
    (ptr->next)->back = ptr->back;
    free(ptr);

    don't forget to check the boundary conditions
    ravi, Dec 3, 2007
    #4
  5. ratika

    santosh Guest

    Chris Dollin wrote:

    <snip>

    > [1] Programmers [2] are notable for their literal [3] interpretation
    > [of
    > questions.
    >
    > [2] OK, /some/ programmers [3].
    >
    > [3] And maybe it's rhetorical, not literal [4].
    >
    > [4] Or a cover for the control messages to the mind-control satellites
    > [[4].
    >
    > [4] There is no footnote 4.


    Maybe you should use structured control flow instead of gotos?
    santosh, Dec 3, 2007
    #5
  6. ratika

    Chris Dollin Guest

    santosh wrote:

    > Chris Dollin wrote:
    >
    > <snip>
    >
    >> [1] Programmers [2] are notable for their literal [3] interpretation
    >> [of
    >> questions.
    >>
    >> [2] OK, /some/ programmers [3].
    >>
    >> [3] And maybe it's rhetorical, not literal [4].
    >>
    >> [4] Or a cover for the control messages to the mind-control satellites
    >> [[4].
    >>
    >> [4] There is no footnote 4.

    >
    > Maybe you should use structured control flow instead of gotos?


    I do.

    --
    Chris "they're procedures" Dollin

    Hewlett-Packard Limited registered office: Cain Road, Bracknell,
    registered no: 690597 England Berks RG12 1HN
    Chris Dollin, Dec 3, 2007
    #6
  7. ratika

    Eric Sosman Guest

    ratika wrote:
    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    <off-topic reason="better asked in comp.programming">

    Draw a picture of the list, showing the links as arrows.
    Then draw another picture of the list as it would be if the
    deleted node were simply not there at all. Study the two
    pictures to see which arrows have changed, and then write
    code to make those changes in the actual list.

    </off-topic>

    --
    Eric Sosman
    lid
    Eric Sosman, Dec 3, 2007
    #7
  8. On Dec 3, 7:36 pm, ratika <> wrote:
    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    read your book and understand the knowledge points yourself
    try it yourself first
    remember that practice makes perfect
    Thomas X. Iverson, Dec 3, 2007
    #8
  9. ratika

    ratika Guest

    On Dec 3, 7:21 pm, "Thomas X. Iverson" <>
    wrote:
    > On Dec 3, 7:36 pm, ratika <> wrote:
    >
    > > can anyone tell me how to delete a certain node in a doubly circular
    > > link list

    >
    > read your book and understand the knowledge points yourself
    > try it yourself first
    > remember that practice makes perfect


    i know the concept of the program .i had made the program too . but
    the problem is that it is running only two times not more than that
    ratika, Dec 4, 2007
    #9
  10. ratika

    ratika Guest

    On Dec 3, 4:36 pm, ratika <> wrote:
    > can anyone tell me how to delete a certain node in a doubly circular
    > link list


    //circular doubly link list
    #include<stdio.h>
    #include<conio.h>
    #include<alloc.h>
    struct node
    {
    struct node *pre;
    int data;
    struct node *next;
    };
    void addnode(struct node** , int);
    void display(struct node*);
    void delfirst(struct node*);
    void main()
    {
    int item,ch;
    struct node **t;
    clrscr();
    *t=NULL;
    do
    {
    printf("\nMenu:\n1.add node\n2.display\n3.delete first node\n4.exit
    \nenter the choice");
    scanf("%d",&ch);
    switch(ch)
    {
    case 1:
    printf("enter the value to be inserted");
    scanf("%d",&item);
    addnode(t,item);
    break;
    case 2:
    display(*t);
    break;
    case 4:
    break;
    case 3:
    delfirst(*t);
    break;
    default:
    printf("wrong choice try again");
    }
    }while(ch!=3);
    getch();
    }


    //functions starts
    void addnode(struct node **t,int val)
    {
    struct node *temp,*temp1;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->pre=NULL;
    temp->data=val;
    temp->next=NULL;
    if(*t==NULL)
    {
    *t=temp;
    temp->pre=*t;
    temp->next=*t;
    }
    else
    {
    *t=temp1;
    while(temp1->next!=*t)
    {
    temp1=temp1->next;
    }
    temp1->next->pre=temp;
    temp->next=temp1->next;
    temp->pre=temp1;
    temp1->next=temp;
    }
    }

    void display(struct node *t)
    {
    struct node *temp;
    if(t==NULL)
    {
    printf("link list empty");
    }
    else
    {
    temp=t;
    while(temp->next!=NULL)
    {
    printf("%d",temp->data);
    temp=temp->next;
    }
    }
    }
    void delfirst(struct node *st)
    {
    if(st==NULL)
    {
    printf("link list empty");
    }
    else
    {
    struct node *temp;
    temp=st;
    temp->pre->next=temp->next;
    st=temp->next;
    temp->next->pre=temp->pre;
    }
    }
    this is the program made by me please see and tell me the errors
    ratika, Dec 4, 2007
    #10
  11. ratika

    Mark Bluemel Guest

    ratika wrote:
    > On Dec 3, 4:36 pm, ratika <> wrote:
    >> can anyone tell me how to delete a certain node in a doubly circular
    >> link list


    > //circular doubly link list
    > #include<stdio.h>
    > #include<conio.h>


    Non-standard header

    > #include<alloc.h>


    Non-standard header

    [snip]

    > void main()
    > {
    > int item,ch;
    > struct node **t;


    It's not clear what "t" should be - I think it's probably the "head" of
    the list and should probably be simply "struct node *t". A more
    meaningful name would be good.

    > clrscr();


    Non-standard function.

    > *t=NULL;


    Fails here - t is not initialized, so you can't dereference it safely.

    > do
    > {
    > printf("\nMenu:\n1.add node\n2.display\n3.delete first node\n4.exit
    > \nenter the choice");
    > scanf("%d",&ch);


    scanf() is a poor choice for interactive input (and for much other
    input, IMHO)

    > switch(ch)
    > {
    > case 1:
    > printf("enter the value to be inserted");
    > scanf("%d",&item);
    > addnode(t,item);


    I think you want to pass "&t" not "t" here.

    > break;
    > case 2:
    > display(*t);


    If I'm right about t, then you should just pass t.

    > break;
    > case 4:
    > break;
    > case 3:
    > delfirst(*t);


    And here you probably need to pass "&t" again.

    > break;
    > default:
    > printf("wrong choice try again");
    > }
    > }while(ch!=3);


    Wrong exit check...

    > getch();


    Non-standard function

    > }
    >
    >
    > //functions starts
    > void addnode(struct node **t,int val)


    Where do you want to add your new nodes - are they ordered?

    > {
    > struct node *temp,*temp1;


    Hopeless names for your variables.

    > temp=(struct node*)malloc(sizeof(struct node));
    > temp->pre=NULL;
    > temp->data=val;
    > temp->next=NULL;
    > if(*t==NULL)
    > {
    > *t=temp;
    > temp->pre=*t;
    > temp->next=*t;
    > }
    > else
    > {
    > *t=temp1;


    What is this supposed to mean?

    > while(temp1->next!=*t)
    > {
    > temp1=temp1->next;
    > }
    > temp1->next->pre=temp;
    > temp->next=temp1->next;
    > temp->pre=temp1;
    > temp1->next=temp;
    > }
    > }
    >
    > void display(struct node *t)
    > {
    > struct node *temp;


    Stupid name and not needed.

    > if(t==NULL)
    > {
    > printf("link list empty");
    > }
    > else
    > {
    > temp=t;
    > while(temp->next!=NULL)


    This is a doubly-linked list, isn't it?
    This condition won't be encountered.

    > {
    > printf("%d",temp->data);
    > temp=temp->next;
    > }
    > }
    > }
    > void delfirst(struct node *st)
    > {
    > if(st==NULL)
    > {
    > printf("link list empty");
    > }
    > else
    > {
    > struct node *temp;
    > temp=st;
    > temp->pre->next=temp->next;
    > st=temp->next;
    > temp->next->pre=temp->pre;
    > }
    > }


    This doesn't update the list head that you track in your main routine,
    does it? Nor does it deal with removing the last element.

    Here's a version, with fairly minimal changes, that seems to work

    //circular doubly link list
    #include<stdio.h>
    #include<stdlib.h>

    struct node
    {
    struct node *pre;
    int data;
    struct node *next;
    };
    void addnode (struct node **, int);
    void display (struct node *);
    void delfirst (struct node **);
    int
    main ()
    {
    int item, ch;
    struct node *head;
    head = NULL;
    do
    {
    printf ("\nMenu:\n1.add node\n2.display\n3.delete first
    node\n4.exit\nenter the choice");
    scanf ("%d", &ch);
    switch (ch)
    {
    case 1:
    printf ("enter the value to be inserted");
    scanf ("%d", &item);
    addnode (&head, item);
    break;
    case 2:
    display (head);
    break;
    case 4:
    break;
    case 3:
    delfirst (&head);
    break;
    default:
    printf ("wrong choice try again");
    }
    }
    while (ch != 4);
    }


    //functions starts
    void
    addnode (struct node **head, int val)
    {
    struct node *newNode;
    newNode = (struct node *) malloc (sizeof *newNode);
    newNode->pre = NULL;
    newNode->data = val;
    newNode->next = NULL;
    if (*head == NULL)
    {
    *head = newNode;
    newNode->pre = *head;
    newNode->next = *head;
    }
    else
    {
    struct node *currentNode = *head;
    while (currentNode->next != *head)
    {
    currentNode = currentNode->next;
    }
    newNode->next = currentNode->next;
    newNode->pre = currentNode;
    currentNode->next->pre = newNode;
    currentNode->next = newNode;
    }
    }

    void
    display (struct node *head)
    {
    struct node *currentNode;
    if (head == NULL)
    {
    printf ("link list empty");
    }
    else
    {
    currentNode = head;
    do
    {
    printf ("%d %p %p %p\n", currentNode->data, currentNode,
    currentNode->pre, currentNode->next);
    currentNode = currentNode->next;
    } while (currentNode != head);
    }
    }
    void
    delfirst (struct node **head)
    {
    if (*head == NULL)
    {
    printf ("link list empty");
    }
    else if ((*head)->next == *head) { // last entry
    *head = NULL;
    }
    else
    {
    struct node *nodeToDelete = *head;
    nodeToDelete->pre->next = nodeToDelete->next;
    nodeToDelete->next->pre = nodeToDelete->pre;
    *head = nodeToDelete->next;
    }
    }
    Mark Bluemel, Dec 4, 2007
    #11
  12. ratika

    Mark Bluemel Guest

    Mark Bluemel wrote:

    Oh! and main returns int - I fixed it in my version but forgot to
    mention it. (Ideally I should have used "int main(void)")
    Mark Bluemel, Dec 4, 2007
    #12
  13. ratika

    ratika Guest

    On 4 Dec, 15:09, Mark Bluemel <> wrote:
    > ratika wrote:
    > > On Dec 3, 4:36 pm, ratika <> wrote:
    > >> can anyone tell me how to delete a certain node in a doubly circular
    > >> link list

    > > //circular doubly link list
    > > #include<stdio.h>
    > > #include<conio.h>

    >
    > Non-standard header
    >
    > > #include<alloc.h>

    >
    > Non-standard header
    >
    > [snip]
    >
    > > void main()
    > > {
    > > int item,ch;
    > > struct node **t;

    >
    > It's not clear what "t" should be - I think it's probably the "head" of
    > the list and should probably be simply "struct node *t". A more
    > meaningful name would be good.
    >
    > > clrscr();

    >
    > Non-standard function.
    >
    > > *t=NULL;

    >
    > Fails here - t is not initialized, so you can't dereference it safely.
    >
    > > do
    > > {
    > > printf("\nMenu:\n1.add node\n2.display\n3.delete first node\n4.exit
    > > \nenter the choice");
    > > scanf("%d",&ch);

    >
    > scanf() is a poor choice for interactive input (and for much other
    > input, IMHO)
    >
    > > switch(ch)
    > > {
    > > case 1:
    > > printf("enter the value to be inserted");
    > > scanf("%d",&item);
    > > addnode(t,item);

    >
    > I think you want to pass "&t" not "t" here.
    >
    > > break;
    > > case 2:
    > > display(*t);

    >
    > If I'm right about t, then you should just pass t.
    >
    > > break;
    > > case 4:
    > > break;
    > > case 3:
    > > delfirst(*t);

    >
    > And here you probably need to pass "&t" again.
    >
    > > break;
    > > default:
    > > printf("wrong choice try again");
    > > }
    > > }while(ch!=3);

    >
    > Wrong exit check...
    >
    > > getch();

    >
    > Non-standard function
    >
    > > }

    >
    > > //functions starts
    > > void addnode(struct node **t,int val)

    >
    > Where do you want to add your new nodes - are they ordered?
    >
    > > {
    > > struct node *temp,*temp1;

    >
    > Hopeless names for your variables.
    >
    > > temp=(struct node*)malloc(sizeof(struct node));
    > > temp->pre=NULL;
    > > temp->data=val;
    > > temp->next=NULL;
    > > if(*t==NULL)
    > > {
    > > *t=temp;
    > > temp->pre=*t;
    > > temp->next=*t;
    > > }
    > > else
    > > {
    > > *t=temp1;

    >
    > What is this supposed to mean?
    >
    > > while(temp1->next!=*t)
    > > {
    > > temp1=temp1->next;
    > > }
    > > temp1->next->pre=temp;
    > > temp->next=temp1->next;
    > > temp->pre=temp1;
    > > temp1->next=temp;
    > > }
    > > }

    >
    > > void display(struct node *t)
    > > {
    > > struct node *temp;

    >
    > Stupid name and not needed.
    >
    > > if(t==NULL)
    > > {
    > > printf("link list empty");
    > > }
    > > else
    > > {
    > > temp=t;
    > > while(temp->next!=NULL)

    >
    > This is a doubly-linked list, isn't it?
    > This condition won't be encountered.
    >
    >
    >
    >
    >
    > > {
    > > printf("%d",temp->data);
    > > temp=temp->next;
    > > }
    > > }
    > > }
    > > void delfirst(struct node *st)
    > > {
    > > if(st==NULL)
    > > {
    > > printf("link list empty");
    > > }
    > > else
    > > {
    > > struct node *temp;
    > > temp=st;
    > > temp->pre->next=temp->next;
    > > st=temp->next;
    > > temp->next->pre=temp->pre;
    > > }
    > > }

    >
    > This doesn't update the list head that you track in your main routine,
    > does it? Nor does it deal with removing the last element.
    >
    > Here's a version, with fairly minimal changes, that seems to work
    >
    > //circular doubly link list
    > #include<stdio.h>
    > #include<stdlib.h>
    >
    > struct node
    > {
    > struct node *pre;
    > int data;
    > struct node *next;};
    >
    > void addnode (struct node **, int);
    > void display (struct node *);
    > void delfirst (struct node **);
    > int
    > main ()
    > {
    > int item, ch;
    > struct node *head;
    > head = NULL;
    > do
    > {
    > printf ("\nMenu:\n1.add node\n2.display\n3.delete first
    > node\n4.exit\nenter the choice");
    > scanf ("%d", &ch);
    > switch (ch)
    > {
    > case 1:
    > printf ("enter the value to be inserted");
    > scanf ("%d", &item);
    > addnode (&head, item);
    > break;
    > case 2:
    > display (head);
    > break;
    > case 4:
    > break;
    > case 3:
    > delfirst (&head);
    > break;
    > default:
    > printf ("wrong choice try again");
    > }
    > }
    > while (ch != 4);
    >
    > }
    >
    > //functions starts
    > void
    > addnode (struct node **head, int val)
    > {
    > struct node *newNode;
    > newNode = (struct node *) malloc (sizeof *newNode);
    > newNode->pre = NULL;
    > newNode->data = val;
    > newNode->next = NULL;
    > if (*head == NULL)
    > {
    > *head = newNode;
    > newNode->pre = *head;
    > newNode->next = *head;
    > }
    > else
    > {
    > struct node *currentNode = *head;
    > while (currentNode->next != *head)
    > {
    > currentNode = currentNode->next;
    > }
    > newNode->next = currentNode->next;
    > newNode->pre = currentNode;
    > currentNode->next->pre = newNode;
    > currentNode->next = newNode;
    > }
    >
    > }
    >
    > void
    > display (struct node *head)
    > {
    > struct node *currentNode;
    > if (head == NULL)
    > {
    > printf ("link list empty");
    > }
    > else
    > {
    > currentNode = head;
    > do
    > {
    > printf ("%d %p %p %p\n", currentNode->data, currentNode,
    > currentNode->pre, currentNode->next);
    > currentNode = currentNode->next;
    > } while (currentNode != head);
    > }}
    >
    > void
    > delfirst (struct node **head)
    > {
    > if (*head == NULL)
    > {
    > printf ("link list empty");
    > }
    > else if ((*head)->next == *head) { // last entry
    > *head = NULL;
    > }
    > else
    > {
    > struct node *nodeToDelete = *head;
    > nodeToDelete->pre->next = nodeToDelete->next;
    > nodeToDelete->next->pre = nodeToDelete->pre;
    > *head = nodeToDelete->next;
    > }
    >
    >
    >
    > }- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -


    thankyou sir for correcting my mistakes..i would run and tell you the
    results which i get
    ratika, Dec 12, 2007
    #13
    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. =?Utf-8?B?SGFyYWxk?=

    Persistent cache contents after deletion

    =?Utf-8?B?SGFyYWxk?=, Feb 19, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    283
    =?Utf-8?B?SGFyYWxk?=
    Feb 19, 2004
  2. alanb

    FilePicker Deletion Access Denied

    alanb, Apr 26, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    368
    alanb
    Apr 26, 2004
  3. YouKnowIt
    Replies:
    0
    Views:
    380
    YouKnowIt
    May 12, 2004
  4. Kevin Spencer

    Re: Link Link Link DANGER WILL ROBINSON!!!

    Kevin Spencer, May 17, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    792
    Kevin Spencer
    May 17, 2005
  5. Replies:
    2
    Views:
    329
    Bart Van der Donck
    Dec 27, 2008
Loading...

Share This Page