How to remove any node in a singly linked list

Here's my code:

#include<stdio.h>
#include<stdlib.h>

struct node
{ 
    int x;
    struct node *next;       
};

struct node *addNode(struct node *head, int y)
{
       struct node *traverser;
       traverser = head;
       if(traverser!=NULL)
       {                 
             while(traverser->next!=NULL)
             traverser=traverser->next;

             traverser -> next = malloc(sizeof(struct node));
             traverser -> next -> x = y;
             traverser -> next -> next = NULL;
       }
       else
       {
             head= malloc(sizeof(struct node));
             head -> x=y;
             head -> next = NULL;
       }    
       return head;
 }

 void display(struct node *head)
 {   
     struct node *traverser;
     traverser = head;

     while(traverser!=NULL)
     {
          printf("%d\n",traverser->x);
          traverser=traverser->next; 
     }
 }

 struct node *InitializeList(void)
 {
       return NULL;
 }

int main()
{
    struct node *head;
    head = InitializeList();
    head = addNode(head,2);
    head = addNode(head,15);
    head = addNode(head,5);
    head = addNode(head,8);
    display(head);  

    free(head);
    getchar();
}

I need to remove a node in main like this

struct node *head;
head = InitializeList();
head = addNode(head,2);
head = addNode(head,15);
head = addNode(head,5);开发者_StackOverflow中文版
head = addNode(head,8);
display(head);  
removenode(5);
display(head);  
removenode(8); 
display(head);  
free(head);

That's my code for main() when it comes to delete specific node in my program.

But how can I do it? The removenode() is just function name what algorithm should I use? Or what or how to remove it?

---

Not quite a answer, just some general advice

For the purposes of figuring this kind of thing out, it is generally sufficient to solve exactly three cases

• The node to be removed is the head
• The node to be removed is the tail
• the node to be removed is interior to the list

---

The the big sources of trouble you will encounter are

• making sure that the "next" field in any preceding nodes get properly reset
• insuring that the caller gets or retains a valid pointer to the new head.

Note that there is a recursive implementation (think n.next = remove(n.next,val)) that makes these two problems one and the same, and that you can convert it mostly to a loop to prevent stack overflows on very long lists.

---

A sub-problem that may crop up is that of finding the node to be removed in the list. Can you makae you life easier by separating there part about finding the target node from a remove(node* head, node* target)?

---

The algorithm prototype needs to be:

struct node * removenode(struct node *head, int y);

Since if you're removing the first item, the original "head" pointer will no longer be valid.

The algorithm is simply to step through the list, remembering the previous item (and the head), and looking for the data. When found, set previous item's next pointer to be the current item's next.

---

At a high level, to remove any node, what you need to do is:

1) Point to the item that is pointing to the node you want to delete.

2) Set the reference to the item you want to delete to the item you want to delete's next item.

3) Delete the item you want to delete.

That way, you chain is maintained and you've freed that element from memory.

Like so:

Head -> Item1 -> Item2 -> Item3 -> NULL

If you want to delete Item2, you go like this:

Head -> Item1 -> Item2 -> Item3 -> NULL
          ^       ^   (Grab pointers to these items)

Set Item1's next to Item2's next, then delete Item2.

           /--------------\
Head -> Item1    Item2 -> Item3 -> NULL
          ^       ^ (Delete 2)

EDIT: Deleting Item or Item3:

Head -> Item1 -> Item2 -> Item3 -> NULL
 ^       ^   (Grab pointers to these items)

Repoint head to Item2, then delete Item1:

   /--------------\
Head    Item1 -> Item2 -> Item3 -> NULL
 ^       ^ (Delete 1)

OR

Head -> Item1 -> Item2 -> Item3 -> NULL
                    ^       ^   (Grab pointers to these items)

Repoint head to Item2, then delete Item1:

                    /--------------\
Head -> Item1 -> Item2   Item3 -> NULL
                   ^       ^ (Delete 3)

---

See if this works out for you or not, perhaps was stored in my PC somewhere for a situation like this:

void RemoveNode(struct node*x)
{
    struct node *temp=x,*tempo=NULL;
    int i=0,n;
    printf("\nWould you like to delete a node?\nPress 1 for Yes 2 for No: ");
    scanf("%d",&i);
    if(i==1)
    {
        printf("Enter nth node to be deleted");
        scanf("%d",&n);
        i=0;
        if(n==1)
        {
        x=temp->next;
        free(temp);
        }
        while(i<n-2)
        {
        temp=temp->next;
        i++;
        }
        if(temp->next->next==NULL)
        {
        tempo=temp->next;
        temp->next=NULL;
        free(tempo);
        }
        else
        {
        tempo=temp->next;
        temp->next=temp->next->next;
        free(tempo);
        }
    }
    else
    printf("\n No Changes Made\nExiting....");
}

It always the Head that counts.