Saturday, December 27, 2014

Implementing Reversal Operation on Linked List using recursion/less temporary variables - Data Structures - C++ Program (Procedural)





Problem Question


To implement Reversal of a Linked List using Recursion. This paradigm makes use of processor stack, instead of using a dedicated loop to do the job.

Explanation of Problem


In this program we would be implementing a Linked List. Make sure you have a strong understanding of pointers to understand Linked Lists. A linked list is a basic data structure that is used in dynamic memory allocation applications. It comprises of 'nodes' which are linked together to form a sequence of nodes called Linked List. The linkage is done using memory addresses of adjacent nodes (next node in singly linked list, and both next & previous node in doubly linked list).






In this program we use a struct to implement the node of our linked list. We will implement addition function to get some data in linked list before we can perform desired operations on it. Adding a new node to the list means, creating a new node structure, allocating memory to it and linking it to the list.

Code


#include<iostream>

/**@Title: LinkedList v1.7.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-12-2014*
*/

struct node
{
  int data;
  node* next;
};

void addAtLast(node** rootNode);
node* reverseList(node* rootNode);
void displayList(node* rootNode);

int main()
{
  int choice;
  node *startList = NULL;
  std::cout << "Welcome to LinkedList v1.5" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Reverse List" <<
         std::endl << "3 : Display List" <<
         std::endl << "4 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        addAtLast(&startList);
        break;
    case 2:
        startList = reverseList(startList);
        break;
    case 3:
        displayList(startList);
        break;
    case 4:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.7"<<std::endl<<"Made by Rogue Coder"
           <<std::endl<<"Press any key to exit"<<std::endl;
      break;
    default:
      std::cout<<"\a\aWrong Choice\a\a"<<std::endl;
      break;
    }
  }
  while(choice != 4);
  std::cin.get();
  return 0;
}

void addAtLast(node** rootNode)
{
   node* newNode = new node;
   std::cout<<std::endl<<"Enter data : ";
   std::cin>>newNode -> data;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}

node* reverseList(node* rootNode)
{
    if (rootNode == NULL || rootNode -> next == NULL)
    {
        return rootNode;
    }
    node* remainingList = reverseList(rootNode -> next);
    rootNode -> next -> next = rootNode;
    rootNode -> next = NULL;
    return remainingList;
}

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}


Explanation of Code





#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

using namespace std; -> In modern IDEs, we have to explicitly write std::cout instead of cout to use the ostream cout object. Namespace std helps in easing off the pain of writing std:: again and again. Though make sure you are not trapped! The classes defined in std should not be redefined by you. So in case you want to define a class 'distance', you can't do so if you have used std namespace. Though you can define 'Distance' (capital D).

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.



struct node
{
  int data;
  node* next;
};
->
This is where we create the struct node that is going to be the building block of our linked list. It comprises of an int 'data' where the user shall store the data they wish. Please note, you can use as many variables and of as many types in the struct, but be sure you handle them correctly. For simplicity we have used int type in our case. The other variable inside our node is 'next', which is a pointer to node. This would be used to build the linkage between the nodes of our linked list. 'next' is going to hold the address of the next node in the sequence.

node* startList; -> The global pointer ‘startList’ which we are going to use to point to the first node/root node/ start node of the linked list, we are going to implement in this program.

int choice; -> This variable 'choice' will be used for the user’s choice in the menu driven program.





void addAtLast(node** rootNode)
{
   node* newNode = new node;
   std::cout<<std::endl<<"Enter data : ";
   std::cin>>newNode -> data;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}
->
This function is used to add a new node at the end of our linked list. It asks for user input and the data is stored in the ‘newNode’ which is the pointer to the new node that we are going to add to our list. The first statement of this function means, memory is allocated for a node type variable and a pointer is returned which we capture in the variable ‘newNode’. After the user input the program checks if the list is empty which we come to know if the ‘rootNode’, i.e., root node of the linked list is initialised as yet or not. If the root node is not yet initialised for our list, we make the ‘rootNode’ pointer to point to the ‘newNode’ we just created. Else, we traverse through the list. Starting from the root node, we hold the position in a new pointer, ‘currentNode’. Since the last node’s ‘next’ won’t point to any node, thus we use currentNode->next != NULL for that. Till so is the case, we keep on assigning the address of the next node in sequence to the pointer ‘currentNode’. So as and when we encounter the last node in the list, we come out of the loop. The pointer ‘currentNode’ now holds the address to the last node in the list. So we define the ‘next’ for this last node of ours as the newNode we just created. Now the next of newNode is set to NULL, hence the newNode is added at the end of the list.
node* reverseList(node* rootNode)
{
    if (rootNode == NULL || rootNode -> next == NULL)
    {
        return rootNode;
    }
    node* remainingList = reverseList(rootNode -> next);
    rootNode -> next -> next = rootNode;
    rootNode -> next = NULL;
    return remainingList;
}
->
This is the recursive function that would reverse the list and return the header node back. If the rootNode itself is NULL, it means list is empty. If rootNode is the only node, i.e., rootNode -> next is NULL, there's nothing to reverse. In these two cases we return back rootNode.
The heart of the function is to reverse one node, and push rest of the list to stack. Thus, node* remainingList = reverseList(rootNode -> next);, here we send send the list but the first node back to the function recursively, until we are at the last node, when we would simply return(if clause, as explained above).
Then we make this separated rootNode to be the successor of it's sucessor, reversing the connection in effect. Then we mark this node to point to NULL, as if it was the last node, and we return back the remaining List, via, remainingList, which is the pointer to rootNode of the rest of the list.

