tutorial on linked list - part 2

now coming to a bit more useful topics in linked lists. often, we require that our lists be sorted at all times. even the items we insert into the linked lists be places at the correct place. so let's look at the insert function.

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

now the possibilities are:

1. list is currently empty
2. the item (head->data) at first place is bigger than item to be inserted
3. the new item needs to placed "somewhere" in between
4. the new item needs to placed at the end.

now look at the following code:

node *temp;
temp->data=item;
temp->next=head;
head=temp;

if the head is NULL OR head->data is more than item, the above code works. otherwise, we go to the node (current), BEFORE which, the new node should be inserted. we also heep a track of the node before that (last) so that we can insert the new node (temp) between last and current.

node *current=head,*last;
while(current!=NULL && current->data< item)
{
        last=current;
        current=current->next;
}
node *temp;
temp->data=item;
last->next=temp;
temp->next=current;

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

deletion function - similar to the insertion function, cases are:

1. either list is empty (do nothing)
2. item to delete is at head (just shift head to the next node)
3. item to delete is in the middle or at the end. (link the item before the concerned item to the item next to the concerned item\)

if(head->data==item)
    head=head->next;
else
{
    node *current=head,*last;
    while(current!=NULL && current->data!=item)
    {
        last=current;
        current=current->next;
    }
    if(current!=NULL)
        last->next=current->next;
    //if we reach the end of list, the item is not found
}