Question

Given:

#include <iostream>
using std::cout;

template <typename T>
struct Node {
T data;
Node *link;
  
   Node(T data=0, Node *p = nullptr) { //Note, this constructor combines both default and parameterized constructors. You may modify the contructor to your needs
this->data = data;
       link = p;
}
};

template <typename T>
class linked_list
{
Node<T> *head,*current;
public:
//default constructor
linked_list() {
head = nullptr;//the head pointer
current = nullptr;//acts as the tail of the list
}

//destructor - IMPORTANT
~linked_list() {
       current = head;
       while( current != nullptr ) {//the loop stops when both current and head are NULL
       head = head->link;
       delete current;
       current = head;
       }
}

void addLast(int n) {// to add a node at the end of the list
if(head == nullptr){
head = new Node<T>(n);
current = head;
} else {
           if( current->link != nullptr)
               current = current->link;
current->link = new Node<T>(n);
current = current->link;//You may decide whether to keep this line or not for the function
}
}
  
void print() { // to display all nodes in the list
Node<T> *tmp = head;
while (tmp != nullptr) {
cout << tmp->data << "\n";
tmp = tmp->link;
}
}
};

int main() {
linked_list<int> a;
a.addLast(1);
a.addLast(2);

   a.print();
  
return 0;
}

2. Implement the following member methods: ▪ addFirst (T data)

// Adds a node with data at the beginning of the list ▪ pop() // Removes the first node of the list. Note: Don't forget to delete/reallocate the removed dynamic memory ▪ contains(T data) //

Returns true or false if a node contains the data exists in the list ▪ update(T oldDate, T newData) //

Updates the oldData of a node in the list with newData. ▪ size()

// Returns the number of nodes in the list ▪ remove( T data) //Removes the node that contains the data. Note, you will need to check if the node exists. Again, don't forget to delete/re-allocate the dynamic memory

3. Implement the following additional member methods ▪ insertAfter(int n, T data)

//Adds a node after the n-th node. Note, you will need to check if the n th node exists, if not, do addLast(). ▪ merge(const LinkedList &linkedlist

) //Merges this object with linkedlist object. In other words, add all nodes in linkedlist to this object.

Answer 1

I managed to find complete solution of your problem. Additionally, I also implemented/called all of these utility functions through our main() method and taken the screenshot of the output. In case you find difficulty in understanding, you can check the comments against that statement.

Lets first look at some key concepts we need to use:-

Add a node at the front:
1) The new node is always added before the head of the given Linked List.
2) And newly added node becomes the new head of the Linked List.
3) For example if the given Linked List is 10->20->30->40 and we add an item 5 at the front, then the Linked List becomes 5->10->20->30->40.

Pop from the beginning:
1) Initialize the head to a temporary node, temp=head.
2) Move the head to next node, head= head -> link.
3) Delete the temporary node, delete temp.

Search for an element:
1) Initialize a node pointer, currentNode = head.
2) Do following while currentNode is not NULL
    a) currentNode->key is equal to the key being searched return true.
    b) currentNode = currentNode->next
3) Return false

Count the number of nodes :
1) Initialize count as 0
2) Initialize a node pointer, temp = head.
3) Do following while temp is not NULL
     a) temp = temp -> next
     b) count++;
4) Return count

Delete a specific element/node:
1) Find the previous node(prev) of the node to be deleted(temp).
2) Change the next of the previous node, prev->link = temp->link.
3) Free memory for the node to be deleted, delete temp.

Insert after a given node:
Insert a node x after the nth node from the end in the given singly linked list. It is guaranteed that the list contains the nth node from the end. Also 1 <= n.
Examples:
Input : list: 1->3->4->5
        n = 4, x = 2
Output : 1->2->3->4->5
(4th node from the end is 1 and insertion has been done after this node)

Here is the code for the same:-

#include <iostream>
using std::cout;
using namespace std;

template <typename T>
struct Node {
T data;
Node *link;

   Node(T data=0, Node *p = NULL) { //Note, this constructor combines both default and parameterized constructors.
                                        // You may modify the contructor to your needs
       this->data = data;
        link = p;
   }
};

template <typename T>
class linked_list
{
   Node<T> *head,*current;
   public:
   //default constructor
   linked_list() {
   head = NULL;//the head pointer
   current = NULL;//acts as the tail of the list
   }

   //destructor - IMPORTANT
   ~linked_list() {
       current = head;
       while( current != NULL ) {//the loop stops when both current and head are NULL
       head = head->link;
       delete current;
       current = head;
       }
   }

   void addLast(int n) {// to add a node at the end of the list
       if(head == NULL){
           head = new Node<T>(n);
           current = head;
       } else {
           if( current->link != NULL)
               current = current->link;
               current->link = new Node<T>(n);
               current = current->link;//You may decide whether to keep this line or not for the function
           }
   }
   //Question 2 Starts
   //Adds a node with data at the beginning of the list
   void addFirst(int n){
       if(head==NULL){//check if list is NULL
           head = new Node<T>(n);
           current = head;
       }
       else{
           Node<T> *newNode= new Node<T>(n); //Allocate node
           newNode->link = head; //Link to the head node
           head = newNode; //New head of the list
       }
   }
  