Consider example list 1 -> 2 -> 3 -> 4 -> 5 .
Lets iterate through the function's recursion stack and see what happens.



  1. rootNode is not NULL. rootNode is not the only node either. So we have rootNode pointing to 1, and we send pointer to 2 to the new call.
  2. Now rootNode is holding pointer to 2. This is not NULL, and is not the only node either. So we send pointer to 3 to the new call.
  3. Now rootNode is holding pointer to 3. This is not NULL, and is not the only node either. So we send pointer to 4 to the new call.
  4. Now rootNode is holding pointer to 4. This is not NULL, and is not the only node either. So we send pointer to 5 to the new call.
  5. Now rootNode is holding pointer to 5. This is not NULL, but is the only node. So we return pointer to 5 back to the call.
  6. Now the control is with the previous call, where we called our function with pointer to 4. Here rootNode is holding 4 (and 4 points to 5 as the original 'next' value), and remainingList is holding 5. We will now reverse the connections. Right now the list is 4 -> 5. So we make 5 to point to 4, and 4 to point to NULL. Thus our list becomes 5 -> 4 . We return back the address of 5 to the call.
  7. Now the control is with the previous call, where we called our function with pointer to 3. Here rootNode is holding 3 (and 3 points to 4 as the original 'next' value), and remainingList is holding address to 5(thus in effect 5 -> 4, as returned by previous call). We will now reverse the connections. Right now the list is 3 -> 4 and 5 -> 4. So we make 4 to point to 3, and 3 to point to NULL. Thus our list becomes 5 -> 4 -> 3. We return back the address of 5 to the call.
  8. Now the control is with the previous call, where we called our function with pointer to 2. Here rootNode is holding 2 (and 2 points to 3 as the original 'next' value), and remainingList is holding address to 5(thus in effect 5 -> 4 -> 3, as returned by previous call). We will now reverse the connections. Right now the list is 2 -> 3 and 5 -> 4 -> 3. So we make 3 to point to 2, and 2 to point to NULL. Thus our list becomes 5 -> 4 -> 3 -> 2. We return back the address of 5 to the call.
  9. Now the control is with the previous call, where we called our function with pointer to 1. Here rootNode is holding 1 (and 1 points to 2 as the original 'next' value), and remainingList is holding address to 5(thus in effect 5 -> 4 -> 3 -> 2, as returned by previous call). We will now reverse the connections. Right now the list is 1 -> 2 and 5 -> 4 -> 3 -> 2. So we make 2 to point to 1, and 1 to point to NULL. Thus our list becomes 5 -> 4 -> 3 -> 2 -> 1. We return back the address of 5 to the call.
  10. Previous one was the last call on our recursion stack. Thus, we return the address of 5 as the address of rootNode to the call. Thus, we have reversed the list.

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}
->
This function is used to display the list. The functions accepts the address of the root node as the argument. It then starts traversing through the list from root node, until it finds a node which points to NULL as the next element, indicating the end of list. While traversing through, the function displays the values held in each node on the screen separated by '->'.




do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)









Download Source Code



Tuesday, December 09, 2014

Implementing Delete Operations on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement Delete Operations on a Linked List. This includes deleting a node at particular position, deleting a node based on value(search and delete first occurrence), deleting all nodes with a specific value(search and delete all occurrences).

Explanation of Problem


In this program we would be implementing a Linked List. Make sure you have a strong understanding of pointers to understand Linked Lists. A linked list is a basic data structure that is used in dynamic memory allocation applications. It comprises of 'nodes' which are linked together to form a sequence of nodes called Linked List. The linkage is done using memory addresses of adjacent nodes (next node in singly linked list, and both next & previous node in doubly linked list).



In this program we use a struct to implement the node of our linked list. We will implement addition function to get some data in linked list before we can perform desired operations on it. Adding a new node to the list means, creating a new node structure, allocating memory to it and linking it to the list.




Code


#include<iostream>

/**@Title: LinkedList v1.6.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-12-2014*
*/

struct node
{
  int data;
  node* next;
};

node* deleteNodeFirst(node* rootNode);
node* deleteNodeGlobal(node* rootNode);
node* deleteNode(node* rootNode);
void addAtLast(node** rootNode);
void displayList(node* rootNode);

