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



Monday, October 27, 2014

Implementing Searching & Sorting Operations on a Linked List - Data Structures - C++ Program (Procedural)

Problem Question


To implement Linked List and perform searching and sorting on it

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 sorting/searching 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.3.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-10-2014*
*/

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

node* startList;
void addAtLast();
void searchPositions();
void searchHighlight();
void sortList();
void displayList();

int main()
{
  int choice;
  std::cout << "Welcome to LinkedList v1.3" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Search a Node (Display Positions)" <<
         std::endl << "3 : Search a Node (Highlight Nodes)" <<
         std::endl << "4 : Sort the Linked List" <<
         std::endl << "5 : Display List" <<
         std::endl << "6 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
      addAtLast();
      break;
    case 2:
      searchPositions();
      break;
    case 3:
      searchHighlight();
      break;
    case 4:
      sortList();
      break;
    case 5:
      displayList();
      break;
    case 6:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.3"<<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* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(startList == NULL)
  {
    startList = newNode;
  }
  else
  {

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

void searchPositions()
{
  if (startList == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a";
  }
  else
  {
    int elementToFind, foundAt = 1, foundFlag = 0;
    node* currentNode = startList;
    std::cout << std::endl << "Enter the element you wish to search: ";
    std::cin >> elementToFind;
    while (currentNode)
    {
      if(elementToFind == currentNode -> data)
      {
        std::cout << std::endl << elementToFind << " Found at position: " << foundAt;
        foundFlag = 1;
      }
      currentNode = currentNode -> next;
      foundAt++;
    }
    if (foundFlag != 1)
    {
      std::cout << std::endl << "Element not found!";
    }
  }
  std::cout << std::endl;
}

void searchHighlight()
{
  if (startList == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a";
  }
  else
  {
    int elementToFind, foundFlag = 0;
    node* currentNode = startList;
    char separator = 221;
    std::cout << std::endl << "Enter the element you wish to search: ";
    std::cin >> elementToFind;
    std::cout << std::endl;
    while (currentNode)
    {
      if(elementToFind == currentNode -> data)
      {
        std::cout << separator << currentNode -> data << separator << "->";
        foundFlag = 1;
      }
      else
      {
        std::cout << currentNode -> data << "->";
      }
      currentNode = currentNode -> next;
    }
    if (foundFlag != 1)
    {
      std::cout << std::endl << "Element not found!";
    }
    else
    {
      std::cout << "End of List";
    }
  }
  std::cout << std::endl;
}

void sortList()
{
  if(startList == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else
  {
    node *temporaryNode = new node();
    node *currentNode = startList;
    node *compareMe;
    while (currentNode)
    {
      compareMe = currentNode;
      while (compareMe)
      {
        if(currentNode -> data > compareMe -> data)
        {
          temporaryNode -> data = currentNode -> data;
          currentNode -> data = compareMe -> data;
          compareMe -> data = temporaryNode -> data;
        }
        compareMe = compareMe -> next;
      }
      currentNode = currentNode -> next;
    }
  }
}

void displayList()
{
  node *currentNode = startList;
  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.

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* newNode = new node;
std::cout<<std::endl<<"Enter data : ";
std::cin>>newNode->data;
if(startList == NULL)
{ startList = newNode; }
else
{
node* currentNode=startList;
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 ‘startList’, 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 ‘startList’ 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 searchPositions()
{
if (startList == NULL)
{
std::cout<<std::endl<<"\aList Empty\a";
}
else
{
int elementToFind, foundAt = 1, foundFlag = 0;
node* currentNode = startList;
std::cout << std::endl << "Enter the element you wish to search: ";
std::cin >> elementToFind;
while (currentNode)
{
if(elementToFind == currentNode -> data)
{
std::cout << std::endl << elementToFind << " Found at position: " << foundAt;
foundFlag = 1;
}
currentNode = currentNode -> next;
foundAt++;
}
if (foundFlag != 1)
{
std::cout << std::endl << "Element not found!";
}
}
std::cout << std::endl;
}
-> In this function we search and display all the positions where the element user wants to find exists. So we first check if the list is empty. Else, we ask for user input for the element to be found in the list. Then we start from the start/root node and traverse through the list. Whenever the data of the current node and the data to be found match, we display the position to the user. In such a case we set the foundFlag as ‘1’. If the search was unsuccessful, foundFlag is not set to 1. So once we are out of the loop, we check the value of foundFlag and display search unsuccessful message if foundFlag was not set to 1.

void searchHighlight()
{
if (startList == NULL)
{
std::cout<<std::endl<<"\aList Empty\a";
}
else
{
int elementToFind, foundFlag = 0;
node* currentNode = startList;
char separator = 221;
std::cout << std::endl << "Enter the element you wish to search: ";
std::cin >> elementToFind;
std::cout << std::endl;
while (currentNode)
{
if(elementToFind == currentNode -> data)
{
std::cout << separator << currentNode -> data << separator << "->";
foundFlag = 1;
}
else
{
std::cout << currentNode -> data << "->";
}
currentNode = currentNode -> next;
}
if (foundFlag != 1)
{
std::cout << std::endl << "Element not found!";
}
else
{
std::cout << "End of List";
}
}
std::cout << std::endl;
}
-> In this function we search for the element user wants to find. The list is displayed as a whole and the position where the search was successful is highlighted. So we first check if the list is empty. Else, we ask for user input for the element to be found in the list. Then we start from the start/root node and traverse through the list, displaying all the elements as we go. Whenever the data of the current node and the data to be found match, we highlight the position by printing the ‘separator’ (char type, ASCII value:221, a solid block) on either sides of the element. In such a case we set the foundFlag as ‘1’. If the search was unsuccessful, foundFlag is not set to 1. So once we are out of the loop, we check the value of foundFlag and display search unsuccessful message if foundFlag was not set to 1. Else we print ‘End of List’.

void sortList()
{
if(startList == NULL)
{
std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
}
else
{
node *temporaryNode = new node();
node *currentNode = startList;
node *compareMe;
while (currentNode)
{
compareMe = currentNode;
while (compareMe)
{
if(currentNode -> data > compareMe -> data)
{
temporaryNode -> data = currentNode -> data;
currentNode -> data = compareMe -> data;
compareMe -> data = temporaryNode -> data;
}
compareMe = compareMe -> next;
}
currentNode = currentNode -> next;
}
}
}
-> In this function we sort the elements of the list. At first we check if the list is empty. If not we enter the else block. We create a temporary node, and initialise a pointer currentNode to point to the startList. We also create another pointer ‘compareMe’. currentNode will be used to traverse through the list. compareMe will be used to compare the data of two nodes. We have implemented an exchange sort in this case. The outer while loop traverses through the list, starting from the root node, till we find the last node. The inner loop starts from the node pointed to by ‘currentNode’ and traverses till the end of the list. At each node we compare data of currentNode with compareMe. If compareMe was lesser, we exchange the data. Thus, going on till the end.

Let’s take an example list: ‘3->2->5->1’.
Iteration 1(outer loop): currentNode points at 3, and compareMe starts also at 3. Now, we compare 3 with 3, nothing happens. Then compare me points to ‘2’. Now we exchange 2 and 3. So the list becomes: ‘2->3->5->1’. Now currentNode is pointing at 2, and compareMe at 3. Then compareMe points to 5. No exchange happens. Then compareMe points to ‘1’. Now the exchange happens between ‘2’(currentNode) and ‘1’(compareMe). List becomes: ‘1->3->5->2’.
Iteration 2(outer loop): Now currentNode is pointing at ‘3’. compareMe starts from ‘3’. No exchange happens when compareMe points to ‘3’, or ‘5’. Then when comapreMe points to ‘2’, exchange happens. Thus, currentNode points at ‘2’ and compareMe at ‘3’. Now the list is: ‘1->2->5->3’.
Iteration 3(outer loop): Now currentNode is pointing at ‘5’. So compareMe starts from this ‘5’. When compareMe points at ‘3’ exchange happens. Now currentNode points to ‘3’, and compareMe to ‘5’. The list becomes: ‘1->2->3->5’.
Iteration 4(outer loop, last iteration): Now currentNode is pointing at 5, and so is compareMe. Thus, the loops come to end, and the list is sorted.

void displayList()
{
node *currentNode = startList;
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. In the start of the function, we have assigned a new pointer, ‘currentNode’, to point to the root node, ‘startList’. 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



Thursday, October 09, 2014

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

Problem Question


To implement Linked List and perform deletion operation on it

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 deletion 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. Deletion from linked list is quite simple, just orphaning the node to be deleted.

Code


#include <iostream>
/**@Title: LinkedList v1.2.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-10-2014*
*/

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

node* startList;

void deleteFromBeginning();
void deleteFromPosition();
void deleteFromLast();
void displayList();
void addAtLast();

int main()
{
  int choice;
  std::cout << "Welcome to LinkedList v1.2" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node to the list" <<
         std::endl << "2 : Delete a Node from beginning" <<
         std::endl << "3 : Delete a Node from some position" <<
         std::endl << "4 : Delete a Node from last" <<
         std::endl << "5 : Display List" <<
         std::endl << "6 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
      addAtLast();
      break;
    case 2:
      deleteFromBeginning();
      break;
    case 3:
      deleteFromPosition();
      break;
    case 4:
      deleteFromLast();
      break;
    case 5:
      displayList();
      break;
    case 6:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.2"<<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* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(startList == NULL)
  {
    startList = newNode;
  }
  else
  {

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

void deleteFromBeginning()
{
  if(startList == NULL)
  {
    std::cout << std::endl << "\aList empty!\a";
  }
  else
  {
    startList = startList -> next;
  }
}

void deleteFromPosition()
{
  char wishToDelete;
  if (!startList)
  {
    std::cout << std::endl << "\aList empty!\a" << std::endl;
    return;
  }
  else
  {
    node* currentNode = startList;
    int positionToDelete, loopCounter = 1;
    std::cout << std::endl << "Enter the position from where to delete: ";
    std::cin >> positionToDelete;
    if (positionToDelete < 1)
    {
      std::cout << "\a\aInvalid Position! Do you wish to delete from beginning of the list?(y for yes): ";
      std::cin >> wishToDelete;
      if (wishToDelete == 'y')
      {
        deleteFromBeginning();
        return;
      }
    }
    else
    {
      while(currentNode)
      {
        currentNode = currentNode -> next;
        loopCounter++;
      }
      if (positionToDelete >= loopCounter)
      {
        std::cout << "\a\aLast node encountered. The position you wish does not exist on the list yet."
             << std::endl << "Do you wish to delete from the end of list?(y for yes): ";
        std::cin >> wishToDelete;
        if (wishToDelete == 'y')
        {
          deleteFromLast();
          return;
        }
      }
      else
      {
        currentNode = startList;
        for (loopCounter = 1; loopCounter < positionToDelete - 1; loopCounter++)
        {
          currentNode = currentNode -> next;
        }
        currentNode -> next = currentNode -> next -> next;
        return;
      }
    }
  }
  std::cout << "\aNo node deleted...\a";
}

void deleteFromLast()
{
  if (startList == NULL)
  {
    std::cout << std::endl << "\aList empty!\a";
  }
  else if (startList -> next == NULL)
  {
    startList = NULL;
  }
  else
  {
    node* currentNode = startList;
    while(currentNode -> next -> next != NULL)
    {
      currentNode = currentNode -> next;
    }
    currentNode->next=NULL;
  }
}

void displayList()
{
  node *currentNode = startList;
  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.

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* newNode = new node;
std::cout<<std::endl<<"Enter data : ";
std::cin>>newNode->data;
if(startList == NULL)
{ startList = newNode; }
else
{
node* currentNode=startList;
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 ‘startList’, 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 ‘startList’ 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 deleteFromBeginning()
{
if(startList == NULL)
{
std::cout << std::endl << "\aList empty!\a";
}
else
{
startList = startList -> next;
}
}
-> In this function we have implemented deletion of the first node of the list, i.e., at beginning of the linked list. At first, we check if the list is empty, and we do so by checking if the pointer ‘startList’ points to NULL. If that is not the case, then we orphan the earlier root node by making the pointer startList to point to the ‘next’ of our current root node. Thus, leaving the earlier root node inaccessible, hence deleting the first node from the list.



void deleteFromPosition()
{
char wishToDelete;
if (!startList)
{
std::cout << std::endl << "\aList empty!\a" << std::endl;
return;
}
else
{
node* currentNode = startList;
int positionToDelete, loopCounter = 1;
std::cout << std::endl << "Enter the position from where to delete: ";
std::cin >> positionToDelete;
if (positionToDelete < 1)
{
std::cout << "\a\aInvalid Position! Do you wish to delete from beginning of the list?(y for yes): ";
std::cin >> wishToDelete;
if (wishToDelete == 'y')
{
deleteFromBeginning();
return;
}
}
else
{
while(currentNode)
{
currentNode = currentNode -> next;
loopCounter++;
}
if (positionToDelete >= loopCounter)
{
std::cout << "\a\aLast node encountered. The position you wish does not exist on the list yet."
<< std::endl << "Do you wish to delete from the end of list?(y for yes): ";
std::cin >> wishToDelete;
if (wishToDelete == 'y')
{
deleteFromLast();
return;
}
}
else
{
currentNode = startList;
for (loopCounter = 1; loopCounter < positionToDelete - 1; loopCounter++)
{
currentNode = currentNode -> next;
}
currentNode -> next = currentNode -> next -> next;
return;
}
}
}
std::cout << "\aNo node deleted...\a";
}
-> In this function we have implemented deletion of that node of the list which the user wishes to delete based on the position. At first, we check if the list is empty, and we do so by checking if the pointer ‘startList’ points to NULL. If that is the case, we return. The significance of this return statement will be discussed a little later.

If that is not the case, the program asks for user’s input of the position where the node is to be deleted. If this position is less than ‘1’ that means an invalid position has been entered by the user. Thus the program asks if the user would wish to delete the node at the beginning of the list, instead. If the user wishes so, ‘deleteFromBeginning’ is called followed by a return statement. The significance of this return statement is similar to that of earlier, and will be discussed a little later. If the user does not wish to, the control flows to the end of the function displaying to the user the message, “No node deleted”.

If the position was greater than equal to 1, the function counts the number of nodes in the list. Then the position entered by the user is examined again. If this is greater than the number of nodes in the list, a message is displayed to the user asking if they wish to delete at the end of list instead. If the user wishes so, function, ‘deleteFromLast’ is called followed by a return statement. The significance of this return statement is similar to that of earlier, and will be discussed a little later. If the user does not wish to, the control flows to the end of the function displaying to the user the message, “No node deleted”.

If the position entered by user was alright, i.e., greater than or equal to 1 and less than or equal to the number of nodes, then the function starts traversing the list from start node upto the node previous to the position where the node has to be deleted. Once we reach this node, we set the ‘next’ of our current node, i.e., one node prior to the node to be deleted, to point to the ‘next’ of the node to be deleted. This means orphaning the node to be deleted.

Now the return statements are necessary in this function because if they were not there, the control would flow to the statement where ‘no node deleted’ is displayed to the user. We won’t want that if the deletion was successful. Hence we used return statements at various levels in the function.



void deleteFromLast()
{
if (startList == NULL)
{
std::cout << std::endl << "\aList empty!\a";
}
else if (startList -> next == NULL)
{
startList = NULL;
}
else
{
node* currentNode = startList;
while(currentNode -> next -> next != NULL)
{
currentNode = currentNode -> next;
}
currentNode->next=NULL;
}
}
-> In this function we have implemented deletion of the last node of the list, i.e., at end of the linked list. At first, we check if the list is empty, and we do so by checking if the pointer ‘startList’ points to NULL. If that is not the case, we check if the start node is the only node in the list. If so is the case, we delete that by making the pointer ‘startList’ to point at NULL. If that too is not the case, we start to traverse the linked list. We achieve this by making a new pointer currentNode to point to the start node of the list, and we enter a while loop. This loop would run until it encounters the case when ‘next’ of ‘next’ of ‘currentNode is NULL, which means, till currentNode points to the second last node of the list. Once we reach this point, we set this second last node to be the last node of the list, by setting its ‘next’ to point to NULL. Again as you see we achieved deletion by orphaning the node to be deleted.

void displayList()
{
node *currentNode = startList;
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. In the start of the function, we have assigned a new pointer, ‘currentNode’, to point to the root node, ‘startList’. 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



Saturday, September 27, 2014

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

Problem Question


To implement Linked List and perform addition operation on it

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. 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.1.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-09-2014*
*/

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

node* startList;

void addAtBeginning();
void addAtPosition();
void addAtLast();
void displayList();

int main()
{
  int choice;
  std::cout << "Welcome to LinkedList v1.1" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node at beginning" <<
         std::endl << "2 : Add a Node at some position" <<
         std::endl << "3 : Add a Node at last" <<
         std::endl << "4 : Display List" <<
         std::endl << "5 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
      addAtBeginning();
      break;
    case 2:
      addAtPosition();
      break;
    case 3:
      addAtLast();
      break;
    case 4:
      displayList();
      break;
    case 5:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.1"<<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 addAtBeginning()
{
  node* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(startList == NULL)
  {
    startList = newNode;
    newNode -> next = NULL;
  }
  else
  {
    newNode -> next = startList;
    startList = newNode;
  }
}

void addAtPosition()
{
  char wishToAdd;
  if (!startList)
  {
    std::cout << std::endl << "The list is empty, do you wish to add at the beginning of the list?(y for yes): ";
    std::cin >> wishToAdd;
    if (wishToAdd == 'y')
    {
      addAtBeginning();
      return;
    }
  }
  else
  {
    node* currentNode = startList;
    int positionToAddAt, loopCounter = 1;
    std::cout << std::endl << "Enter the position where to add at: ";
    std::cin >> positionToAddAt;
    if (positionToAddAt <= 1)
    {
      std::cout << "\a\aDo you wish to add at beginning of the list?(y for yes): ";
      std::cin >> wishToAdd;
      if (wishToAdd == 'y')
      {
        addAtBeginning();
        return;
      }
    }
    else
    {
      while(currentNode)
      {
        currentNode = currentNode -> next;
        loopCounter++;
      }
      if (positionToAddAt > loopCounter)
      {
        std::cout << "\a\aLast node encountered. The position you wish does not exist in the list yet."
             << std::endl << "Do you wish to enter at the end of list?(y for yes): ";
        std::cin >> wishToAdd;
        if (wishToAdd == 'y')
        {
          addAtLast();
          return;
        }
      }
      else
      {
        currentNode = startList;
        for (loopCounter = 1; loopCounter < positionToAddAt - 1; loopCounter++)
        {
          currentNode = currentNode -> next;
        }
        node* newNode = new node;
        std::cout << std::endl << "Please enter the data: ";
        std::cin >> newNode -> data;
        newNode -> next = currentNode -> next;
        currentNode -> next = newNode;
        return;
      }
    }
  }
  std::cout << "\aNo node created...\a";
}

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

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

void displayList()
{
  node *currentNode = startList;
  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.

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 addAtBeginning()
{
node* newNode = new node;
std::cout<<std::endl<<"Enter data : ";
std::cin>>newNode->data;
if(startList == NULL)
{
startList = newNode;
newNode -> next = NULL;
}
else
{
newNode -> next = startList;
startList = newNode;
}
}
-> This is the function that will be used for adding a new node at the beginning of the list. To do so, the basic logic is creating a new node and assigning it to be the start node and the next of this to point at the earlier start node. Now let’s examine how we implement this logic in our program. So we get the user’s input of the data that they wish to enter into the list. After the user input the program checks if the list is empty which we come to know if the ‘startList’, 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 ‘startList’ pointer to point to the ‘newNode’ we just created. Else, the newNode’s next is assigned as the current start node of the list. Then we assign the startList to point to the newNode. Thus, we get the new node at beginning of the list.



void addAtPosition()
{
char wishToAdd;
if (!startList)
{
std::cout << std::endl << "The list is empty, do you wish to add at the beginning of the list?(y for yes): ";
std::cin >> wishToAdd;
if (wishToAdd == 'y')
{
addAtBeginning();
return;
}
}
else
{
node* currentNode = startList;
int positionToAddAt, loopCounter = 1;
std::cout << std::endl << "Enter the position where to add at: ";
std::cin >> positionToAddAt;
if (positionToAddAt <= 1)
{
std::cout << "\a\aDo you wish to add at beginning of the list?(y for yes): ";
std::cin >> wishToAdd;
if (wishToAdd == 'y')
{
addAtBeginning();
return;
}
}
else
{
while(currentNode)
{
currentNode = currentNode -> next;
loopCounter++;
}
if (positionToAddAt > loopCounter)
{
std::cout << "\a\aLast node encountered. The position you wish does not exist in the list yet."
<< std::endl << "Do you wish to enter at the end of list?(y for yes): ";
std::cin >> wishToAdd;
if (wishToAdd == 'y')
{
addAtLast();
return;
}
}
else
{
currentNode = startList;
for (loopCounter = 1; loopCounter < positionToAddAt - 1; loopCounter++)
{
currentNode = currentNode -> next;
}
node* newNode = new node;
std::cout << std::endl << "Please enter the data: ";
std::cin >> newNode -> data;
newNode -> next = currentNode -> next;
currentNode -> next = newNode;
return;
}
}
}
std::cout << "\aNo node created...\a";
}
-> In this function we let the user decide a position in our list where they wish to add a node in the list. But since the user can enter positions like negative and those which don’t yet exist on the list, we need to handle those cases elegantly. So in our function we let the user give their choice what they wish to do in such special cases. To handle this choice of the user we declare a char type variable ‘wishToAdd’.

Now we first check if the list is empty. If so is the case, we prompt the user with a message and ask if the user would like to add a node at the beginning of the list. If the user enters ‘y’ indicating yes as their choice, we call the function addAtBeginning() and return. The return statement is necessary so that the control doesn’t fall below this level in the program. If the user enters something else, “No node created” is displayed to the user.

If the list wasn’t empty, we ask the user to enter the position where they’d wish to enter the new node. If the position is less than or equal to 1, that means the only valid position where the new node can be entered is the beginning of the list. So here too we shall prompt the user if they’d like to create a new node at beginning. If the user indicates yes, we call the function addAtBeginning(), else “No node created” is displayed to user. Please note the return statement here too has the same importance as earlier, else even if the node is created, “No node created” would be displayed.

If the user didn’t enter a position less than or equal to 1, we count the number of exisiting nodes in the list. For this we use the currentNode to store the location same as that in startList. Then we traverse through the list until we encounter a null node, i.e. End Of List. We increment the loopCounter at each iteration. Now we have the number of nodes in the list. If the position that user enters is greater than this number, that means the user wishes to enter at a position which doesn’t exist in the list yet. Thus the user prompted of the case and asked if they wish to enter at the end of the list. If the user chooses so, the control is sent to the function addAtLast(). Again, return statement has the same effect here. If the user doesn’t wish to add a new node at the end of list, then ‘No Node created’ is displayed to the user.

Now if the user entered a correct position, that means, which is not less than or equal to 1, is not greater than the number of nodes in the list, we set the currentNode to point to the start node again and we traverse through the list upto the point where the user wishes to enter in the list. Now how do we achieve this? We start from the first node, and we go 2 nodes before the node where the user wishes to enter new node. Like, if the user wants to enter the new node at position 4, we start from root node. The loop runs till loopCounter becomes from 1 to 1 less than the position where the user wishes to enter, i.e., 2 in the case we are discussing here. Since we are setting the currentNode to point to next node in each iteration, at the end of list, currentNode points to(node 3 in this case) one node before the position where the user wishes to enter the new node. Now, we create a new node and ask for user’s input for the data to be stored in this node. Then we set the ‘next’ of our new node to point to the next of the currentNode(which would be the actual 4th node in this case), i.e., the node currently at position where the user wished to enter the new node. And then, we set the currentNode’s next to point to the newNode(thus newNode is now at position 4). Again return statement has the same significance as we discussed earlier.



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

node* currentNode=startList;
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 ‘startList’, 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 ‘startList’ 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 displayList()
{
node *currentNode = startList;
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. In the start of the function, we have assigned a new pointer, ‘currentNode’, to point to the root node, ‘startList’. 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



Tuesday, September 09, 2014

Implementing a Linked List - Data Structures - C++ Program (Procedural)

Problem Question


To implement Linked List and do basic operations, add, delete, search and traversal on it

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. Adding a new node to the list means, creating a new node structure, allocating memory to it and linking it to the list. Traversal as such won’t be visible to the user, thus we have implemented a function to display the list. For simplicity of the program we have implemented only addition at end of the list, deletion of the last node from list, searching an element in the list, and displaying all elements in the list.

Code


#include <iostream>
/**@Title: LinkedListv1.0.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-09-2014*
*/

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

node* startList;

void addToList();
void displayAll();
void deleteFromList();
void findElement();

int main()
{
  int choice;
  std::cout << "Welcome to LinkedList v1.0" << std::endl << "Made by Rogue Coder" << std::endl;
  do
  {
    std::cout << std::endl << "1 : Add a Node" <<
         std::endl << "2 : Display List" <<
         std::endl << "3 : Delete a Node" <<
         std::endl << "4 : Search an element" <<
         std::endl << "5 : Exit" <<
         std::endl << "Enter your choice : ";
    std::cin>>choice;
    switch(choice)
    {
    case 1:
      addToList();
      break;
    case 2:
      displayAll();
      break;
    case 3:
      deleteFromList();
      break;
    case 4:
      findElement();
      break;
    case 5:
      std::cout<<std::endl<<"Thank you for using LinkedList v1.0"<<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 addToList()
{
  node* newNode = new node;
  std::cout<<std::endl<<"Enter data : ";
  std::cin>>newNode->data;
  if(startList == NULL)
  {
    startList = newNode;
  }
  else
  {

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

void displayAll()
{
  node *currentNode = startList;
  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;
  }
}

void deleteFromList()
{
  if(startList == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a"<<std::endl;
  }
  else if(startList -> next == NULL)
  {
    startList = NULL;
    std::cout<<"Node Deleted From End"<<std::endl;
  }
  else
  {
    node* candidateNode = startList;
    while(candidateNode->next->next != NULL)
    {
      candidateNode = candidateNode->next;
    }
    candidateNode->next = NULL;
    std::cout<<"Node Deleted"<<std::endl;
  }
}

void findElement()
{
  if (startList == NULL)
  {
    std::cout<<std::endl<<"\aList Empty\a";
  }
  else
  {
    int searchMe, foundAt = 1, foundFlag = 0;
    node* currentNode = startList;
    std::cout << std::endl << "Enter the element you wish to search: ";
    std::cin >> searchMe;
    while (currentNode)
    {
      if(searchMe == currentNode -> data)
      {
        std::cout << std::endl << searchMe << " Found at position: " << foundAt;
        foundFlag = 1;
      }
      currentNode = currentNode -> next;
      foundAt++;
    }
    if (foundFlag != 1)
    {
      std::cout << std::endl << "Element not found!";
    }
  }
  std::cout << 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.

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 addToList()
{
node* newNode = new node;
std::cout<<std::endl<<"Enter data : ";
std::cin>>newNode->data;
if(startList == NULL)
{ startList = newNode; }
else {
node* currentNode=startList;
while(currentNode->next != NULL)
{ currentNode=currentNode->next; }
currentNode->next=newNode;
}
newNode->next=NULL;

}
-> This function is used to add a new node to our linked list. It asks for user input and the data is stored in the new Node which is pointed to by the pointer, 'newNode'. The first statement of this function means, memory is allocated for a node type variable and a pointer is returned which we capture in ‘newNode’. After the user input the program checks if the list is empty which we come to know if the ‘startList’, 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 ‘startList’ 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 checking the last node. 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. We would like you to note that this function adds only at the end of the list. We will be posting a new program soon where we will discuss adding anywhere in the linked list. For simplicity we wanted to discuss only the basic functionality of the linked list in this program, hence we have kept only addition at end of list.

void displayAll()
{
node *currentNode = startList;
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. In the start of the function, we have assigned a new pointer, ‘currentNode’, to point to the root node, ‘startList’. 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.

void deleteFromList()
{
if(startList == NULL)
{ std::cout<<std::endl<<"\aList Empty\a"<<std::endl; }
else if(startList -> next == NULL)
{
startList = NULL;
std::cout<<"Node Deleted From End"<<std::endl;
}
else
{
node* candidateNode = startList;
while(candidateNode->next->next != NULL)
{
candidateNode = candidateNode->next;
}
candidateNode->next = NULL;
std::cout<<"Node Deleted"<<std::endl;
}
}
->This function implements deletion from linked list. This is achieved simply by orphaning the node to be deleted. For simplicity of the program we have only discussed deletion at the end of list in this program. We will soon post a new program where we will discuss deletion from anywhere in the list. So at first we check if the list is empty. Else, we check if the list has only one node, the root node. If so is the case, we orphan that node by setting the global pointer, ‘startList’ to point to NULL. If you set the pointer ‘startList’ to point to NULL, the whole linked list would be orphaned. So be careful when you do so and be sure when to do so. If the above two cases are not positive, we go to the next case, where we traverse the linked list from the start node using a while loop. Please note, here we run the loop till the next of next of candidateNode is NULL. We do so because backtracking in a singly linked list is not possible. If we wouldn’t do so, we will reach the last node instead of reaching the second last node. We wish to reach the second last node of the list in this case because it will be the candidate to be the new last node of the list. We delete the last node by reaching the second last node and making the next of this second last node to point to NULL instead of the last node of the list. Thus, the last node of the list is orphaned, and the second last node becomes the last of node of our list. Hence, we delete from end of list.

void findElement()
{
if (startList == NULL)
{ std::cout<<std::endl<<"\aList Empty\a"; }
else
{
int searchMe, foundAt = 1, foundFlag = 0;
node* currentNode = startList;
std::cout << std::endl << "Enter the element you wish to search: ";
std::cin >> searchMe;
while (currentNode)
{
if(searchMe == currentNode -> data)
{
std::cout << std::endl << searchMe << " Found at position: " << foundAt;
foundFlag = 1;
}
currentNode = currentNode -> next;
foundAt++;
}
if (foundFlag != 1)
{ std::cout << std::endl << "Element not found!"; }
}
std::cout << std::endl;
}
->This is the function that is used to search for an element in the list. The function first checks if the list is empty. If not, three variables are used, int searchMe, foundAt = 1, foundFlag = 0;. ‘searchMe’ is the value that is to be searched in the list. ‘foundAt’ is the location where the element exists. ‘foundFlag’ is used to check if the search was successful. The user enters the element to be searched. A while loop is used to traverse through the list. The if condition checks if the node pointed to by ‘currentNode’ has the data we are looking for. In such a case the value with the position is printed, and ‘founfFlag’ is set to 1, denoting the search was successful. Then the currentNode is set to point to its next node. ‘foundAt’ is incremented with each iteration of the loop since it keeps the track of the position currentNode points to. Out of the loop, the function checks if ‘foundFlag’ was set to 1. If not, unsuccessful search is notified to the user.

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