Singly and Doubly Link List C Program

Link List Program

Singly Linked List


/*
* File     : SLL.C
* Author   : Piyush Patel
* Purpose  : Singly Linked List Data Structure Using C Language
* Copyright: Shree Matrumandir College
*/
#include <stdio.h>
#include <stdlib.h>

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

typedef void (*callback)(node* data);


/*
    create a new node
    initialize the data and next field

    return the newly created node
*/
node* create(int data,node* next)
{
    node* new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        printf("Error creating a new node.\n");
        exit(0);
    }
    new_node->data = data;
    new_node->next = next;

    return new_node;
}


//add a new node at the beginning of the list
node* prepend(node* head,int data)
{
    node* new_node = create(data,head);
    head = new_node;
    return head;
}

//add a new node at the end of the list
node* append(node* head, int data)
{
node *new_node, *cursor = head;

if(head == NULL)
return NULL;
/* go to the last node */
while(cursor->next != NULL)
cursor = cursor->next;

/* create a new node */
new_node =  create(data,NULL);
cursor->next = new_node;

    return head;
}

/*
    insert a new node after the prev node
*/
node* insert_after(node *head, int data, node* prev)
{
node *cursor = head;
if(head == NULL || prev == NULL)
return NULL;
/* find the prev node, starting from the first node*/
while(cursor != prev)
        cursor = cursor->next;

    if(cursor != NULL)
    {
        node* new_node = create(data,cursor->next);
        cursor->next = new_node;
        return head;
    }
    else
    {
return NULL;
}
}

/*
insert a new node before the nxt node
*/
node* insert_before(node *head, int data, node* nxt)
{
node *cursor;
if(nxt == NULL || head == NULL)
return NULL;

if(head == nxt)
{
head = prepend(head,data);
return head;
}

/* find the prev node, starting from the first node*/
cursor = head;
while(cursor != NULL)
{
if(cursor->next == nxt)
            break;
        cursor = cursor->next;
    }

    if(cursor != NULL)
    {
        node* new_node = create(data,cursor->next);
        cursor->next = new_node;
        return head;
    }
    else
    {
        return NULL;
    }
}

/*
    traverse the linked list
*/
void traverse(node* head,callback f)
{
    node* cursor = head;
    while(cursor != NULL)
    {
        f(cursor);
        cursor = cursor->next;
    }
}
/*
    remove node from the front of list
*/
node* remove_front(node* head)
{
node *front = head;
if(head == NULL)
return NULL;
head = head->next;
    front->next = NULL;
    /* is this the last node in the list */
    if(front == head)
        head = NULL;
    free(front);
    return head;
}

/*
    remove node from the back of the list
*/
node* remove_back(node* head)
{
node *cursor = head;
node *back = NULL;
if(head == NULL)
return NULL;

while(cursor->next != NULL)
    {
        back = cursor;
        cursor = cursor->next;
    }

    if(back != NULL)
        back->next = NULL;

    /* if this is the last node in the list*/
    if(cursor == head)
        head = NULL;

    free(cursor);

return head;
}

/*
remove a node from the list
*/
node* remove_any(node* head,node* nd)
{
node* cursor;
if(nd == NULL)
return NULL;
/* if the node is the first node */
if(nd == head)
return remove_front(head);

/* if the node is the last node */
if(nd->next == NULL)
return remove_back(head);

/* if the node is in the middle */
cursor = head;
while(cursor != NULL)
    {
        if(cursor->next == nd)
            break;
        cursor = cursor->next;
    }

    if(cursor != NULL)
    {
        node* tmp = cursor->next;
        cursor->next = tmp->next;
        tmp->next = NULL;
        free(tmp);
    }
    return head;

}
/*
    display a node
*/
void display(node* n)
{
    if(n != NULL)
        printf("%d ", n->data);
}

/*
    Search for a specific node with input data

    return the first matched node that stores the input data,
    otherwise return NULL
*/
node* search(node* head,int data)
{

    node *cursor = head;
    while(cursor!=NULL)
    {
        if(cursor->data == data)
            return cursor;
        cursor = cursor->next;
    }
    return NULL;
}