int main()
{
  int choice;
  node *startList = NULL;
  std::cout << "Welcome to LinkedList v1.5" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Find and Delete First Occurrence" <<
         std::endl << "3 : Find and Delete All Occurrences" <<
         std::endl << "4 : Delete node at specific position" <<
         std::endl << "5 : Display List" <<
         std::endl << "6 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        addAtLast(&startList);
        break;
    case 2:
        startList = deleteNodeFirst(startList);
        break;
    case 3:
        startList = deleteNodeGlobal(startList);
        break;
    case 4:
        startList = deleteNode(startList);
        break;
    case 5:
        displayList(startList);
        break;
    case 6:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.6"<<std::endl<<"Made by Rogue Coder"
           <<std::endl<<"Press any key to exit"<<std::endl;
      break;
    default:
      std::cout<<"\a\aWrong Choice\a\a"<<std::endl;
      break;
    }
  }
  while(choice != 6);
  std::cin.get();
  return 0;
}

void addAtLast(node** rootNode)
{
   node* newNode = new node;
   std::cout<<std::endl<<"Enter data : ";
   std::cin>>newNode -> data;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}

node* deleteNodeFirst(node* rootNode)
{
    int searchKey;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Value to Delete: ";
    std::cin>>searchKey;
    if(rootNode -> data == searchKey)
    {
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        return rootNode -> next;
    }
    node* currentNode = rootNode;
    while (currentNode -> next)
    {
        if(searchKey == currentNode -> next -> data)
        {
            currentNode -> next = currentNode -> next -> next;
            return rootNode;
        }
        currentNode = currentNode -> next;
    }
    std::cout<<"Value not Found";
    return rootNode;
}

node* deleteNodeGlobal(node* rootNode)
{
    int searchKey, value_found = 0;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Value to Delete: ";
    std::cin>>searchKey;
    while(rootNode -> data == searchKey)
    {
        value_found++;
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        rootNode = rootNode -> next;
    }
    node *currentNode = rootNode;
    while (currentNode)
    {
        if(currentNode -> next == NULL && value_found == 0)
        {
            std::cout<<"Value not Found!";
            return rootNode;
        }
        while(currentNode -> next != NULL && searchKey == currentNode -> next -> data)
        {
            value_found++;
            currentNode -> next = currentNode -> next -> next;
        }
        currentNode = currentNode -> next;
    }
    return rootNode;
}

node* deleteNode(node* rootNode)
{
    int deletePosition;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Position to Delete: ";
    std::cin>>deletePosition;
    if (deletePosition < 1)
    {
        std::cout<<"Position Out of Bounds";
        return rootNode;
    }
    if (deletePosition == 1)
    {
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        return rootNode -> next;
    }
    if (deletePosition == 2)
    {
        if(rootNode -> next == NULL)
        {
            std::cout<<"Position Out of Bounds";
            return rootNode;
        }
        rootNode -> next = rootNode -> next -> next;
        return rootNode;
    }
    node *currentNode = rootNode;
    int node_number = 1;
    while (node_number < deletePosition - 1 && currentNode)
    {
        node_number++;
        currentNode = currentNode -> next;
        if (currentNode -> next == NULL)
        {
            std::cout<<"Position Out of Bound";
            return rootNode;
        }
    }
    if (currentNode == NULL)
    {
        std::cout<<"Position Out of Bound";
        return rootNode;
    }
    currentNode -> next = currentNode -> next -> next;
    return rootNode;
}

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}


Explanation of Code





#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

using namespace std; -> In modern IDEs, we have to explicitly write std::cout instead of cout to use the ostream cout object. Namespace std helps in easing off the pain of writing std:: again and again. Though make sure you are not trapped! The classes defined in std should not be redefined by you. So in case you want to define a class 'distance', you can't do so if you have used std namespace. Though you can define 'Distance' (capital D).

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.




struct node
{
int data;
node* next;
}; ->
This is where we create the struct node that is going to be the building block of our linked list. It comprises of an int 'data' where the user shall store the data they wish. Please note, you can use as many variables and of as many types in the struct, but be sure you handle them correctly. For simplicity we have used int type in our case. The other variable inside our node is 'next', which is a pointer to node. This would be used to build the linkage between the nodes of our linked list. 'next' is going to hold the address of the next node in the sequence.

node* startList; -> The global pointer ‘startList’ which we are going to use to point to the first node/root node/ start node of the linked list, we are going to implement in this program.

int choice; -> This variable 'choice' will be used for the user’s choice in the menu driven program.



void addAtLast(node** rootNode)
{
   node* newNode = new node;
   std::cout<<std::endl<<"Enter data : ";
   std::cin>>newNode -> data;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}
->
This function is used to add a new node at the end of our linked list. It asks for user input and the data is stored in the ‘newNode’ which is the pointer to the new node that we are going to add to our list. The first statement of this function means, memory is allocated for a node type variable and a pointer is returned which we capture in the variable ‘newNode’. After the user input the program checks if the list is empty which we come to know if the ‘rootNode’, i.e., root node of the linked list is initialised as yet or not. If the root node is not yet initialised for our list, we make the ‘rootNode’ pointer to point to the ‘newNode’ we just created. Else, we traverse through the list. Starting from the root node, we hold the position in a new pointer, ‘currentNode’. Since the last node’s ‘next’ won’t point to any node, thus we use currentNode->next != NULL for that. Till so is the case, we keep on assigning the address of the next node in sequence to the pointer ‘currentNode’. So as and when we encounter the last node in the list, we come out of the loop. The pointer ‘currentNode’ now holds the address to the last node in the list. So we define the ‘next’ for this last node of ours as the newNode we just created. Now the next of newNode is set to NULL, hence the newNode is added at the end of the list.






