Question

IN C ONLY PLZ (read the instruction carefully plz)

You will implement the following functions:

List * initIntegerList( ) // Return empty list

int insertAtHead(int k, List*) // Insert k at head

int insertAtTail(int k, List*) // Insert k at tail

int removeHead(List *) // Remove head and return its key

int getListSize(List *) // Return number of elements in list

void printHead(List *) // Print key in head

void moveHeadToTail(List *) // Move key at head to tail

This doesn’t seem so bad – and it isn’t. However, there is a performance requirement that must be satisfied: all of the functions must take only a constant amount of time independent of the length of the list, i.e., they must all have O(1) complexity. Does this make things much more difficult? No, you just need to define a struct (List) that contains a pointer to the head of a linked list; a pointer to the tail of the list; and an integer containing the number of items/keys in the list. (Note that nodes in the linked list will not be List structs.) The information in the List struct is what will allow all operations to be satisfied in O(1) time.

Note that the above prototypes impose restrictions on how you handle potential error conditions, e.g., if the user tries to remove the head of an empty list, so you will need to document those situations for the user. For example, the function printHead will need documentation telling the user that nothing is printed if the list is empty. The two insert functions, however, have integer return values that can be used for error codes.

Answer 1

// C program to implement Linked list operations in O(1) time

#include <stdio.h>

#include <stdlib.h>

// structure to represent a node in the linked list

typedef struct Node

{

       int data;

       struct Node *next;

}Node;

// structure to represent the list

typedef struct List

{

       Node *head;

       Node *tail;

       int size;

}List;

// function prototype

List * initIntegerList( ); // Return empty list

int insertAtHead(int k, List*); // Insert k at head

int insertAtTail(int k, List*); // Insert k at tail

int removeHead(List *); // Remove head and return its key

int getListSize(List *); // Return number of elements in list

void printHead(List *); // Print key in head

void moveHeadToTail(List *); // Move key at head to tail

int main(void) {

       printf("\nInsert At Head :");

       List *list = initIntegerList();

       int result;

       if(list != NULL)

       {

             int i;

             for(i=1;i<=5;i++ )

             {

                    result = insertAtHead(i,list);

                    if(result == 0)

                    {

                           exit(1);

                    }

                    printHead(list);

             }

             printf("\nInsert At Tail :");

             for(i=6;i<=10;i++)

             {

                    result = insertAtTail(i,list);

                    if(result == 0)

                           exit(1);

             }

             printHead(list);

             printf("\nSize : %d",getListSize(list));

             printf("\nMove Head to Tail :");

             for(i=0;i<getListSize(list);i++)

             {

                    printHead(list);

                    moveHeadToTail(list);

             }

             printHead(list);

             printf("\nSize : %d",getListSize(list));

             printf("\nRemove Head :");

             while(getListSize(list) > 0)

             {

                    //printHead(list);

                    printf("\nRemoved : %d",removeHead(list));

             }

       }

       return EXIT_SUCCESS;

}

// function that creates and returns a new empty list, returns NULL if memory allocation failed

List * initIntegerList( ) // Return empty list

{

       // create a new List

       List *list = (List*)malloc(sizeof(List));

       // check if memory is allocated successfully

       if(list != NULL)

       {

             // initialize head and tail to NULL and set size to 0

             list->head = NULL;

             list->tail = NULL;

             list->size = 0;

       }

       return list; // return list

}

// function to insert the node at the head of the list

// returns 1 if insertion is successful else 0

int insertAtHead(int k, List *list) // Insert k at head

{

       Node *node = (Node*)malloc(sizeof(Node)); // create a new node to contain k

       // if memory allocation is successful

       if(node != NULL)

       {

             // insert the node at head

             node->data = k;

             node->next = list->head;

             list->head = node;

             if(list->tail == NULL)

                    list->tail = node;

             list->size++;

             return 1; // insertion successful

       }

       return 0; // insertion unsuccessful

}

// function to insert a node at the tail

// returns 1 if insertion is successful else 0

int insertAtTail(int k, List *list) // Insert k at tail

{

       // create a new node to contain k

       Node *node = (Node*)malloc(sizeof(Node));

       // if memory allocation is successful

       if(node != NULL)

       {

             // insert node at the tail

             node->data = k;

             node->next = NULL;

             if(list->tail !=NULL)

             {

                    list->tail->next = node;

             }else

                    list->head = node;

             list->tail = node;

             list->size++;

             return 1; // insertion successful

       }

       return 0; // insertion unsuccessful

}

// function to remove and return the value at the head of the list

// return the key value if deletion is successful else returns -999

int removeHead(List *list) // Remove head and return its key

{

       if(list->head == NULL) // empty list

       {

             printf("\nEmpty list");

             return -999;

       }

       else

       {

             // delete the node at the head

             int k = list->head->data;

             Node *node = list->head;

             list->head = list->head->next;

             if(list->head == NULL)

                    list->tail = NULL;

             list->size--;

             free(node);

             return k;

       }

}

// function to return the size of the list

int getListSize(List *list) // Return number of elements in list

{

       return list->size;

}

// function to print the value at the head of the list

void printHead(List *list) // Print key in head

{

       if(list->head == NULL) // empty list

             printf("\nEmpty list");

       else // non-empty list

             printf("\nHead : %d",list->head->data);

}

// function to move the node at head to the tail

void moveHeadToTail(List *list) // Move key at head to tail

{

       if(list->head == NULL) // empty list

             printf("\nEmpty list");

       else

       {

             if(list->head->next != NULL) // more than 1 node

             {

                    // move the head node to tail

                    Node *node = list->head;

                    list->head = list->head->next;

                    node->next = NULL;

                    list->tail->next = node;

                    list->tail = node;

             }else // 1 node so no movement

                    printf("\nList has only one element");

       }

}

//end of program

Output:

Insert At Head Head 1 Head 2 Head 3 Head 4 Head 5 Insert At Tail Head 5 Size 10 Move Head to Tail Head 5 Head 4 Head 3 Head 2 Head 1 Head 6 Head 7 Head 8 Head 9 Head 10 Head 5 Size 10 Remove Head Removed 5 Removed 4 Removed 3 Removed 2 Removed 1 Removed 6 Removed 7 Removed 8 Removed 9