/*
    remove all element of the list
*/
void dispose(node *head)
{
    node *cursor, *tmp;

    if(head != NULL)
    {
        cursor = head->next;
        head->next = NULL;
        while(cursor != NULL)
        {
            tmp = cursor->next;
            free(cursor);
            cursor = tmp;
        }
    }
}
/*
    return the number of elements in the list
*/
int count(node *head)
{
    node *cursor = head;
    int c = 0;
    while(cursor != NULL)
    {
        c++;
        cursor = cursor->next;
    }
    return c;
}
/*
    sort the linked list using insertion sort
*/
node* insertion_sort(node* head)
{
    node *x, *y, *e;

    x = head;
    head = NULL;

    while(x != NULL)
    {
        e = x;
        x = x->next;
        if (head != NULL)
        {
            if(e->data > head->data)
            {
                y = head;
                while ((y->next != NULL) && (e->data> y->next->data))
                {
                    y = y->next;
                }
                e->next = y->next;
                y->next = e;
            }
            else
            {
                e->next = head;
                head = e ;
            }
        }
        else
        {
            e->next = NULL;
            head = e ;
        }
    }
    return head;
}

/*
    reverse the linked list
*/
node* reverse(node* head)
{
    node* prev    = NULL;
    node* current = head;
    node* next;
    while (current != NULL)
    {
        next  = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
    return head;
}
/*
    display the menu
*/
void menu()
{
    printf("--- C Linked List Demonstration --- \n\n");
    printf("0.menu\n");
    printf("1.prepend an element\n");
    printf("2.append an element\n");
    printf("3.search for an element\n");
    printf("4.insert after an element\n");
    printf("5.insert before an element\n");
    printf("6.remove front node\n");
    printf("7.remove back node\n");
    printf("8.remove any node\n");
    printf("9.sort the list\n");
    printf("10.Reverse the linked list\n");
    printf("-1.quit\n");

}


int main()
{
    int command = 0;
    int data;

    node* head = NULL;
    node* tmp = NULL;
    callback disp = display;


    menu();
    while(1)
    {
        printf("\nEnter a command(0-10,-1 to quit):");
        scanf("%d",&command);

        if(command == -1)
            break;
        switch(command)
        {
        case 0:
            menu();
            break;
        case 1:
            printf("Please enter a number to prepend:");
            scanf("%d",&data);
            head = prepend(head,data);
            traverse(head,disp);
            break;
        case 2:
            printf("Please enter a number to append:");
            scanf("%d",&data);
            head = append(head,data);
            traverse(head,disp);
            break;
        case 3:
            printf("Please enter a number to search:");
            scanf("%d",&data);
            tmp = search(head,data);
            if(tmp != NULL)
            {
                printf("Element with value %d found.",data);
            }
            else
            {
                printf("Element with value %d not found.",data);
            }
            break;
        case 4:
            printf("Enter the element value where you want to insert after:");
            scanf("%d",&data);
            tmp = search(head,data);
            if(tmp != NULL)
            {
                printf("Enter the element value to insert after:");
                scanf("%d",&data);
                head = insert_after(head,data,tmp);
                if(head != NULL)
                    traverse(head,disp);
            }
            else
            {
                printf("Element with value %d not found.",data);
            }
            break;
        case 5:
            printf("Enter the element value where you want to insert before:");
            scanf("%d",&data);
            tmp = search(head,data);
            if(tmp != NULL)
            {
                printf("Enter the element value to insert before:");
                scanf("%d",&data);
                head = insert_before(head,data,tmp);

                if(head != NULL)
                    traverse(head,disp);
            }
            else
            {
                printf("Element with value %d not found.",data);
            }
            break;
        case 6:
            head = remove_front(head);
            if(head != NULL)
                traverse(head,disp);
            break;
        case 7:
            head = remove_back(head);
            if(head != NULL)
                traverse(head,disp);
            break;
        case 8:
            printf("Enter the element value to remove:");
            scanf("%d",&data);
            tmp = search(head,data);
            if(tmp != NULL)
            {
                remove_any(head,tmp);
                if(head != NULL)
                    traverse(head,disp);
            }
            else
            {
                printf("Element with value %d not found.",data);
            }
            break;
        case 9:
            head = insertion_sort(head);
            if(head != NULL)
                traverse(head,disp);
            break;
        case 10:
            head = reverse(head);
            if(head != NULL)
                traverse(head,disp);
            break;
        }

    }
    dispose(head);
    return 0;
}

Doubly Linked List


/*
 * C Program to Implement a Doubly Linked List 
 * Provide Insertion, Deletion, Display, Update, Sort & Search Operations
 */
#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    struct node *prev;
    int n;
    struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
 
void insert1();
void insert2();
void insert3();
void traversebeg();
void traverseend(int);
void sort();
void search();
void update();
void delete();
 
int count = 0;

void main()
{
int ch;
clrscr();
h = NULL;
temp = temp1 = NULL;

while (1)
{
printf("\n DOUBLY LINK LIST MENU");
printf("\n =====================");
printf("\n 1 - Insert at beginning");
printf("\n 2 - Insert at end");
printf("\n 3 - Insert at position i");
printf("\n 4 - Delete at i");
printf("\n 5 - Display from beginning");
printf("\n 6 - Display from end");
printf("\n 7 - Search for element");
printf("\n 8 - Sort the list");
printf("\n 9 - Update an element");
printf("\n 10 - Exit");
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1: insert1(); break;
case 2: insert2(); break;
case 3: insert3(); break;
case 4: delete(); break;
case 5: traversebeg(); break;
case 6:
temp2 = h;
if (temp2 == NULL)
printf("\n Error : List empty to display ");
else
{
printf("\n Reverse order of linked list is : ");
traverseend(temp2->n);
}
break;
case 7: search(); break;
case 8: sort(); break;
case 9: update(); break;
case 10: exit(0);
default:
printf("\n Wrong choice menu");
}
}
}