node* deleteNodeFirst(node* rootNode)
{
    int searchKey;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Value to Delete: ";
    std::cin>>searchKey;
    if(rootNode -> data == searchKey)
    {
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        return rootNode -> next;
    }
    node* currentNode = rootNode;
    while (currentNode -> next)
    {
        if(searchKey == currentNode -> next -> data)
        {
            currentNode -> next = currentNode -> next -> next;
            return rootNode;
        }
        currentNode = currentNode -> next;
    }
    std::cout<<"Value not Found";
    return rootNode;
}
->
This function implements deletion of the node which is the first occurrence of a value user inputs. We have a variable 'searchKey', which stores the user input value, the data which we need to find and remove from the list.
The function returns the address of the rootNode of the list, thus in the call to the function we are setting 'startList' variable with the value returned from this function.
We first check if the list is empty. This is done by chcking if the rootNode points to NULL. If so, we prompt the same thing to the user, and return NULL.
Next, we grab user input to get the value that we wish to lookup in the list.
If the value exists at the rootNode, and rootNode is the only node in the list, then we return NULL back(i.e., list is emptied). Otherwise, if the value exists on the rootNode, we set rootNode to point to the next node, and returin this to the function call.
Next, if above checks are untrue, we proceed with list traversal.
We store the rootNode address in a temp variable, 'currentNode', and use it to travers through the list, until we find a node, who's successor has the data we are looking for. If we find such node, we make it to point to the node next to its original successor, removing the successor from the list in effect, and return the rootNode address, else we keep traversing. Once the traversal is complete, and we didnt find the data(if we would have had, out progrma would have returned back, in the if clause itself), we prompt the message to the user 'Value not found' and return the rootNode address back to the function call.

node* deleteNodeGlobal(node* rootNode)
{
    int searchKey, value_found = 0;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Value to Delete: ";
    std::cin>>searchKey;
    while(rootNode -> data == searchKey)
    {
        value_found++;
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        rootNode = rootNode -> next;
    }
    node *currentNode = rootNode;
    while (currentNode)
    {
        if(currentNode -> next == NULL && value_found == 0)
        {
            std::cout<<"Value not Found!";
            return rootNode;
        }
        while(currentNode -> next != NULL && searchKey == currentNode -> next -> data)
        {
            value_found++;
            currentNode -> next = currentNode -> next -> next;
        }
        currentNode = currentNode -> next;
    }
    return rootNode;
}
->
This function implements deletion of all the nodes where the data matches to the value user inputs. We have a variable 'searchKey', which stores the user input value, the data which we need to find and remove from the list.
The function returns the address of the rootNode of the list, thus in the call to the function we are setting 'startList' variable with the value returned from this function.
We first check if the list is empty. This is done by chcking if the rootNode points to NULL. If so, we prompt the same thing to the user, and return NULL.
Next, we grab user input to get the value that we wish to lookup in the list.
The first while loop: The code checks if the value exists at the rootNode, it resets the rootNode to it's successor. We have used a while loop to take care of streak of values. For example, if the value existed at a series of positions from 1 to n, this loop takes care of all such values.
Though, if we encounter the node to be last node(rootNode -> next == NULL), we return an empty list back(return NULL, resets the rootNode address).
Next, we proceed with list traversal.
We store the rootNode address in a temp variable, 'currentNode', and use it to travers through the list. We are looking for such a node, who's successor contains the data we wish to delete. If we find such node, we mark its successor as the next node of the original successor. Again, we keep doing this, in case we have a sequence of such nodes (while(currentNode -> next != NULL && searchKey == currentNode -> next -> data)). This process deletes all occurrences of the nodes with the user input value.
When we are able to find the value in the list, we also increment the flag value_found so that we can prompt the user in case of unsuccessful search.
If we reach the second last node, and we still don't find any node who's successor has the data we are looking for, and the value_found flag is 0, we prompt the user with a Value not found message.

node* deleteNodeGlobal(node* rootNode)
{
    int searchKey, value_found = 0;
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
        return NULL;
    }
    std::cout<<"Enter the Value to Delete: ";
    std::cin>>searchKey;
    while(rootNode -> data == searchKey)
    {
        value_found++;
        if(rootNode -> next == NULL)
        {
            return NULL;
        }
        rootNode = rootNode -> next;
    }
    node *currentNode = rootNode;
    while (currentNode)
    {
        if(currentNode -> next == NULL && value_found == 0)
        {
            std::cout<<"Value not Found!";
            return rootNode;
        }
        while(currentNode -> next != NULL && searchKey == currentNode -> next -> data)
        {
            value_found++;
            currentNode -> next = currentNode -> next -> next;
        }
        currentNode = currentNode -> next;
    }
    return rootNode;
}
->
This functions implements the logic to delete the node at a given position from the linked list. The function returns back the address of the rootNode once it completes. The function first checks if the rootNode is pointing to NULL, if so, that means the lit is empty. A prompt is returned to the user in such case. Else, we move ahead, and ask for user to input the position of the node which the user wants to remove. Please note, in my implementation, the first node is positioned 1, not 0.
If the user input is less than 1, that means it is not a valid location, we prompt user with such information and return.
If the user inputs 1, that means the user wants to delete the rootNode. In such case, we return NULL if rootNode is the only node in the list. Else, rootNode is set as the next node and the function returns next node's address to the call.
If the user had input 2, and we didn't have this position available, we prompt the user with message value out of bounds, else we set change the successor of the rootNode as the next node to original successor.
Otherwise, we traverse through the list, until we reach the node before the one we wish to delete. Once we reach there, we replace the next node address, with that of next to next node. If we don't find such node, we prompt position out of bound and return.





