Showing posts with label Singly Linked List. Show all posts
Showing posts with label Singly Linked List. Show all posts

Monday, March 09, 2015

Implementing Shuffle Merge Operation on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement alternate split operation on 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.

Consider we have two linked lists. With shuffle merge operation, we output one merged list, such that the elements of the list are alternatingly inserted in the result list. For example, we had lists 1->2->3 and 4->5->6, the output of shuffle merge would be 1->4->2->5->3->6.




Code


#include<iostream>

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

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

void addAtLast(node** rootNode, int userData);
void shuffleMerge(node* rootNodeFirst, node* rootNodeSecond, node **rootNodeMerge);
void displayList(node* rootNode);

int main()
{
  int choice, userInput;
  node *startListFirst = NULL, *startListSecond = NULL, *startListMerged = NULL;
  std::cout << "Welcome to LinkedList v1.12" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list 1" <<
         std::endl << "2 : Add a Node to the list 2" <<
         std::endl << "3 : Perform Shuffle Merge" <<
         std::endl << "4 : Display Lists" <<
         std::endl << "5 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        std::cout<<std::endl<<"Enter data : ";
        std::cin>>userInput;
        addAtLast(&startListFirst, userInput);
        break;
    case 2:
        std::cout<<std::endl<<"Enter data : ";
        std::cin>>userInput;
        addAtLast(&startListSecond, userInput);
        break;
    case 3:
        startListMerged = NULL;
        shuffleMerge(startListFirst, startListSecond, &startListMerged);
        std::cout<<std::endl<<"Shuffle Merged List: ";
        displayList(startListMerged);
        break;
    case 4:
        std::cout<<"List 1: ";
        displayList(startListFirst);
        std::cout<<"List 2: ";
        displayList(startListSecond);
        break;
    case 5:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.12"<<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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}

void shuffleMerge(node* rootNodeFirst, node* rootNodeSecond, node **rootNodeMerge)
{
    if (rootNodeFirst == NULL || rootNodeSecond == NULL)
    {
        std::cout<<"One of the Lists is Empty!";
        return;
    }
    node *currentNodeFirst = rootNodeFirst, *currentNodeSecond = rootNodeSecond;
    while (currentNodeFirst || currentNodeSecond)
    {
        if (currentNodeFirst)
        {
            addAtLast(rootNodeMerge, currentNodeFirst -> data);
            currentNodeFirst = currentNodeFirst -> next;
        }
        if (currentNodeSecond)
        {
            addAtLast(rootNodeMerge, currentNodeSecond -> data);
            currentNodeSecond = currentNodeSecond -> next;
        }
    }
}

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* startListFirst; node* startListSecond; -> These are the pointers, which we are going to use to point to the first node / root node / start node of the linked list, that will be input to the shuffle merge function, which 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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   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 user input which is fed as a parameter to the function, 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’. 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.


void shuffleMerge(node* rootNodeFirst, node* rootNodeSecond, node **rootNodeMerge)
{
    if (rootNodeFirst == NULL || rootNodeSecond == NULL)
    {
        std::cout<<"One of the Lists is Empty!";
        return;
    }
    node *currentNodeFirst = rootNodeFirst, *currentNodeSecond = rootNodeSecond;
    while (currentNodeFirst || currentNodeSecond)
    {
        if (currentNodeFirst)
        {
            addAtLast(rootNodeMerge, currentNodeFirst -> data);
            currentNodeFirst = currentNodeFirst -> next;
        }
        if (currentNodeSecond)
        {
            addAtLast(rootNodeMerge, currentNodeSecond -> data);
            currentNodeSecond = currentNodeSecond -> next;
        }
    }
}
->
We first check if either of our original list is empty. If so, we prompt the user about it and exit out of the function. Else we go ahead.
We traverse through the both the lists, and assign the nodes to our output list alternatingly. We start at with the rootNode of our first original list, as done in the line node *currentNodeFirst = rootNodeFirst;. If the reference is not NULL, that means we have not yet reached end of the list. We ad the value stored at this node to the first node of the output list, pointed to by rootNodeMerge. Then we do similar operation with second list and assign it's value to the next node of rootNodeMerge. We keep traversing through the lists and assign their nodes alternatingly. If we encounter end of list of one, we assign rest of the nodes of other list to output, else we keep assigning nodes in alternate manner.
At the end, when we reach end of list for both the lists, we come out of the function. We have 1 output list that contains data from both lists shuffle merged into one.

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



Friday, February 27, 2015

Implementing Alternate Split Operation on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement alternate split operation on 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.

Consider we have a linked list. With alternate split operation, we output two lists. If we number our elements in the list like 0, 1, 2, 3, 4..., then each element at even position goes to list one, and other elements to list two. For example, our original input list is 1 -> 2 -> 3 -> 4 -> 5. Output would be two lists, i.e., 1 -> 3 -> 5 and 2 -> 4.




Code


#include<iostream>

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

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

void addAtLast(node** rootNode, int userData);
void alternateSplit(node* rootNode, node** rootNodeFirst, node** rootNodeSecond);
void displayList(node* rootNode);

int main()
{
  int choice, userInput;
  node *startListFirst = NULL, *startListSecond = NULL, *startList = NULL;
  std::cout << "Welcome to LinkedList v1.11" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Perform Alternate Split" <<
         std::endl << "3 : Display Lists" <<
         std::endl << "4 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        std::cout<<std::endl<<"Enter data : ";
        std::cin>>userInput;
        addAtLast(&startList, userInput);
        break;
    case 2:
        startListFirst = NULL;
        startListSecond = NULL;
        alternateSplit(startList, &startListFirst, &startListSecond);
        break;
    case 3:
        std::cout<<"Original List: ";
        displayList(startList);
        std::cout<<"List 1: ";
        displayList(startListFirst);
        std::cout<<"List 2: ";
        displayList(startListSecond);
        break;
    case 4:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.11"<<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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}

void alternateSplit(node* rootNode, node** rootNodeFirst, node** rootNodeSecond)
{
    if (rootNode == NULL)
    {
        std::cout<<"Original List is Empty!";
        return;
    }
    node *currentNode = rootNode;
    while (currentNode)
    {
        addAtLast(rootNodeFirst, currentNode -> data);
        currentNode = currentNode -> next;
        if (currentNode)
        {
            addAtLast(rootNodeSecond, currentNode -> data);
            currentNode = currentNode -> next;
        }
    }
}

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* startListFirst; node* startListSecond; -> These are the pointers, which we are going to use to point to the first node / root node / start node of the linked list, that will be out output from the alternate split function, which 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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   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 user input which is fed as a parameter to the function, 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’. 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.


void alternateSplit(node* rootNode, node** rootNodeFirst, node** rootNodeSecond)
{
    if (rootNode == NULL)
    {
        std::cout<<"Original List is Empty!";
        return;
    }
    node *currentNode = rootNode;
    while (currentNode)
    {
        addAtLast(rootNodeFirst, currentNode -> data);
        currentNode = currentNode -> next;
        if (currentNode)
        {
            addAtLast(rootNodeSecond, currentNode -> data);
            currentNode = currentNode -> next;
        }
    }
}
->
We first check if our original list is empty. If so, we prompt the user about it and exit out of the function. Else we go ahead.
We traverse through the list, and assign the nodes to our lists alternatingly. We start at with the rootNode of our original list, as done in the line node *currentNode = rootNode;. Until we encounter NULL, representing the end of list, we traverse through the list. We then add the first node to first list by calling addToLast function, and passing the reference of rootNode of first list and the data at the current node to the call. Then we move our pointer, currentNode, to the next node. If the next node is not end of list (not NULL), then we add this node to the second list by calling addToList function. We pass the rootNode reference of second list and the data at the current node to the function call to do this, and we move the pointer, currentNode, to next node.
The approach we are using reduces the number of iterations of the loop to half the size of list, though we are traversing every node internally in the loop.
At the end we have two lists, pointed by the input reference pointers, passed as paramter 2 and parameter 3 to our function.

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



Monday, February 09, 2015

Implementing Intersection Operation on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement intersection operation on 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.

Consider we have two linked lists. Intersection means finding those unique nodes which are common to both the lists. For example, if we have two lists, 1->2->3->4 and 1->1->2->8->4->6, then the intersection is 1->2->4.




Code


#include<iostream>

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

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

void addAtLast(node** rootNode, int userData);
void intersection(node** rootNodeFirst, node** rootNodeSecond, node** rootIntersect);
void displayList(node* rootNode);
bool findNode(node* rootNode, int findData);

int main()
{
  int choice, userInput;
  node *startListFirst = NULL, *startListSecond = NULL, *intersect = NULL;
  std::cout << "Welcome to LinkedList v1.10" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list 1" <<
         std::endl << "2 : Add a Node to the list 2" <<
         std::endl << "3 : Get Intersection" <<
         std::endl << "4 : Display List" <<
         std::endl << "5 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
        std::cout<<std::endl<<"Enter data : ";
        std::cin>>userInput;
        addAtLast(&startListFirst, userInput);
        break;
    case 2:
        std::cout<<std::endl<<"Enter data : ";
        std::cin>>userInput;
        addAtLast(&startListSecond, userInput);
        break;
    case 3:
        intersect = NULL;
        intersection(&startListFirst, &startListSecond, &intersect);
        displayList(intersect);
        break;
    case 4:
        std::cout<<"List 1: ";
        displayList(startListFirst);
        std::cout<<"List 2: ";
        displayList(startListSecond);
        break;
    case 5:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.10"<<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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   if(*rootNode == NULL)
   {
      *rootNode = newNode;
   }
   else
   {
       node* currentNode = *rootNode;
       while(currentNode->next != NULL)
       {
           currentNode = currentNode->next;
       }
       currentNode -> next = newNode;
   }
   newNode -> next = NULL;
}

void intersection(node** rootNodeFirst, node** rootNodeSecond, node **rootIntersect)
{
    if (*rootNodeFirst == NULL || *rootNodeSecond == NULL)
    {
        *rootIntersect = NULL;
        return;
    }
    node *currentNode = *rootNodeFirst;
    while (currentNode)
    {
        node *thisNode = *rootNodeSecond;
        while (thisNode)
        {
            if (thisNode -> data == currentNode -> data && ! findNode(*rootIntersect, thisNode -> data))
            {
                addAtLast(rootIntersect, thisNode -> data);
            }
            thisNode = thisNode -> next;
        }
        currentNode = currentNode -> next;
    }
}

bool findNode(node* rootNode, int findData)
{
    node *currentNode = rootNode;
    while (currentNode)
    {
        if (currentNode -> data == findData)
            return true;
        currentNode = currentNode -> next;
    }

    return false;
}

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* startListFirst; node* startListSecond; -> These are the pointers, which we are going to use to point to the first node / root node / start node of the linked list, that 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, int userData)
{
   node* newNode = new node;
   newNode -> data = userData;
   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 user input which is fed as a parameter to the function, 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’. 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.

bool findNode(node* rootNode, int findData)
{
    node *currentNode = rootNode;
    while (currentNode)
    {
        if (currentNode -> data == findData)
            return true;
        currentNode = currentNode -> next;
    }

    return false;
}
->
This is a helper/utility function for our program. Though it is not necessary, we have implemented it as a function to keep the code cleaner, and modular. This is a simple function, which is used to ascertain if the value is present in a given list or not. The code traverses through the list, the rootNode pointer of which is passed to it. While traversing it looks for the value passed as the second parameter. If the value is found in the list, the function returns true, else it returns false.
void intersection(node** rootNodeFirst, node** rootNodeSecond, node **rootIntersect)
{
    if (*rootNodeFirst == NULL || *rootNodeSecond == NULL)
    {
        *rootIntersect = NULL;
        return;
    }
    node *currentNode = *rootNodeFirst;
    while (currentNode)
    {
        node *thisNode = *rootNodeSecond;
        while (thisNode)
        {
            if (thisNode -> data == currentNode -> data && ! findNode(*rootIntersect, thisNode -> data))
            {
                addAtLast(rootIntersect, thisNode -> data);
            }
            thisNode = thisNode -> next;
        }
        currentNode = currentNode -> next;
    }
}
->
This function implements the intersection operation on 2 linked lists which are passed to the function, and create a new list starting at the address passed as third argument.
We first check if either list empty. If so, we simply return, since that means there would be nothing common between the lists. Else, we traverse through the lists and seek common values between them. If such value is found, we add it to the intersection output list, provided it is not already present there. We check the latter using our helper function findNode, passing it the value we have found and the rootNode of the intersection output linked list.
The outer while loop traverses throuhg list one, and the inner loop traverses through list two, comparing each node of the lists. if (thisNode -> data == currentNode -> data && ! findNode(*rootIntersect, thisNode -> data)) statement checks if the value is present in both the lists, and is not yet fed to intersection output. The first half compares the values. The second half checks if the value is present i nthe output already or not. Since we want to keep only unique values going in, we need this second check in place.

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, January 27, 2015

Implementing Front Back Split Operation on Linked List - Data Structures - C++ Program (Procedural)





Problem Question


To implement front back split 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.

Consider we have a linked list. In this problem we want to split it into two lists. If the list has even number of nodes, then we split the list into two lists of equal length. If the list has odd number of nodes, then we split the list into two lists, the first one with one node more than the second one.




Code


#include<iostream>

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

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

void addAtLast(node** rootNode);
void frontBackSplit(node** rootNodeFront, node** rootNodeBack);
void displayList(node* rootNode);

int main()
{
  int choice;
  node *startList = NULL, *backList = NULL;
  std::cout << "Welcome to LinkedList v1.9" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Perform Front Back Split" <<
         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:
        frontBackSplit(&startList, &backList);
        break;
    case 3:
        std::cout<<"List 1: ";
        displayList(startList);
        std::cout<<"List 2: ";
        displayList(backList);
        break;
    case 4:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.9"<<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;
}

void frontBackSplit(node** rootNodeFront, node** rootNodeBack)
{
    if (*rootNodeFront == NULL)
    {
        std::cout << "List Empty!";
        return;
    }
    int length = 0;
    node* currentNode = *rootNodeFront;
    while (currentNode)
    {
        length++;
        currentNode = currentNode -> next;
    }
    currentNode = *rootNodeFront;
    for(int newLength = 1; newLength < ((length / 2) + (length % 2)); newLength++)
    {
        currentNode = currentNode -> next;
    }
    *rootNodeBack = currentNode -> next;
    currentNode -> next = NULL;
    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;
  }
}


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.



void frontBackSplit(node** rootNodeFront, node** rootNodeBack)
{
    if (*rootNodeFront == NULL)
    {
        std::cout << "List Empty!";
        return;
    }
    int length = 0;
    node* currentNode = *rootNodeFront;
    while (currentNode)
    {
        length++;
        currentNode = currentNode -> next;
    }
    currentNode = *rootNodeFront;
    for(int newLength = 1; newLength < ((length / 2) + (length % 2)); newLength++)
    {
        currentNode = currentNode -> next;
    }
    *rootNodeBack = currentNode -> next;
    currentNode -> next = NULL;
    return;
}
->
This function implements front-back split. The function takes reference pointers to starting node of first and second list as inputs. The second list originally points to NULL. Though it won't matter, since we are going to overwrite the entry in the function.
We first check if the first list is empty. We do that by checking if the value at this reference pointer(the value is also a pointer, notice 2 asterisks, denoting pointer to pointer), points to start of first node.
If the list is not empty we go ahead with the split operation. We first get the length of the list by traversing through the list. We traverse the list starting the first node until we reach the last node, incrementing the variable storing length at every point.
Once we have the length, we need to split the list. But we need to find the point at which we want to split it. As explained, we need to split into two equal halves if the length is even, else first list would contain one extra node. We achieve this with the condition newLength < ((length / 2) + (length % 2)). If the length of original list was 4, we need to lists of length 2 each. If the length was 5, we need lists of length 3 and 2. If we have length of first list with us, we simply assign the node at this position as last(make it's next NULL), and the original next of this node becomes the first node of second list.
That's exactly waht we do in the statments *rootNodeBack = currentNode -> next; and currentNode -> next = NULL;.
We thus have 2 lists from the orginal 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