l2

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

typedef struct node
{
    int key;
    struct node *next;
} NodeT;

NodeT *search(NodeT *head, int givenKey)
{
    //TODO: search the given key and return the first node containing it or NULL
    NodeT *p;
    p=head;
    while(p)
    {
        if(p->key==givenKey)
            return p;
        p=p->next;
    }
    return NULL;
}

void print_list(NodeT *head)
{
    //TODO: print list keys
    NodeT *p;
    p=head;
    while(p!=NULL)
    {
        printf("%d ",p->key);
        p=p->next;
    }
    printf("\n");
}

void insert_first(NodeT **head, NodeT **tail, int givenKey)
{
    //TODO: insert the given key in the first position of the list given by head and tail;
    NodeT *p=(NodeT*)malloc(sizeof(NodeT));
    p->key=givenKey;
    p->next=NULL;
    if(*head==NULL)
    {
        p->next=NULL;
        *head=p;
        *tail=p;
    }
    else
    {
        p->next=*head;
        *head=p;
    }
}

void insert_last(NodeT **head, NodeT **tail, int givenKey)
{
    //TODO: insert the given key in the last position of the list given by head and tail;
    NodeT *p=(NodeT*)malloc(sizeof(NodeT));
    p->key=givenKey;
    p->next=NULL;
    if(*head==NULL)
    {
        *head=p;
        *tail=p;
    }
    else
    {
        (*tail)->next=p;
        *tail=p;
    }
}

void insert_after_key(NodeT** head, NodeT** tail, int afterKey, int givenKey)
{
    //TODO: insert the given key after afterKey, in list given by head and tail;
    NodeT*q;
    q=*head;
    NodeT *p=(NodeT*)malloc(sizeof(NodeT));
    p->key=givenKey;
    p->next=NULL;
    if(q==NULL)
    {
        insert_first(head,tail,givenKey);
        return;
    }
    while(q!=NULL)
    {
        if(q->key==afterKey)
        {
            p->next=q->next;
            q->next=p;
            if(q==*tail)
                *tail=p;
            break;
        }
        q=q->next;
    }

}

void insert_before_key(NodeT** head, NodeT** tail, int beforeKey, int givenKey)
{
    //TODO: insert the given key after afterKey, in list given by head and tail;
    NodeT *p=(NodeT*)malloc(sizeof(NodeT));
    p->key=givenKey;
    p->next=NULL;

    NodeT*crt,*before;
    crt=*head;
    before=NULL;

    while(crt!=NULL)
    {
        if(crt->key==beforeKey)
        {
            before->next=p;
            p->next=crt;
            break;
        }
        else
        {
            before=crt;
            crt=crt->next;
        }
    }
}

void delete_first(NodeT** head, NodeT** tail)
{
    //TODO: delete first list element
    if(*head==NULL)
        return;
    else{
        NodeT *p=*head;
        *head=(*head)->next;
        //free(p);
    }
}

void delete_last(NodeT** head, NodeT** tail)
{
    //TODO: delete last list element
    NodeT*p=*head;
    NodeT*prev=NULL;

    if(*head==NULL)
        return;

    while(p!=*tail)
    {
        prev=p;
        p=p->next;
    }
    if(p==*head)
    {
        *head=NULL;
        *tail=NULL;
    }
    prev->next=NULL;
    *tail=prev;
}

void delete_key(NodeT** first, NodeT** last, int givenKey)
{
    //TODO: delete element having given key
    NodeT *crt, *before;
    crt=*first;
    before=NULL;
    if(first==NULL)
        return;
    while(crt!=NULL)
    {
        if(crt->key==givenKey)
        {
            if(crt==*first)
                delete_first(first, last);
            else
            {
                if(crt==*last)
                    delete_last(first,last);
                else
                {
                    before->next=crt->next;
                }
            }
        }
        before=crt;
        crt=crt->next;
    }
}

int main()
{
    NodeT *first = NULL;
    NodeT *last  = NULL;

    //perform several insertions
    insert_first(&first, &last, 4);
    insert_first(&first, &last, 1);
    insert_last(&first, &last, 3);

    insert_before_key(&first, &last, 4, 5);

    //search for two distinct keys...
    int toSearch = 2;
    NodeT *foundNode = search(first, toSearch);
    if (foundNode == NULL)
    {
        printf("Node %d not found!\n", toSearch);
    }
    else
    {
        printf("%d found!\n", foundNode->key);
    }

    toSearch = 3;
    foundNode = search(first, toSearch);
    if (foundNode == NULL)
    {
        printf("Node %d not found!\n", toSearch);
    }
    else
    {
        printf("%d found!\n", foundNode->key);
    }

    //perform some insertions
    insert_after_key(&first, &last, 4, 22);
    insert_after_key(&first, &last, 3, 25);

    //print list contents
    print_list(first);

    //perform some deletions
    delete_first(&first,&last);
    delete_last(&first, &last);
    delete_key(&first, &last, 3);
    //delete_key(&first, &last, 8);

    //print list contents
    print_list(first);


    //TODO: place here code to delete all list
    /*....*/

    //print list contents
    print_list(first);

    return 0;
}