void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}
->
This function is used to display the list. The functions accepts the address of the root node as the argument. It then starts traversing through the list from root node, until it finds a node which points to NULL as the next element, indicating the end of list. While traversing through, the function displays the values held in each node on the screen separated by '->'.

do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)

















Download Source Code



Thursday, November 27, 2014

Implementing Search and Add/Replace Operations on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement Search and Replace, Add Before Value, and Add After Value Operations on a Linked List

Explanation of Problem


In this program we would be implementing a Linked List. Make sure you have a strong understanding of pointers to understand Linked Lists. A linked list is a basic data structure that is used in dynamic memory allocation applications. It comprises of 'nodes' which are linked together to form a sequence of nodes called Linked List. The linkage is done using memory addresses of adjacent nodes (next node in singly linked list, and both next & previous node in doubly linked list).



In this program we use a struct to implement the node of our linked list. We will implement addition function to get some data in linked list before we can perform desired operations on it. Adding a new node to the list means, creating a new node structure, allocating memory to it and linking it to the list.




Code


#include<iostream>

/**@Title: LinkedList v1.5.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-11-2014*
*/

struct node
{
  int data;
  node* next;
};

void addAfter(node* rootNode);
void addBefore(node* rootNode);
void addAtLast(node** rootNode);
void replaceValue(node* rootNode);
node* findNode(int SearchKey, node* rootNode);
void displayList(node* rootNode);

int main()
{
  int choice;
  node *startList = NULL;
  std::cout << "Welcome to LinkedList v1.5" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Add Value After" <<
         std::endl << "3 : Add Value Before" <<
         std::endl << "4 : Find And Replace Value" <<
         std::endl << "5 : Display List" <<
         std::endl << "6 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        addAtLast(&startList);
        break;
    case 2:
        addAfter(startList);
        break;
    case 3:
        addBefore(startList);
        break;
    case 4:
        replaceValue(startList);
        break;
    case 5:
        displayList(startList);
        break;
    case 6:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.4"<<std::endl<<"Made by Rogue Coder"
           <<std::endl<<"Press any key to exit"<<std::endl;
      break;
    default:
      std::cout<<"\a\aWrong Choice\a\a"<<std::endl;
      break;
    }
  }
  while(choice != 6);
  std::cin.get();
  return 0;
}

void addAtLast(node** rootNode)
{
  node* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(*rootNode == NULL)
  {
    *rootNode = newNode;
  }
  else
  {

    node* currentNode = *rootNode;
    while(currentNode->next != NULL)
    {
      currentNode = currentNode->next;
    }
    currentNode->next=newNode;
  }
  newNode->next=NULL;
}

node* findNode(int SearchKey, node* rootNode)
{
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
    }
    else
    {
        node* currentNode = rootNode;
        while (currentNode)
        {
            if(SearchKey == currentNode -> data)
            {
                return currentNode;
            }
            currentNode = currentNode -> next;
        }
    }
    return NULL;
}

void addAfter(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL, *tempNode = NULL, *newNode = new node;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter the Value to add: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        tempNode = searchNode -> next;
        searchNode -> next = newNode;
        newNode -> next = tempNode;
        newNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}

void addBefore(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL, *newNode = new node;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter the Value to add: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        newNode -> data = searchNode -> data;
        newNode -> next = searchNode -> next;
        searchNode -> next = newNode;
        searchNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}

void replaceValue(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter new Value: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        searchNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}


Explanation of Code





#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

using namespace std; -> In modern IDEs, we have to explicitly write std::cout instead of cout to use the ostream cout object. Namespace std helps in easing off the pain of writing std:: again and again. Though make sure you are not trapped! The classes defined in std should not be redefined by you. So in case you want to define a class 'distance', you can't do so if you have used std namespace. Though you can define 'Distance' (capital D).

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.




struct node
{
int data;
node* next;
};
->

This is where we create the struct node that is going to be the building block of our linked list. It comprises of an int 'data' where the user shall store the data they wish. Please note, you can use as many variables and of as many types in the struct, but be sure you handle them correctly. For simplicity we have used int type in our case. The other variable inside our node is 'next', which is a pointer to node. This would be used to build the linkage between the nodes of our linked list. 'next' is going to hold the address of the next node in the sequence.