   // Removes the first node of the list.
   void pop(){
       //Declare a temp and point to head
       Node<T> *temp= head;
       //Move the head to next node
       head= head->link;
       //Show the element to be deleted
       cout<<"\nElement to be deleted is : "<<temp->data;
       //Delete temp
       delete temp;
       //Show the new head
       cout<<"\nThe new Head of the List is : "<<head->data;
      
   }
  
   //Returns true or false if a node contains the data
   bool contains(T data)
   {
       Node<T> *temp=head; //initialize loop variable
       while(temp != NULL){
           if(temp->data == data){ //If found return true
               return true;
           }
           temp= temp->link; //move the temp if not found
       }
       return false; //If not found
   }
  
   //Updates the oldData of a node in the list with newData
   void update(T oldData, T newData){
       Node<T> *temp=head; //initialize temporary node as head
       while(temp != NULL){
           if(temp->data == oldData){ //If oldData found change with newData
               temp->data = newData;
           }
           temp= temp->link; //move the temp if not found
       }
   }
  
   //Returns the number of nodes in the list
    int getCount() {
       int count = 0; // Initialize count
       Node<T>* temp = head; // Initialize temporary node
       while (temp != NULL) {
           count++; //Increase count number
           temp = temp->link;
       }
       return count; //Return the total count
   }
  
   //Removes the node that contains the data.
   //Note, you will need to check if the node exists.
   void remove(T data){
       if(head->link == NULL)
        {
            cout << "\nThere is only one node." <<
                    " The list can't be made empty...";
            return;
        }
      
       Node<T> *temp = head; // Initialize temporary node as Head
       Node<T> *prev = temp;
       // 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 != data){
           temp = temp->link;
       }
      
       // If key was not present in linked list
        if (temp == NULL) return;

       // Unlink the node from linked list
       prev->link = temp->link;

       delete temp; // Free memory
   }
   //Question 2 ends
   //Question 3 starts
  
   //Adds a node after the n-th node. Note, you will
   // need to check if the n th node exists, if not, do addLast()
   void insertAfter(int n, T data){
       // if list is empty, do addLast
       if (head == NULL){
           addLast(data);
       }
      
       // get a new node for data
       Node<T>* newNode = new Node<T>(data);
       Node<T>* ptr = head;
       int len = 0, i;

       // find number of nodes in the list
       while (ptr != NULL) {
            len++;
            ptr = ptr->link;
        }

       // traverse up to the nth node from the end
       ptr = head;
       for (i = 1; i <= (len - n); i++)
           ptr = ptr->link;

       // insert the 'newNode' by making the
        // necessary adjustment in the links
       newNode->link = ptr->link;
       ptr->link = newNode;
   }
  
   //merge(const linked_List &linked_list)
   //Merges this object with linkedlist object, i.e., add all nodes in linkedlist to this object.
   //This is somewhat like copy constructor
   void merge(const linked_list &linkedlist){
       if(linkedlist.head == NULL){
           head=NULL;
       }
       else{
           //passing the data to the head
           head = new Node<T>(linkedlist.head->data);
           Node<T> *cur = head; //current
           Node<T> *listHead = linkedlist.head; //object head
           Node<T> *curList = listHead; //current object
          
           while(curList->link != NULL){
               cur->link = new Node<T>(curList->link->data);
               curList = curList->link; //Shift current object
               cur = cur->link; //Shift current node
           }
       }
   }
  
   //Question 3 ends
   void print() { // to display all nodes in the list
       Node<T> *tmp = head;
       cout<<"\nElements of the List are: ";
       while (tmp != NULL) {
           cout << tmp->data << " ";
           tmp = tmp->link;
       }
       cout<<"\n";
   }
  
};

int main() {
   linked_list<int> a;
   a.addLast(1);
   a.addLast(3);
   a.addLast(4);
   a.addFirst(5);
   a.addFirst(2);
   a.insertAfter(2,6);
   a.insertAfter(3,8);
   a.print();
  
   a.pop();
   cout<<"\nEnter number to check if present : ";
   int search;
   cin>>search;
   if(a.contains(search))
       cout<<"Present";
   else
       cout<<"Not Present";
   cout<<"\n***Updating 3 with value 9***\n";
   a.update(3,9);
   a.print();
   cout<<"\nTotal number of elements in the list: "<<a.getCount();
  
   cout<<"\nEnter element to remove from the list :";
   int x;
   cin>>x;
   a.remove(x);
   a.print();
  
   //Call merge()
   linked_list<int> b=a;
   a.addLast(9);
   cout<<"\nList 1\n";
   a.print();
   cout<<"\nList 2\n";
   b.print();
  
   return 0;
}

Output for the same is:-

Ask doubts in the comment section.

Happy Learning...