Question

C++ - Checks the relevance of a data structure in terms of following the interface specification for an ADT that represents a linear data structure:

Depending on the ADT of linear data structure, you must create the operations CRUD (Create, Read (search), Update, Delete) elements in the data structure. Some operations do not apply for certain data structures

Create:

Description: Insert an element in the data structure (create) according to the access policy of the structure

Input:Data structure and element to insert
Output: Valid data structure showing the insertion of the element
Precondition: A valid structure
Postcondition: Modified structure

Read:

Description: Read (search, obtain, etc.) an element within the data structure (read) according to the access policy of the structure
Input: The data structure and additional information about the item to retrieve (depending on the data structure)
Output: Element meeting the input or error criteria (there is no element with those characteristics)
Precondition: Valid data structure
Postcondition: Nothing

Update:

Description
Update an element within the data structure (update) according to the specific data structure

Input: Data structure, element to update, values ​​to modify
Output: Data structure duly updated
Precondition: A valid data structure
Postcondition: Data structure duly updated

Delete:

Description
Delete (remove) an element within the data structure (del) according to the specific data structure

Input: A data structure and criteria that determine the element to delete
Output: Updated data structure
Precondition: A valid data structure
Postcondition: Data structure duly updated

Answer 1

SOURCE CODE

#include <iostream>

using namespace std;

// node structure definition

struct node

{

    int data;

    struct node *next;

};

// defining list ADT

class linkedList

{

private:

    node *head;

public:

    // simple default constructor

    linkedList();

    // member functions

    void insert_first(int k);

    void delete_node(int pos);

    int search(int k);

    void update(int pos, int new_val);

    void display();

};

linkedList::linkedList()

{

    head = NULL;

}

// CREATE

// this function iunserts a value to the beginning of a list

void linkedList::insert_first(int k)

{

    node *ptr;

    ptr = new node;

    ptr->data = k;

    // if list is empty, insert new node at front

    if (head == NULL)

    {

        ptr->next = NULL;

        head = ptr;

    }

    // otherwise replace head with new node

    else

    {

        ptr->next = head;

        head = ptr;

    }

}

// READ

// This function is used to check the existance of a value

// in a linked list

int linkedList::search(int k)

{

    bool found = false;

    

    node *t = head;

    // if linked list is empty

    if(t == NULL)

        return false;

    

    // traverse the list to look for the value

    while(t->next != NULL)

    {

        // if the data has been found

        if(t->data == k)

        {

            found = true;

            break;

        }

        t = t->next;

    }

    // returns the result of reading the list

    return found;

}

// UPDATE

// alters the value of a particular node in

// linked list

void linkedList::update(int pos, int new_val)

{

    node *t = head;

    int i = 1;

    bool flag = false;

    // if list is empty

    if(t == NULL)

        cout << "\nLinked list is empty";

    else

    {

        // traverse the list

        while(t->next != NULL)

        {

            // if the value has been found

            // stop tarversing

            if(i == pos)

            {

                flag = true;

                break;

            }

            t = t->next;

            i++;

        }

        // if value was found, alter the value

        if (flag)

            t->data = new_val;

        else

            cout << "\nThe position was not found...";

        

    }

}

// DELETE

// function to delete a node at a particular position

void linkedList::delete_node(int pos)

{

    struct node *temp, *s, *ptr;

    int i, f = 0;

    // if position to delete is the first position

    if (pos == 1)

    {

        temp = head;

        head = head->next;

        delete temp;

    }

    // otherwise

    else

    {

        ptr = head->next;

        s = head;

        // traverse to the required position of list

        for (i = 2; i <= pos; i++)

        {

            if(ptr == NULL)

            {

                f = 1;

                break;

            }

            ptr = ptr->next;

            s = s->next;

        }

        if(f == 1)

        {

            cout <<"\nPosition is invalid";

            return;

        }

        s->next = ptr->next;

        delete ptr;

    }

}

// function to display the contents of linked list

void linkedList::display()

{

    int i;

    struct node *ptr;

    

    // if list is empty

    if (head == NULL)

        cout << "\n The list is empty";

    else

    {

        ptr = head;

        cout << "\nThe current state of linked list: ";

        // traverse through the list and print the elements

        while (ptr->next != NULL)

        {

            cout << ptr->data << "->";

            ptr = ptr->next;

        }

        cout << ptr->data;

    }

}

// main function to test the singly linked list implementation

int main()

{

    linkedList ll;

    cout << "\nInserting 10 at first of linked list...";

    ll.insert_first(10);

    cout << "\nInserting 20 at first of linked list...";

    ll.insert_first(20);

    cout << "\nInserting 30 at first of linked list...";

    ll.insert_first(30);

    cout << "\nInserting 40 at first of linked list...";

    ll.insert_first(40);

    ll.display();

    cout << "\nDeleting element at position 2...";

    ll.delete_node(2);

    ll.display();

    cout << "\nLooking for value 40 in linked list...";

    if(ll.search(40))

        cout << "\nFound";

    else

        cout << "\nNot found";

    cout << "\nLooking for value 30 in linked list...";

    if(ll.search(30))

        cout << "\nFound";

    else

        cout << "\nNot found";

    

    cout << "\nUpdating element at position 1...";

    ll.update(1, 21);

    ll.display();

    return 0;

}

OUTPUT