Simple Linked List Class Using an appropriate definition of ListNode, design a s

Question

Simple Linked List Class
Using an appropriate definition of ListNode, design a simple linked list class with only
two member functions and a default constructor:
void add(double x);
boolean isMember(double x);
LinkedList( );
The add function adds a new node containing x to the front (head) of the list, while the isMember function tests to see if the list contains a node with the value x. Test your linked list class by adding various numbers to the list and then testing for membership.

Recursive Member Check
Modify the list class you created in the previous programming challenges to use a recursive method to check for list membership. Test your class.

List Member Deletion
Modify the list class you created in the previous programming challenges by adding a function to remove an item from the list, and by adding a destructor:
void remove(double x);
~LinkedList();
Test the class by adding by a sequence of instructions that mixes operations for adding items, removing items, and printing the list.

List Reverse
Modify the list class you created in the previous programming challenges by adding a member function for reversing the list:
void reverse();
The member function rearranges the nodes in the list so that their order is reversed. You should do this without creating or destroying nodes.

class LinkedList //Class linked list
{
private:
   ListNode *head; //One datamember as private, accessed thru only member functions
public: //Public members started
   LinkedList() //Default constructor
   {
       head=NULL; //Initially head is null
   }

Answers in c++ only.

Please provide necessary comments.

Explanation / Answer

I have defined every functions below:

//adding node before the head
void add(ListNode** head_ref,double new_data)
{
   ListNode* new_node =new ListNode;
       /* put in the data */
       new_node->data = new_data;
       /* link the old list off the new node */
       new_node->next = (*head_ref);
       /* move the head to point to the new node */
       (*head_ref) = new_node;

}
  
//check whether x,is present in linked list or not
bool is_member_itr(ListNode* head,double x) //iterative
{
   while(head!=0)
   {
       if(head->data==x)
       return true;
       head=head->next; //iterating throughout the list if found return true;
   }
   return false;
}
  
//recursive method to check x is present in linked list or not
bool is_member_rec(ListNode* head,double x)
{
   if(head==0)
   return false;
   if(head->data==x)
   return true;
   //recursively checking
   return is_member_rec(head->next,x);
}
  
//how we will remove a node from a linked list,two condition one either node to be deleted is head and second node to be deleted is not head

void remove(ListNode *head,double x)
{
   if(head==0)
   return;
   ListNode *temp=head;
   ListNode *node_to_delete=0;
   while(temp!=0)
   {
       if(temp->data==x)
           {
               node_to_delete=temp; //node to delete found break out of loop and delete the required node
               break;
           }      
   }
   if(node_to_delete!=0) //node to delete is not null
   {
       // When node to be deleted is head node
               if(head == node_to_delete)
               {
                   if(head->next==0)
                   {
                       free(head);
                       return ;
                   }
                   /* Copy the data of next node to head */
                   head->data = head->next->data;
                   // store address of next node
                   node_to_delete = head->next;
                   // Remove the link of next node
                   head->next = head->next->next;
                   // free memory
                   free(node_to_delete);
                   return;
          }
          // When not first node, follow the normal deletion process
               // find the previous node
               ListNode *prev = head;
               while(prev->next != NULL && prev->next != node_to_delete)
               prev = prev->next;
               // Check if node really exists in Linked List
               if(prev->next == NULL)
               {
                   printf(" Given node is not present in Linked List");
                   return;
               }
               // Remove node from Linked List
               prev->next = prev->next->next;
               // Free memory
               free(node_to_delete);
               return;
   }
}
  
//Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.
void reverse(ListNode** head)
{
   ListNode* prev = NULL;
       ListNode* current = *head;
       ListNode* next;
       while (current != NULL)
       {
       next = current->next;
       current->next = prev;
       prev = current;
       current = next;
       }
       *head = prev;
}
  
  

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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