node* startList; -> The global pointer ‘startList’ which we are going to use to point to the first node/root node/ start node of the linked list, we are going to implement in this program.

int choice; -> This variable 'choice' will be used for the user’s choice in the menu driven program.




void addAtLast(node** rootNode)
{
  node* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(*rootNode == NULL)
  {
    *rootNode = newNode;
  }
  else
  {

    node* currentNode = *rootNode;
    while(currentNode->next != NULL)
    {
      currentNode = currentNode->next;
    }
    currentNode->next=newNode;
  }
  newNode->next=NULL;
} ->


This function is used to add a new node at the end of our linked list. It asks for user input and the data is stored in the ‘newNode’ which is the pointer to the new node that we are going to add to our list. The first statement of this function means, memory is allocated for a node type variable and a pointer is returned which we capture in the variable ‘newNode’. After the user input the program checks if the list is empty which we come to know if the ‘rootNode’, i.e., root node of the linked list is initialised as yet or not. If the root node is not yet initialised for our list, we make the ‘rootNode’ pointer to point to the ‘newNode’ we just created. Else, we traverse through the list. Starting from the root node, we hold the position in a new pointer, ‘currentNode’. Since the last node’s ‘next’ won’t point to any node, thus we use currentNode->next != NULL for that. Till so is the case, we keep on assigning the address of the next node in sequence to the pointer ‘currentNode’. So as and when we encounter the last node in the list, we come out of the loop. The pointer ‘currentNode’ now holds the address to the last node in the list. So we define the ‘next’ for this last node of ours as the newNode we just created. Now the next of newNode is set to NULL, hence the newNode is added at the end of the list.

node* findNode(int SearchKey, node* rootNode)
{
    if (rootNode == NULL)
    {
        std::cout<<std::endl<<"\aList Empty\a";
    }
    else
    {
        node* currentNode = rootNode;
        while (currentNode)
        {
            if(SearchKey == currentNode -> data)
            {
                return currentNode;
            }
            currentNode = currentNode -> next;
        }
    }
    return NULL;
}
->
This function is usd to find the address of the the node which contains the value that we want to search. This function is not available for the user as a direct functionality, but instead, is used internally by other functions which I would explain shortly. Observe the function's signature. You would see we have 2 arguments passed to this function. The first one, 'searchKey', holds the value that the user is looking for. The second argument, 'rootNode', is used to hold the address of the starting node of the list, just like the other functions.
We first check if the list is empty. To achieve that, we look at the address held by the 'rootNode' variable. If it is 'NULL', then our list is empty as yet. Otherwise, we traverse through the list starting from the root node until we find a node where the pointer 'next' holds NULL. While we are traversing through the list, if we encounter the data that we're looking for, we end the search and return the address of the node where hit the sucessful search.
This means, our function returns the first successful search back. If the element is not found on the list, the function returns NULL.



void addAfter(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL, *tempNode = NULL, *newNode = new node;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter the Value to add: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        tempNode = searchNode -> next;
        searchNode -> next = newNode;
        newNode -> next = tempNode;
        newNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}
->


This is the function that is used to add a node after the value that the user inputs. The function expects root node's address as the agument, which gets stored in the 'rootNode' variable.
The function prompts the user to enter the value he's looking for and the data to be added after that value. Once the program gets the user inputs, it calls the findNode function to lookup the value in the Linked List. Once we get the address of the node where the value matches, the current next node of this node is stored in a temp node ('tempNode' variable). A new node ('newNode' variable) is brought up, and the node which we found from our call to 'findNode' function, starts pointing to this new node as it's next node. 'newNode' starts to point to tempNode in it's next pointer, and stores the value user wanted to insert in data variable.
If the value was not found in the list, then the function displays Value not found and returns.





void addBefore(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL, *newNode = new node;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter the Value to add: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        newNode -> data = searchNode -> data;
        newNode -> next = searchNode -> next;
        searchNode -> next = newNode;
        searchNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}
->

This function is used to insert the new value before the element searched by the user. There are two ways in which this part can be implemented. One is to find the element, and the insert a new node before that. The other way is to add a new node after the searched node, copy the contents of searched node to this new node, and replacevalue of searched node with new value. Although, former is a bteer approach, our implementation uses the latter. I have gone with the second approach so that I could reuse search operation from findNode function.
So what are we doing here? We find the node which has the data the user is looking for. Then we push a new node after that one, and copy the contents of searched node to the new node(newNode -> data = searchNode -> data and newNode -> next = searchNode -> next). Then we replace the contents of original node with new values. In essence, we get the new value inserted before the searched value.
Again, if the value is not found, the user is prompted with 'Value not found' message.

void replaceValue(node* rootNode)
{
    int searchKey, newData;
    node *searchNode = NULL;
    std::cout<<"Enter the Value to find: ";
    std::cin>>searchKey;
    std::cout<<"Enter new Value: ";
    std::cin>>newData;
    searchNode = findNode(searchKey, rootNode);
    if (searchNode != NULL)
    {
        searchNode -> data = newData;
    }
    else
    {
        std::cout<<"Value Not Found!";
    }
}
->
This function is used to replace the first occurence of the value that the user searches in the list, with a value that the user inputs. Both search and new values are taken from the user as inputs. The function then calls findNode function to get the address of the nodw where the search value resides. Then the new value replaces the data already sitting there. If the value is not present in the list, a message is shown to the user to indicate the same.

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}
->

