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
No comments:
Post a Comment
Need help?