Question

1 Problem Description

This lab will cover a new topic: linked lists. The basic idea of a linked list is that an address or a pointer value to one object is stored within another object. By following the address or pointer value (also called a link), we may go from one object to another object. Understanding the pointer concept (which has be emphasized in previous labs and assignments) is crucial in understanding how a linked list operates.

Your task will be to add some code to manipulate the list.

2 Purpose

Understand the concept of linked lists, links or pointers, and how to modify a linked list.

3 Design

A very simple design of a node structure and the associated linked list is provided lab7.cpp. Here is the declaration:

typedef int element_type; 

struct Node 

{ 

    element_type elem; 

    Node * next;

    Node * prev; // not used for this lab 

}; 

Node * head; 

NOTE: A struct is conceptually the same thing as a class. The only significant difference is that every item (each method and data field) is public. Structs are often used as simple storage containers, while classes encompass complex data and methods on that data. Nodes of a linked list are good examples of where a struct would be useful.

Since head is a pointer that points to an object of type Node, head->elem ( or (*head).elem ) refers to the elem field. Similarly, head->next refers to the next field, the value of which is a pointer and may point to another node. Thus, we are creating a chain of Nodes. Each node points to the next Node in the chain.

Note that in our program head should always points to the first node of the linked list. For a linked list that has no elements (an empty list), the value of head is NULL. When working with linked lists, it is usually helpful to draw them out in order to understand their operation.

4 Implementation

Note that this file contains a show() function that will display the contents of a linked list in order. As with previous labs, you must call show() after each of the following steps.

1. Remove the first element from the linked list. Make sure to free the space for the Node correctly, and make sure that head is now pointing to the correct node in the list. When your code is working, you should see the node sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].
2. Remove the last element from the list, assuming that we do not know how many nodes are in the linked list initially. Make sure to free the space and set the pointers correctly. Hint: we need to traverse the list to find the second to last Node. Once we have the pointer to that node we can safely remove the last node. One way to accomplish this is to store both a current pointer that points to the current node in the chain, and a previous pointer that points to the node containing the last element we saw. The previous pointer follows the current pointer through the list. When your code is working, you should see the node sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14].
3. Insert ten elements (0 to 9 for element values) to the beginning of the current linked list, each being placed at the beginning. You must use a loop here (so we can easily change the action to insert 1000 elements (0 to 999) for instance). When your code is working, you should see the node sequence [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. The basic procedure is to create a new node, set its next pointer to the head of the list, and then move the head to your new node.
4. Insert ten elements (0 to 9 for element values) after the first node having value 7 in the current linked list. You will need to loop through the list to find the node that has 7 (again, do not assume you know where the 7 is. You should search for it.) Once you find the correct starting point, you will need to integrate your new nodes into the list one at a time. When your code is working, you should see the node sequence [9, 8, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. One possible procedure will be to first get the node after 7 (e.g. the first node containing a 6, note that current points to the node of 7 in the search is assumed in the following), and make variable “end” points to the node. Create a new node with proper value, set this node's next to the end (node 6), set current's next to the new node. Depending on the order of inserting these values, we may either update end so that it points to the new node or move current so that it points to the new node. Then repeat creating a new node action.

Please write in C++

Basic Linked Lists Starter Code:

#include <cstdlib>
#include <iostream>

using namespace std;

// Data element type, for now it is int, but we could change it to anything else
// by just changing this line
typedef int element_type;

// Basic Node structure
struct Node
{
    element_type elem;  // Data
    Node * next;        // Pointer to the next node in the chain
    Node * prev;        // Pointer to the previous node in the chain, not used for lab 7
};

// Print details about the given list, one Node per line
void show(Node* head)
{
    Node* current = head;
    
    if (current == NULL)
        cout << "It is an empty list!" << endl;
    
    int i = 0;
    while (current != NULL) 
    {
        cout << "Node " << i << "\tElem: " << '\t' << current->elem << "\tAddress: " << current << "\tNext Address: " << current->next << endl;
        current = current->next;
        i++;
    }
    
    cout << "----------------------------------------------------------------------" << endl;
}

int main() 
{
    const int size = 15;

    Node* head    = new Node();
    Node* current = head;

    // Create a linked list from the nodes
    for (int i = 0; i < size; i++)
    {
        current->elem = i;
        current->next = new Node();
        current       = current->next;
    }
    
    // Set the properties of the last Node (including setting 'next' to NULL)
    current->elem = size;
    current->next = NULL;
    show(head);

    // TODO: Your Code Here Please use show(head); after completing each step.
STEP 1:


STEP 2:


STEP3:    


STEP 4:

    // Clean up
    current = head;
    while (current != NULL)
    {
        Node* next = current->next;
        delete current;
        current = next;
    }
    
    return 0;
}

Answer 1

 Step 1:
    Node *temp=head->next;  // Storing adress of 2nd element in pointer temp.
    delete head;
    head=temp;             //Changing the 2nd node to 1st Node after deletion.
    show(head);

Step 2:
    temp=head;
    while((temp->next->next)!=NULL)   // condition of reaching 2nd last Node
    {
        temp=temp->next;
    }
    Node* lastnode= temp->next;
    delete lastnode;
    temp->next=NULL;     // Changing 2nd last node into last node.
    show(head);

Step 3:
    int i=0;
    while(i!=10)
    {
        Node *newnode=new Node();
        newnode->elem=i;
        newnode->next=head;         // Connecting the head to newly constructed node.
        head=newnode;               // Making the newly constructed node head of linked list.
        i++;
    }
    show(head);

 Step 4:
    temp=head;
    while(temp->elem!=7)    // Searching for the element in linked list
    {
        temp=temp->next;
    }
    int j=0;
    while(j!=10)
    {
        Node *new_node=new Node(); 
        new_node->elem=j;
        new_node->next=temp->next;   // Connecting new_node to the node that is currently connected to element.
        temp->next=new_node;         // Connecting element to the newly constructed node.
        temp=temp->next;             // Updating the element to next node to insert further elements.
        j++;
    }
    show(head);

I am attaching the working code for all the required steps in the problem. The steps are explained with comments alongside. On dry run on notebook you will get the clear idea of the working of code.

Hope it helps.