This function is used to display the list. The functions accepts the address of the root node as the argument. It then starts traversing through the list from root node, until it finds a node which points to NULL as the next element, indicating the end of list. While traversing through, the function displays the values held in each node on the screen separated by '->'

do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)













Download Source Code



Sunday, November 09, 2014

Implementing Reversal& Merging Operations on Linked List - Data Structures - C++ Program (Procedural)

Problem Question


To implement Linked Lists and perform reversal of list and union of lists

Explanation of Problem


In this program we would be implementing a Linked List. Make sure you have a strong understanding of pointers to understand Linked Lists. A linked list is a basic data structure that is used in dynamic memory allocation applications. It comprises of ‘nodes’ which are linked together to form a sequence of nodes called Linked List. The linkage is done using memory addresses of adjacent nodes (next node in singly linked list, and both next & previous nodes in doubly linked list).



In this program we use a struct to implement the node of our linked list. We will implement addition function to get some data in linked list before we can perform reversal/union on it. Adding a new node to the list means, creating a new node structure, allocating memory to it and linking it to the list.

Code


#include<iostream>

/**@Title: LinkedList v1.4.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-11-2014*
*/

struct node
{
  int data;
  node* next;
};

void addAtLast(node** rootNode);
void reverseList(node** rootNode);
void unionOfLists(node** rootOfListA, node** rootOfListB);
void displayList(node* rootNode);

int main()
{
  int choice;
  node *startOtherList = NULL, *startList = NULL;
  std::cout << "Welcome to LinkedList v1.4" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Reverse the List" <<
         std::endl << "3 : Merge 2 lists" <<
         std::endl << "4 : Display List" <<
         std::endl << "5 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
      std::cout << "Which list would you like to add to?(1/2): ";
      std::cin >> choice;
      switch(choice)
      {
      case 1:
        addAtLast(&startList);
        break;
      case 2:
        addAtLast(&startOtherList);
        break;
      default:
        std::cout << std::endl << "!!!Wrong Choice! Please enter 1 or 2!!!" << std::endl;
        choice = 1;
        break;
      }
      break;
    case 2:
      std::cout << "Which list would you like to reverse?(1/2): ";
      std::cin >> choice;
      switch(choice)
      {
      case 1:
        reverseList(&startList);
        break;
      case 2:
        reverseList(&startOtherList);
        break;
      default:
        std::cout << std::endl << "!!!Wrong Choice! Please enter 1 or 2!!!" << std::endl;
        choice = 2;
        break;
      }
      break;
    case 3:
      std::cout << "How would you like to perform union of the lists?" <<
           std::endl << "1. ListA->ListB" <<
           std::endl << "2. ListB->ListA" <<
           std::endl << "Your choice: ";
      std::cin >> choice;
      switch(choice)
      {
      case 1:
        unionOfLists(&startList, &startOtherList);
        break;
      case 2:
        unionOfLists(&startOtherList, &startList);
        break;
      default:
        std::cout << std::endl << "!!!Wrong Choice! Please enter 1 or 2!!!" << std::endl;
        choice = 3;
        break;
      }
      break;
    case 4:
      std::cout << "Which list would you like to display?(1/2): ";
      std::cin >> choice;
      switch(choice)
      {
      case 1:
        displayList(startList);
        break;
      case 2:
        displayList(startOtherList);
        break;
      default:
        std::cout << std::endl << "!!!Wrong Choice! Please enter 1 or 2!!!" << std::endl;
        choice = 4;
        break;
      }
      break;
    case 5:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.4"<<std::endl<<"Made by Rogue Coder"
           <<std::endl<<"Press any key to exit"<<std::endl;
      break;
    default:
      std::cout<<"\a\aWrong Choice\a\a"<<std::endl;
      break;
    }
  }
  while(choice != 5);
  std::cin.get();
  return 0;
}

void addAtLast(node** rootNode)
{
  node* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(*rootNode == NULL)
  {
    *rootNode = newNode;
  }
  else
  {

    node* currentNode = *rootNode;
    while(currentNode->next != NULL)
    {
      currentNode = currentNode->next;
    }
    currentNode->next=newNode;
  }
  newNode->next=NULL;
}

void reverseList(node** rootNode)
{
  if (*rootNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    node *previousNode = NULL, *nextNode, *currentNode = *rootNode;
    while(currentNode != NULL)
    {
      nextNode = currentNode -> next;
      currentNode -> next = previousNode;
      previousNode = currentNode;
      currentNode = nextNode;
    }
    *rootNode = previousNode;
    std::cout << std::endl << "Linked List is reversed!";
  }
}

