Question

C program prelab:

This lab is pretty simple to describe: expand your suite of linked-list functions to include an ability to

insert a given key into a list at a particular location; or in its correct sorted-order position; or to remove a

specified key from a list or the key at a specified location. We’ve gone through the logic – though by now

you should be able to work it out on your own – and we've discussed the kinds of situations that can be

problematic. For example, what should be done if the calling program asks to remove a key that isn’t in

the list? You could have a return value telling the user it wasn't deleted, or you could have it do nothing

if the key is not in the list. As long as you provide appropriate documentation for the user then either

choice is defensible.

In the case of delete/remove, should the function remove only the first occurrence of the specified key

or all occurrences? Or should we provide separate functions for those two cases? Again, it's up to you to

decide which is more useful/convenient for the user.

Answer 1

# PLEASE GIVE IT A THUMBS UP !

Below is the function that inserts a given element at a soecified position into the linkedlist.

The function takes 3 parameters as arguments the head of the linkedlist , the new element to be inserted and the position where to be inserted.

#steps:

1.) Traverse the linkedlist till position -1 th element.

2.) Assign a new node to the given element

3.)store the next of the current position element in temp variable.

4.)change the next of the current position variable to the node

5.) Assign the next of the node to the temp.

#SOURCE CODE

#include <bits/stdc++.h>

using namespace std;

  

// A linked list Node

struct Node {

    int data;

    struct Node* next;

};

  

// Size of linked list

int size = 0;

  

// function to create and return a Node

Node* getNode(int data)

{

    // allocating space

    Node* newNode = new Node();

  

    // inserting the required data

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}

  

// function to insert a Node at required postion

void insertPos(Node** current, int pos, int data)

{

    // This condition to check whether the

    // postion given is valid or not.

    if (pos < 1 || pos > size + 1)

        cout << "Invalid postion!" << endl;

    else {

  

        // Keep looping until the pos is zero

        while (pos--) {

  

            if (pos == 0) {

  

                // adding Node at required postion

                Node* temp = getNode(data);

  

                // Making the new Node to point to

                // the old Node at the same position

                temp->next = *current;

  

                // Changing the pointer of the Node previous

                // to the old Node to point to the new Node

                *current = temp;

            }

            else

              // Assign double pointer variable to point to the

              // pointer pointing to the address of next Node

              current = &(*current)->next;

        }

        size++;

    }

}

  

// This function prints contents

// of the linked list

void printList(struct Node* head)

{

    while (head != NULL) {

        cout << " " << head->data;

        head = head->next;

    }

    cout << endl;

}

  

// Driver Code

int main()

{

    // Creating the list 3->5->8->10

    Node* head = NULL;

    head = getNode(3);

    head->next = getNode(5);

    head->next->next = getNode(8);

    head->next->next->next = getNode(10);

  

    size = 4;

  

    cout << "Linked list before insertion: ";

    printList(head);

  

    int data = 12, pos = 3;

    insertPos(&head, pos, data);

    cout << "Linked list after insertion of 12 at position 3: ";

    printList(head);

  

    // front of the linked list

    data = 1, pos = 1;

    insertPos(&head, pos, data);

    cout << "Linked list after insertion of 1 at position 1: ";

    printList(head);

  

    // insetion at end of the linked list

    data = 15, pos = 7;

    insertPos(&head, pos, data);

    cout << "Linked list after insertion of 15 at position 7: ";

    printList(head);

  

    return 0;

}

b.) For deletion the steps are:

1.) Traverse and find the previous node of the node to be deleted.

2.)Modify the next of the previous node to the next of the node to be deleted.

3.)Free the deleted node.

#SOURCE CODE

#include <stdio.h> #include <stdlib.h>    // A linked list node struct Node {     int data;     struct Node *next; };    /* Given a reference (pointer to pointer) to the head of a list    and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) {     struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));     new_node->data = new_data;     new_node->next = (*head_ref);     (*head_ref)    = new_node; }    /* Given a reference (pointer to pointer) to the head of a list    and a key, deletes the first occurrence of key in linked list */ void deleteNode(struct Node **head_ref, int key) {     // Store head node     struct Node* temp = *head_ref, *prev;        // If head node itself holds the key to be deleted     if (temp != NULL && temp->data == key)     {         *head_ref = temp->next;   // Changed head         free(temp);               // free old head         return;     }        // Search for the key to be deleted, keep track of the     // previous node as we need to change 'prev->next'     while (temp != NULL && temp->data != key)     {         prev = temp;         temp = temp->next;     }        // If key was not present in linked list     if (temp == NULL) return;        // Unlink the node from linked list     prev->next = temp->next;        free(temp); // Free memory }    // This function prints contents of linked list starting from // the given node void printList(struct Node *node) {     while (node != NULL)     {         printf(" %d ", node->data);         node = node->next;     } }    /* Drier program to test above functions*/ int main() {     /* Start with the empty list */     struct Node* head = NULL;        push(&head, 7);     push(&head, 1);     push(&head, 3);     push(&head, 2);        puts("Created Linked List: ");     printList(head);     deleteNode(&head, 1);     puts("\nLinked List after Deletion of 1: ");     printList(head);     return 0; } Thankyou , if any query plz comment , I will resolve it asap.