Revolution

avail-list.c

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

#define AVAILLISTMAX 100

struct Node // Creating a Node
{
    int data;
    struct Node *next;
};

struct Node *head = NULL, *last = NULL;
struct Node *avail = NULL; // avalilist

void traverse(struct Node *node) // Function for traversing the list
{
    if (node == NULL)
    {
        printf("The List is Empty!\n");
        return;
    }

    printf("The list is : ");
    while (node != NULL)
    {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("[END]");
}

void insertBeg(int data) // Function for creating the list node
{
    struct Node *newNode = NULL;

    if (avail == NULL)
    { // If no node is avail-list
        printf("[FATAL] Out of available nodes\n");
        return;
    }

    newNode = avail; // delete from avail, insert in main
    avail = avail->next;

    newNode->data = data; // insert at beginning
    newNode->next = head;

    head = newNode;
    if (head->next == NULL)
        last = head;
}

void insertEnd(int data)
{
    struct Node *newNode = NULL;

    if (avail == NULL)
    {
        // If no node is avail-list
        printf("[FATAL] Out of available nodes\n");
        return;
    }
    newNode = avail; // delete from avail
    avail = avail->next;

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)
    {
        head = newNode;
        last = head;
    }
    else
    {
        last->next = newNode;
        last = last->next;
    }
}

void deleteBeg()
{
    struct Node *temp = NULL;

    if (head == NULL)
    {
        printf("List EMPTY!\n");
        return;
    }

    temp = head;

    head = head->next; // Delete from main list, insert in avail list
    if (head == NULL)
        last = NULL;

    temp->next = avail;
    avail = temp;
}

void deleteEnd()
{
    struct Node *temp = NULL, *secondLast = NULL;

    if (head == NULL)
    {
        printf("List EMPTY!\n");
        return;
    }

    if (head->next == NULL)
    {
        temp = head;
        head = NULL;
        last = NULL;
    }
    else
    {
        secondLast = head;

        while (secondLast->next != last)
            secondLast = secondLast->next;
        printf("%d second last %p\n", secondLast->data, secondLast);

        temp = last;
        secondLast->next = NULL;
        last = secondLast;
    }

    temp->next = avail;
    avail = temp;
}

void searchUnsorted(int data)
{
    struct Node *temp;

    for (temp = head; temp != NULL; temp = temp->next)
        if (temp->data == data)
        {
            printf("Data found!!!\n");
            return;
        }

    printf("Data Not Found!!\n");
    return;
}

void sortLinkedList()
{
    int swapped = 0, tempint;
    struct Node *lastptr = NULL, *temp = NULL;

    do
    {
        temp = head;
        swapped = 0;

        while (temp->next != lastptr)
        {
            if (temp->data > temp->next->data)
            {
                tempint = temp->data;
                temp->data = temp->next->data;
                temp->next->data = tempint;
                swapped = 1;
            }
            temp = temp->next;
        }

        lastptr = temp;
    } while (swapped);
}

struct Node *mid(struct Node *start, struct Node *last)
{
    if (start == NULL)
        return NULL;

    struct Node *single_step = start;
    struct Node *double_step = start->next;

    while (double_step != last)
    {
        double_step = double_step->next;
        if (double_step != last)
        {
            single_step = single_step->next;
            double_step = double_step->next;
        }
    }
    return single_step;
}

void binarySearch(int value) // Function for searching in a sorted list
{
    struct Node *start = head;
    struct Node *last = NULL;
    int loc = 0;

    do
    {
        struct Node *middle = mid(start, last);
        if (middle->data == value)
        {
            printf("[+] The number is present!\n");
            return;
        }

        else if (middle->data < value)
            start = middle->next;
        else
            last = middle;
    } while (last == NULL || last != start);

    printf("[-] The Number Not Found !\n");
}

void getValue(const char *msg, int *n)
{
    puts(msg);
    scanf("%d", n);
}

int main()
{
    int i, N, data, choice;
    struct Node *temp;

    avail = (struct Node *)malloc(sizeof(struct Node));
    temp = avail;
    for (i = 0; i < AVAILLISTMAX - 1; i++)
    {
        temp->next = (struct Node *)malloc(sizeof(struct Node));
        temp = temp->next;
    }

    do {
        printf("\n\nEnter your choice:                                                           \
                \n\t0] Display list            5] Delete Beginning        10] Search in Unsorted \
                \n\t1] Insert at beginning     6] Delete End              11] Sort Linked List   \
                \n\t2] Insert at End           7] Delete Before [WIP]     12] Search in Sorted   \
                \n\t3] Insert Before [WIP]     8] Delete After  [WIP]                            \
                \n\t4] Insert After  [WIP]     9] EXIT                                           \
                \nChoice> ");

        scanf("%d", &choice);

        switch (choice)
        {
        case 0:
            traverse(head);
            break;
        case 1:
            getValue("Element to Insert: ", &data);
            insertBeg(data);
            break;
        case 2:
            getValue("Element to Insert: ", &data);
            insertEnd(data);
            break;
        case 5:
            deleteBeg();
            break;
        case 6:
            deleteEnd();
            break;
        case 10:
            getValue("Element to Search: ", &data);
            searchUnsorted(data);
            break;
        case 11:
            sortLinkedList();
            printf("After Sorting:\n");
            traverse(head);
            break;
        case 12:
            sortLinkedList();
            getValue("Element to Search: ", &data);
            binarySearch(data);
            break;
        case 3:
        case 4:
        case 7:
        case 8:
            puts("Feature Not Implemented Yet");
            break;
        case 9:
            printf("Thank you!");
        }
    } while (choice != 9);

    return 0;
}