void unionOfLists(node** rootOfListA, node** rootOfListB)
{
  if (*rootOfListA == NULL)
  {
    *rootOfListA = *rootOfListB;
  }
  else
  {
    node* currentNode = *rootOfListA;
    while (currentNode -> next != NULL)
    {
      currentNode = currentNode -> next;
    }
    currentNode -> next = *rootOfListB;
  }
  *rootOfListB = NULL;
}

void displayList(node* rootNode)
{
  node *currentNode = rootNode;
  if(currentNode == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    std::cout<<std::endl;
    while(currentNode != NULL)
    {
      std::cout<<currentNode->data<<"->";
      currentNode=currentNode->next;
    }
    std::cout<<"End of List"<<std::endl;
  }
}

Explanation of Code


#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.

struct node
{
int data;
node* next;
};
->This is where we create the struct node that is going to be the building block of our linked list. It comprises of an int ‘data’ where the user shall store the data they wish. Please note, you can use as many variables and of as many types in the struct, but be sure you handle them correctly. For simplicity we have used int type in our case. The other variable inside our node is ‘next’, which is a pointer to node. This would be used to build the linkage between the nodes of our linked list. ‘next’ is going to hold the address of the next node in the sequence.

int choice; -> This variable ‘choice’ will be used for the user’s choice in the menu driven program.




void addAtLast(node** rootNode)
{
node* newNode = new node;
std::cout<>newNode->data;
if(*rootNode == NULL)
{
*rootNode = newNode;
}
else
{
node* currentNode = *rootNode;
while(currentNode->next != NULL)
{
currentNode = currentNode->next;
}
currentNode->next=newNode;
}
newNode->next=NULL;
}
->
This function is used to add a new node at the end of our linked list. The argument stores the rootNode of the List to which we are adding to. Since this program is capable of merging two lists too, we first need 2 lists, right? The function asks for user input and the data is stored in the memory location pointed to by ‘newNode’ pointer to the new node that we are going to add to our list. The first statement of this function means, memory is allocated for a node type variable and a pointer to this memory location is returned, which we capture in the variable ‘newNode’. After the user input the program checks if the list to which we are adding to is empty, which we come to know if the ‘rootNode’, i.e., root node of the linked list is initialised as yet or not. If the root node is not yet initialised for our list, we make the ‘rootNode’ pointer to point to the ‘newNode’ we just created. Else, we traverse through the list. Starting from the root node, we hold the position in a new pointer, ‘currentNode’. Since the last node’s ‘next’ won’t point to any node, thus we use currentNode->next != NULL for that. Till so is the case, we keep on assigning the address of the next node in sequence to the pointer ‘currentNode’. So as and when we encounter the last node in the list, we come out of the loop. The pointer ‘currentNode’ now holds the address to the last node in the list. So we define the ‘next’ for this last node of ours as the newNode we just created. Now the next of newNode is set to NULL, hence the newNode is added at the end of the list.

void reverseList(node** rootNode)
{
if (*rootNode == NULL)
{
std::cout< next;
currentNode -> next = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
*rootNode = previousNode;
std::cout << std::endl << "Linked List is reversed!"; } }
-> In this function we take the argument as the root node of the list which is to be reversed. The function first checks if the list is empty, and returns a message to user if so is the case. Otherwise the reversal of list kicks off. Pointer, ‘previousNode’ is used to hold the address of the node previous to the current node. Similarly ‘nextNode’ is used to point to the location of the node next to the current node. We initialise ‘currentNode’ to be rootNode of the list to be reversed. Then as we traverse from rootNode to the end of list, we keep on storing the address of currentNode in nextNode pointer, and the currentNode’s next is made to point to previous node, thus reversing a link. Previous node is then assigned current node’s address, and current node is assigned address of next node(actual next node). Hence we have reversed a link in the list, and the currentNode pointer is pointing to the next node in original list. We traverse this way until currentNode point to NULL. The list is reversed, but the rootNode pointer is still pointing to the original first node of the list. Hence, we make it to point to the ‘previousNode’ pointer, which is the actually the last node in original list when the loop ends. Hence the list is reversed.

void displayList(node* rootNode)
{
node *currentNode = rootNode;
if(currentNode == NULL)
{
std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
}
else
{
std::cout<<std::endl;
while(currentNode != NULL)
{
std::cout<<currentNode->data<<"->";
currentNode=currentNode->next;
}
std::cout<<"End of List"<<std::endl;
}
}
->
This is the function that will be used for traversal of the linked list. We would display the elements of the list as we traverse it. The argument to the function holds the rootNode of the list which is to be displayed. In the start of the function, we have assigned a new pointer, ‘currentNode’, to point to the root node, ‘rootNode. Then, we check if the list is empty by checking if the currentNode is pointing to null. If currentNode is not pointing to NULL, we traverse the list using a while loop. We check until the currentNode points to null, we display the ‘data’ of the node pointed to by ‘currentNode’, followed by setting ‘currentNode’ to point to the next node in sequence. For better presentation, we separate each element by an arrow ‘->’ printing it after printing the data of each node. And thus we print ‘End of List’ at the end. Both these things we have added for presentation purposes only.

do{..}while() -> The program loop which encapsulates the whole program. Until the user chooses to exit the program, the control loops within this.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)








Download Source Code