/* TO create an empty node */
void create()
{
int data;
 
    temp =(struct node *)malloc(1*sizeof(struct node));
    temp->prev = NULL;
    temp->next = NULL;
    printf("\n Enter value to node : ");
    scanf("%d", &data);
    temp->n = data;
    count++;
}
 
/*  TO insert at beginning */
void insert1()
{
    if (h == NULL)
    {
        create();
        h = temp;
        temp1 = h;
    }
    else
    {
        create();
        temp->next = h;
        h->prev = temp;
        h = temp;
    }
}
 
/* To insert at end */
void insert2()
{
    if (h == NULL)
    {
        create();
        h = temp;
        temp1 = h;
    }
    else
    {
        create();
        temp1->next = temp;
        temp->prev = temp1;
        temp1 = temp;
    }
}
 
/* To insert at any position */
void insert3()
{
    int pos, i = 2;
 
    printf("\n Enter position to be inserted : ");
    scanf("%d", &pos);
    temp2 = h;
 
    if ((pos < 1) || (pos >= count + 1))
    {
        printf("\n Position out of range to insert");
        return;
    }
    if ((h == NULL) && (pos != 1))
    {
        printf("\n Empty list cannot insert other than 1st position");
        return;
    }
    if ((h == NULL) && (pos == 1))
    {
        create();
        h = temp;
        temp1 = h;
        return;
    }
    else
    {
        while (i < pos)
        {
            temp2 = temp2->next;
            i++;
        }
        create();
        temp->prev = temp2;
        temp->next = temp2->next;
        temp2->next->prev = temp;
        temp2->next = temp;
    }
}
 
/* To delete an element */
void delete()
{
    int i = 1, pos;
 
    printf("\n Enter position to be deleted : ");
    scanf("%d", &pos);
    temp2 = h;
 
    if ((pos < 1) || (pos >= count + 1))
    {
        printf("\n Error : Position out of range to delete");
        return;
    }
    if (h == NULL)
    {
        printf("\n Error : Empty list no elements to delete");
        return;
    }
    else
    {
        while (i < pos)
        {
            temp2 = temp2->next;
            i++;
        }
        if (i == 1)
        {
            if (temp2->next == NULL)
            {
                printf("Node deleted from list");
                free(temp2);
                temp2 = h = NULL;
                return;
            }
        }
        if (temp2->next == NULL)
        {
            temp2->prev->next = NULL;
            free(temp2);
            printf("Node deleted from list");
            return;
        }
        temp2->next->prev = temp2->prev;
        if (i != 1)
            temp2->prev->next = temp2->next;    /* Might not need this statement if i == 1 check */
        if (i == 1)
            h = temp2->next;
        printf("\n Node deleted");
        free(temp2);
    }
    count--;
}
 
/* Traverse from beginning */
void traversebeg()
{
    temp2 = h;
 
    if (temp2 == NULL)
    {
        printf("List empty to display \n");
        return;
    }
    printf("\n Linked list elements from begining : ");
 
    while (temp2->next != NULL)
    {
        printf(" %d ", temp2->n);
        temp2 = temp2->next;
    }
    printf(" %d ", temp2->n);
}
 
/* To traverse from end recursively */
void traverseend(int i)
{
    if (temp2 != NULL)
    {
        i = temp2->n;
        temp2 = temp2->next;
        traverseend(i);
        printf(" %d ", i);
    }
}
 
/* To search for an element in the list */
void search()
{
    int data, count = 0;
    temp2 = h;
 
    if (temp2 == NULL)
    {
        printf("\n Error : List empty to search for data");
        return;
    }
    printf("\n Enter value to search : ");
    scanf("%d", &data);
    while (temp2 != NULL)
    {
        if (temp2->n == data)
        {
            printf("\n Data found in %d position",count + 1);
            return;
        }
        else
             temp2 = temp2->next;
            count++;
    }
    printf("\n Error : %d not found in list", data);
}
 
