Make a Linked List and Array list using these functions /* A recursive structure

Question

Make a Linked List and Array list using these functions

/* A recursive structure */
struct node {
int number; /* payload */
struct node *next;
};

/* You can use "node_t" instead of "struct node" */
typedef struct node node_t;

/* Make a single node with c as payload */
extern node_t *make_node(int c);

/* Make a list of intacters with a string input and size */
extern node_t *make_list(int numbers[], int size);

/* Print the list. See an example output in the test sheet. */
extern void print_list(node_t *head);

/* Return number of nodes */
extern int size(node_t *head);

/* Add a node with c as payload before the current head. Return the new head. */
extern node_t *prepend(node_t *head, int c);

/* Add a node at the end of list with payload c. */
extern node_t *append(node_t *head, int c);

/* Prints out the payload of a node in a single line */
extern void print_node(node_t n);

/* Return a pointer to the ith element (0-indexed) */
extern node_t *get_ith(node_t *head, int pos);

/* Make and insert a node after the ith node (0-indexed) */
extern node_t *insert_at(node_t *head, int c, int pos);

/* Make and insert a node after a node */
extern void insert_after(node_t *node, int c);

/* Remove a node at the ith position (0-indexed) and free the space of the node */
extern node_t *remove_ith(node_t *head, int i);

/* Free the space of the nodes and set the head to NULL. */
extern void delete_list(node_t **head);

Explanation / Answer

The Linked list operations are made with some predefined values i.e 1 to 5. you can modify the program as per your requirement.

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

struct test_struct
{
    int val;
    struct test_struct *next;
};

struct test_struct *head = NULL;
struct test_struct *curr = NULL;

struct test_struct* create_list(int val)
{
    printf(" creating list with headnode as [%d] ",val);
    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf(" Node creation failed ");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    head = curr = ptr;
    return ptr;
}

struct test_struct* add_to_list(int val, bool add_to_end)
{
    if(NULL == head)
    {
        return (create_list(val));
    }

    if(add_to_end)
        printf(" Adding node to end of list with value [%d] ",val);
    else
        printf(" Adding node to beginning of list with value [%d] ",val);

    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf(" Node creation failed ");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    if(add_to_end)
    {
        curr->next = ptr;
        curr = ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}

struct test_struct* search_in_list(int val, struct test_struct **prev)
{
    struct test_struct *ptr = head;
    struct test_struct *tmp = NULL;
    bool found = false;

    printf(" Searching the list for value [%d] ",val);

    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(true == found)
    {
        if(prev)
            *prev = tmp;
        return ptr;
    }
    else
    {
        return NULL;
    }
}

int delete_from_list(int val)
{
    struct test_struct *prev = NULL;
    struct test_struct *del = NULL;

    printf(" Deleting value [%d] from list ",val);

    del = search_in_list(val,&prev);
    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
            prev->next = del->next;

        if(del == curr)
        {
            curr = prev;
        }
        else if(del == head)
        {
            head = del->next;
        }
    }

    free(del);
    del = NULL;

    return 0;
}

void print_list(void)
{
    struct test_struct *ptr = head;

    printf(" -------Printing list Start------- ");
    while(ptr != NULL)
    {
        printf(" [%d] ",ptr->val);
        ptr = ptr->next;
    }
    printf(" -------Printing list End------- ");

    return;
}

int main(void)
{
    int i = 0, ret = 0;
    struct test_struct *ptr = NULL;

    print_list();

    for(i = 5; i<10; i++)
        add_to_list(i,true);

    print_list();

    for(i = 4; i>0; i--)
        add_to_list(i,false);

    print_list();

    for(i = 1; i<10; i += 4)
    {
        ptr = search_in_list(i, NULL);
        if(NULL == ptr)
        {
            printf(" Search [val = %d] failed, no such element found ",i);
        }
        else
        {
            printf(" Search passed [val = %d] ",ptr->val);
        }

        print_list();

        ret = delete_from_list(i);
        if(ret != 0)
        {
            printf(" delete [val = %d] failed, no such element found ",i);
        }
        else
        {
            printf(" delete [val = %d] passed ",i);
        }

        print_list();
    }

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.