/* To update a node value in the list */
void update()
{
    int data, data1;
 
    printf("\n Enter node data to be updated : ");
    scanf("%d", &data);
    printf("\n Enter new data : ");
    scanf("%d", &data1);
    temp2 = h;
    if (temp2 == NULL)
    {
        printf("\n Error : List empty no node to update");
        return;
    }
    while (temp2 != NULL)
    {
        if (temp2->n == data)
        {
 
            temp2->n = data1;
            traversebeg();
            return;
        }
        else
            temp2 = temp2->next;
    }
 
    printf("\n Error : %d not found in list to update", data);
}
 
/* To sort the linked list */
void sort()
{
    int i, j, x;
 
    temp2 = h;
    temp4 = h;
 
    if (temp2 == NULL)
    {
        printf("\n List empty to sort");
        return;
    }
 
    for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
    {
        for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
        {
            if (temp2->n > temp4->n)
            {
                x = temp2->n;
                temp2->n = temp4->n;
                temp4->n = x;
            }
        }
    }
    traversebeg();
}

Comments

Post a Comment

Popular posts from this blog

પટેલ સમાજનો ઈતિહાસ જાણો : કોણ અને ક્યાંથી આવ્યા હતા પાટીદારો

PATIDAR The  Patidar  are a  caste  found in the state of  Gujarat , India. They were formally recognized as a separate identity in the 1931 census of India, having previously been classified as  Kanbi . They are among the most studied of Indian castes and the process leading to their recognition is a paradigmatic example of the  invention of tradition  by social groups in India. પટેલ અથવા પાટીદાર અથવા કણબી એ ભારત દેશનાં પશ્ચિમ ભાગમાં આવેલા ગુજરાત રાજ્યની એક મુખ્ય જ્ઞાતિ છે. પટેલોમાં લેઉવા પટેલ અને કડવા પટેલ એમ બે પેટા જ્ઞાતિ છે. ઇતિહાસ તેઓ કુર્મઋષિનાં વંશજો હોવાનુ મનાય છે તેથી તેઓ શરૂઆતમાં કુર્મી તરીકે જ ઓળખાતા હતાં. ઇતિહાસકારોનાં મત અનુસાર પટેલો મધ્ય એશિયા માં આસુ નદી પાસે પામીર નામનાં ઉચ્ચ પ્રદેશમાં વસતા હતાં. ત્યાંથી એક સમુહે અફઘાનિસ્તાન માં થઈને હિન્દુકુશ પર્વતમાળા ઓળંગી ખૈબરઘાટનાં માર્ગે પંજાબ માં દાખલ થઈને વસવાટ કર્યો હતો તેમ કહેવાય છે. ભારત દેશમાં પંજાબના સપ્તસિંઘુ પ્રદેશ ‘લેયા’ પ્રદેશમાંથી આવેલા કૂર્મિ ક્ષત્રિયો લેઉઆ કહેવાય...
Read more

Python HTML Generator using Yattag Part 1

Python HTML Generator Download and install yattag pip install yattag You can download the archive here: https://pypi.python.org/pypi/yattag                python setup.py install      or:         python3 setup.py install Yattag is a Python library for generating HTML or XML in a pythonic way. With Yattag, ·         you don't have to worry about closing HTML tags ·         your HTML templates are Python code. Not a weird template language. Just Python. ·         you can easily render HTML forms, with defaults values and error messages. It's actually easier and more readable to generate dynamic HTML with Yattag than to write static HTML. 1. Tags and text from yattag import Doc ...
Read more

Java Event Delegation Model, Listener and Adapter Classes

Image
Java Event Delegation Model The Delegation Event model is one of the many techniques used to handle events in GUI (Graphical User Interface) programming languages. GUI represents a system where an user visually/graphically interacts with the system. Other interactive systems are text based or called CUI (Character User Interface). CUI interacts with the system by typing out commands in the console. GUI programming is inherently event driven; that means, whenever an user initiates an activity such as a mouse move that changes the co-ordinates of the mouse pointer in the screen, or clicks a button, scrolls a page, and so forth, each is deemed as an event that the GUI event handler maps the activity to a piece of code that explains what response the application should provide to the user. Any program that uses GUI (graphical user interface) such as Java application written for windows, is event driven. Event describes the change in state of any object.  For Example:  Pre...
Read more