singly linked list in c++

Singly Linked list in c++

Namaste, My name is Niteen Kumar and I am here to write a blog on the topic of C++ Linked list. We will discuss all the important factors of the Singly Linked list in c++. We will discuss the Singly Linked list in c++,  why it is used where it is used when it is used etc.

So, first of all, what is Singly Linked list in c++.

Singly Linked list in c++

In a singly linked list, each node has two part. First part is the Data item and the second part is the address of the next node.

`Here we are going to discuss all the operation performed in Singly Linked List. First of all, you should know what is Linked List what is the node structure and how the memory we are allocating to a particular node using a malloc function. If you don’t know about the linked list so Click here Linked list to know.

So, First of all here what are the operations performed on a Singly Linked List in C++.

Operations Performed in Singly Linked List in C++

  1. Append [Add at the end]  – Append the element is nothing but insert or more clearly adding an element at the end of the list.
  2. Add a begin  – Suppose After five element insertion. At the beginning of the list add first. If you want to insert an element so that is followed by this operation.
  3. Add at after  – Add at after means at a particular node means to say in middle. How to insert after a specified node, How to insert an element.
  4. Delete the First Node.
  5. Delete Specified node.
  6. Display elements
  7. Find Length
  8. Reverse List
  9. Swap two nodes
  10. Sort Elements.

So, all these operations we can perform in Singly Linked List. We will see one by one.

singly linked list in c++

 

Now, I just want to implement the program and I want to show how in Singly Linked List execute exactly.

So header file we are included. Singly Linked List means what it’s a Dynamic memory allocation.

So, mostly we are using a malloc function because we note that a node is nothing but structure type data. How we are allocating the memory dynamically to structure type variable. So with the help of a malloc function. So, that,s why a malloc function is available in a(stdlib.h). So next main function we are writing and inside what all the operations we can perform on the Single Linked list in c++ that we can write. Here it is more clear if you want to specify to what program we are implementing here single linked list operation. Inside that main, method also the first statement we are writing that is cout<<“Single Linked List operation”;

But here it is if you write like this will execute one time already we have seen this approach in stack implementation also. Continuously we need to perform the operation. So now we have to write all these things so simply all these things we will place inside the while loop[ the condition will be one(1).

while(1)

{

cout<<“Single linked list operations”;

}

Singly Linked List in C++ Operations:-

So, what all the operation we can perform. First one is How to add a node at the end of the list. Append is the First option and the second option How to add the node, in the beginning, to add at the beginning next one the third one option is Add at After next one How to find the length simply how many nodes are present in the list that we are writing. So Four(4) option so next one How to display all the element in Single Linked list in C++. And the next one How to delete an element in the list, nothing but simply how to delete a node in the list. And Finally just how to quit from the program will be the seventh option. How to Quit from the program.

while(1)

{

cout<<“Singly Linked List Operation\n”‘;

cout<<“1. Append\n”;

cout<<“2. Add at the beginning \n”

cout<<“3. Add at after”;

cout<<“4. Length \n”;

cout<<“5.Display \n”;

cout<<“6. Delete \n”;

cout<<“7. Quit\n”;

cout<<“Enter your choice”;

cin>>ch;

}

 

So, all these operations we are performing using while loop. So why the reason continuously while loop executes until you select the option 7. Quit so, we will write the logic that executing the function. So that then it will send the control out of the program.

So here it is the first we are asking to Enter your Choice. So the user will enter. So we have to collect that information here using cin we are reading that choice we are reading address of ch.

Here it is a ch is an integer variable that we are declaring inside the main method

int ch;

So it is! ch is a local variable no problem because here we are using ch inside the main function only. If we use it in all function of then we have to declare globally but here we are not using so not any problem.

Singly Linked List in C++

Here, the while loop depends upon choice the choice is collected in the variable ch. So we need to write the switch case depends on the choice all these seven choices we have to write.

Switch Cases in Singly Linked List in C++
  • Case 1. How to add a node at the end simply we will write append. we know that after every switch case we need to write the Break statement.
  • Case 2. How to add a node at the begging simply we will write add at begging and of course the break statement.
  • Case 3. Add at After specified node
  • Case 4. Length Function and next Break statement.
  • Case 5. How to display the elements of nodes.
  • Case 6. How to delete the node.
  • Case 7. Quit from the program. We know that what is the Function we have to use. It is a pre-defined function that is exit(1); so we used.
Switch(ch)

{

case 1: append();                                                                                                            break;

case 2: add at begin();                                                                                                   break;

case 3: add at after();                                                                                                      break;

case 4: len=length();                                                                                                        break;

case 5: display();                                                                                                             break;

case 6: delete();                                                                                                             break;

case 7: exit(1);                                                                                                                break;

default: cout<<“Invalid Choice\n”;

}

Now suppose they enter other numbers then 1 to 7 then we know that which case will execute default case. Simply we are giving invalid input or you can give invalid choice or whatever you want.

So depends on the function we are calling all these things to execute simple.

So, now we are writing length function break for all the function. We have to write the logic. So first we are writing the logic.

Append Function

For append function, we are writing the logic first.  So we are performing the linked operation but how to create the nodes. First, we have to define the structure. The structure should be global. Means we are using that structure definition inside all the functions. In every Function, we are using. So that’s why above the main function we are declaring the struct node. The structure should end with the semicolon. Here it is a data integer type. One node is holding an address of another node so node type is a pointer type.

Only struct node*  and the variable is the link(struct node*link) every node in a  Singly Linked List in C++ is having two fields we know that. So what are the fields ones the data type field that is integer next one is linked field. S o that is a struct node type. It is pointing to the next node and here it is a globally we can declaring one variable struct node it’s a permanent variable so what is variable root variable. What will be the initial value of the root variable? Though we are not initializing all the global variables initializes with the default value automatically in the C++ language. What is the default value? The default value is the NULL only I don’t want to create any confusion so that’s why I am directly assigning the value NULL.

So now node is ready and root variable is also ready.

 

struct node*

{                                                                                                                                             int data;                                                                                                                               struct node*link;

};

 

First root variable is created at a particular location root is created an initial value is a NULL it contains. It is ready

Singly Linked List in C++

Singly Linked List in C++

 

How to create the node in Singly Linked Listed in C++

Now we need to create the node So, how to create the node so that is inside appended () function. Whenever they call append() function so first, we need to declare one temporary variable. It is a local variable. Because after append() function execution completion so then automatically the local variable will be deleted(struct node*temp) local variable name is the temp so temp also gets memory allocation.

Singly Linked List in C++

Singly Linked List in C++

 

Allocate Memory in Singly Linked list in c++

How to allocate the memory. So using a malloc function and here it is we are creating node so the size of the node we have to pass so it is better to depend on the size of function malloc(sizeof(structnode)) then what a malloc function will do means first it will create a node. Nothing but the memory will be created in two fields. So fields having address also is the first node creation. I will write clearly the part is the data node and last part is the link node and reference address is 2046 integer occupies 2 bytes consider. So the second one is 2048 link address. It is created the node with the help of a malloc function.

Singly Linked List in C++

Singly Linked List in C++

 

I want to store inside the temp variable.

temp=malloc(sizeof(struct node)); 

but here it is a malloc function is return type is generic pointer nothing but void pointer type. So here it is whenever we are trying to collecting to temp is struct node type. So needs type conversion

temp=(structnode*)malloc(sizeof(struct node));

 

So this creation After this creation now we need to check how to react to the information. So from the particular end user. So here it is we are asking to enter the node data

cout<<“Enter node data”;

information we are reading so it will display on the console. So we are scanning the data in the location of temp. You should specify the location. Who is pointing actually? The temp is pointing. Temp contains 2046. So it is having a temporary connection with the data field of the node.

Singly Linked List in C++

Singly Linked List in C++

connect temp to data address

And next is if you want to read this information is into the data field of the node. How to connect temp to data address. Address means location address temp to data address you have to pass. So, here it is we need to write temp to data address(temp ->data) this is a location which read the value so after reading into the next location.

Suppose node values have to give 10 just written and in next location, I want to place NULL Vale so because no other pointer is there is of now. So NULL pointer is there

Singly Linked List in C++

Singly Linked List in C++

So How to press the NULL value in the program. Into temp to link location =because temporarily pointing to the node. In the node-link field is there. In that Field store the NULL value. So, this is reading information.

(temp->link=NULL)

After reading this information so now we have to check. Where we have to connect to the node. Node is ready where we have to connect this node either to root variables or somewhere else. If a list is already having some of the elements we need to add this node at the end of the end of all the available nodes but as of now no nodes is in the list. So root should be pointing to this location how it is possible to root variable is already NULL so temp value is already NULL so temp value we are assigning to root simple. So here it is first we are checking if root equals to NULL (if(root==null) nothing but the node is not having any list. Simply here it is empty. and then we are writing in if block.

Simply the temp value we are assigning to root. Temp value we are assigning to root.

if(root==null)

{

temp=root;

}

So root value is NULL is replaced with the new value is temp value. Temp value is 2046.

singly linked list in c++
Singly Linked List in C++

Singly Linked List in C++

 

So then it starts pointing to the newly created node. That is the of course first node in the list.

Singly Linked List in C++

Singly Linked List in C++

singly linked list in c++

 

So, this is a way of inserting the first node into the linked list. Now, what about the remaining nodes for that we need to write the logic of the else block. Using else block remaining nodes we have to insert. How to insert the remaining node observe. So, first, for this logic, I am writing some of the nodes. Such types of the node we are adding. Four nodes are there.

Singly Linked List in C++

Singly Linked List in C++

singly linked list in c++

 

So one part is used to store the data and the second is used to store the address. So four nodes are ready and of course, root variable is also ready. It is holding the first node address just consider the first node address it is 1000 the 1000 will e stored into root node. So here we are writing like this it is pointing to the First node (root is pointing to the first node) and next node are 2000, 3000, and 4000. Nodes always contain data. Suppose data is 10 consider and link is next link 2000. We don’t know all these things.

I will explain all these things. Next node the data is 20 and address is 3000 and the next one is data is 30 and the address is 4000 and next one is data is 40 and no other links so we are creating NULL value. So, here it is the connections are there. So, the first node is pointing to the second node, the second node is pointing to the third node. The third node is pointing to the fourth node. So as of now, the Linked list is having four nodes.

Singly Linked List in C++

Singly Linked List in C++

 

Now we have to create the new node. So, that we have to add to the end of the list. Just consider after 4 nodes insertion they have called Append method once again. I think but they just want to add one more. So, the first execution sees, First temp variable will be created. Temps get memory allocation and inside temp variable value not stored. malloc function will be created. Next malloc function will call. It will create a node at a particular location. The node will be created suppose location is a 5000 consider.

 

Singly Linked List in C++

Singly Linked List in C++

singly linked list in c++

Next, we are asking to enter node data and we are collecting into temp to data and of course, we are collecting the node address into the temporary variable. So here temp is containing the node address. Node address is what it 50000. So temporarily it is pointing to the node. It is asking to enter the node data address of temp to data. So temp is pointing to the address 5000. In node, we are storing 50. and into next location anyway, we are storing the NULL value. Because it is the last node.

I mean one number node is not created it is a lat node we are creating. Adding at the end simply. After storing a Null value into location temp to link Now we are checking to observe if block will not execute. If block will not execute here it is the root equals to NULL now check is the root value is the NULL value. No its not a NULL value. It is 1000 so if the condition has failed, so Else block will execute so, in the else block how we add directly. Directly we can’t add. We should take one more variable in the else block we should take one more variable(struct node*p) just like p.

P as a local variable we are taking. P will get memory allocation. So, what value we are storing? We should travel from the first location to the last location. Who is pointing to the first location? root is pointing. So initially the root value we need to store inside the temp here it is into P first we are storing the root variable.

(P=root;)

Here it is initially the root value is 1000.

 

Singly Linked List in C++

Singly Linked List in C++

singly linked list in c++

 

Next, we are Checking if next node is there or not every time we have to check. How many times we have to check we don’t know. So that is why we need to use a loop. So here it is we are using the loop.(while(p->link!=NULL) P to link not equals to Null means another node is there. So, this is a simple logic. P to link is equals to NULL or not we are checking. P value is pointing to the first node. P to link is not equal to NULL it is 2000 means it is connecting to another node. So we should be sent from 1000 to 2000. So very simple logic. So P to link is 2000 so that will be stored into P. That will be stored into P. Than here it is 1000 to link value is 2000 so that will be stored.

Next one, how to move to the next location it will execute continuously as long as the condition is true. So what is the condition P to link is not equal to NULL. If it is Null than it will stop or else it will continue 2000 to link to the value is a 3000 not NULL.

Next 4000 to link is a NULL value here it is so whenever it is checking 4000 to link is NULL, NULL not equals to NULL Condition false than while loop will terminate. Finally, P is pointing to the last second node.

Singly Linked List in C++

Now very simple how to add very simple. Just to add temp variable at the end of the last one nothing but to the link. So the temp value is a 5000. 5000 will be stored into the last connected node-link location. So, 5000 is nothing but temp after while loop execution once while loop terminated the temp value will be stored into P to link because P is pointing to 4000. Pis pointing to 4000. 5000 will be stored in the link location of P. So P to link. So then the NULL value here replace with the value that is 5000. So then the fourth node is connected to the fifth node.

This is simply how to add a node at the end of the list. So this logic Else block if Block executes the only fo the first node, for all the remaining nodes which block execute every time. Else block will execute every time.

void append()                                                                                           {                                                                                                               struct node*temp;                                                                                     temp=(structnode*)malloc(sizeof(structnode));                                       cout<<“Enter node data”;                                                                         cin>>temp->data;                                                                                     temp->link=NULL;                                                                                   if(root==NULL)                                                                                         {                                                                                                               root=temp;                                                                                               }                                                                                                              else                                                                                                          {                                                                                                                 struct node*p;                                                                                           p=root;                                                                                                    while(p->link!=NULL)                                                                              {                                                                                                                p=p->link;                                                                                                }                                                                                                                p->link=temp;                                                                                          }

 

This is how to insert a node. How to Append a node to the single linked list.

So now one operation we discussed and so many operations we need to discuss.

 

How to Find the Length in Singly Linked Listed in C++

 

How to find the length of the list. So length function always returns integer type. How many nodes are there in the list so that will be written. That is simply so that will be added to the count. So initially so globally. We are declaring one variable length. Simply(len). So initially value is a globally 0 (zero). we know that. Whenever we are calling the length function. After finding how many numbers on the list that will be added to the length variable finally. So that the length we can access everywhere. Everywhere we can access.

For example, here we are writing the code for length. So length function we are calling. Here suppose we are declaring one temporary variable because all the operation we need to perform with the help of temp variable only. And how many nodes I just want to count. So count variable locally I am declaring and that is initialized with 0 (zero). Temp gets memory allocation already. I took one list. Here it is temp gets memory allocation.

 

One more variable count will get memory allocation and what is the initial value of the count. Initial value that starts with zero. So no need to disturb the root variable in a single linked list operation. So what all the operation you want to perform that you should perform with the temp only.

 

Singly Linked Listed in C++
int length()                                                                      {                                                                                      int count=0;                                                                    struct node*temp;                                                          temp=root;                                                                      while(temp!=NULL)                                                        {                                                                                      count++;                                                                        temp=temp->link;                                                          }                                                                                      return count;                                                                  }

 

Suppose here, so we are placing the root value into the temp variable because we should start counting the nodes from the first node only. So here it is a temp value. Here it is a root value. That is 1000 consider. It is pointing to the first node. Just consider if you are finding to the first node. Just consider if you are finding the length here it is if suppose root equals to NULL that is nothing but means no nodes in the list. If some of the nodes are there how can we continue(while(temp!=NULL)) Temp not equals to NULL if it is NULL that means no nodes are present in the list directly it will return the value count value it will return(return count i).

Singly Linked Listed in C++

The count is a type of integer. So return type of length function is also an integer. How many nodes in the link list it is returning. So while temp nodes are in the link list it is returning. So while temp does not equal to NULL. Suppose if root value is NULL means no node in the list so by that time it will return the count value or else it will return the value. First, we are writing count++. The count value is increased by 1. The reason the temp value initially 1000. 1000 means already node is present. Means the count value we need to increase. Count value become one(1)

 

 

 

After counting the first node we need to send the control to the next node. How to send the control to the next node. we already discussed.

Singly Linked Listed in C++

Temp to link value that is nothing but next node address will be stored into temp. Now temp to link 1000 to link is what is 2000 that 2000 will be stored into temp variable now temp value is 2000.

Again while loop will execute as long as the condition is true the while loop executes. 2000 not equals to NULL again control move inside the count value increase and the temp is pointing to the next location. So value becomes 2 of count and location 2000 to link is 3000.

 

 

Yes, again 3000 is not equal to NULL. It is pointing to the next node. So count value will 3 and 3000 to link is not equal to NULL it’s 4000. The count is 4.

 

 

Next, finally, 4000 to link value is a NULL value. So NULL value means condition so count value will be 4 and the temp value will be NULL.

 

 

 

When the Temp value is NULL the count value is 4 why because you just how many nodes are in the list only 4 nodes are there. 4 nodes are present in the list. So count value is a 4. So finally it is returning the value 4. So whatever the value returned by this one by this function length will be collected to where the length function is called in the main function.

 

How to Display the Elements in Singly Linked Listed in C++

Now the Next how to display all the elements. Very simple here we have display function of return type void.(void display) All the operations we should perform with the help of a temporary variable. So as usual struct node*temp; Again we should start to display the elements with the root variable only initially. Initially root variable we are storing again a temp value start with a 1000 and this same logic we are using to print means to find the length of the list.

So whatever the logic we discussed the same logic we will discuss here. First, we are checking if the temp is equal to NULL(if(temp==nULL) or not why the reason suppose if no nodes in the list by that time if you ae trying to display the elements no elements in the list so directly we are giving the message “List is Empty” . Now else part in else block we display the nodes. We will display the elements with help of while loop. If the temp is not equal to NULL so directly we are displaying the information. tempo data(cout<<“temp->data”) we are printing. As long as the condition is the true the while loop will repeat. So every node. So after that temp to link value will be stored into temp.

temp=temp->link;

After pointing the first node data we need to send the control to the next node. It will check if the next node is NULL that is nothing but it reaches the end of the list then it will stop or else it will continue it will keep on executing like that.

So finally after printing them all we just send the control to next line. Two lines gaps I am going after printing the list. So we have printed the list. I think you well know now how to display the elements of the list.

Singly Linked Listed in C++

I am writing all the prototypes Append function it’s not returning anything and it is not taking anything. Next function add at after function and the same story it’s not taking anything and not returning any data and next one the length function is changed length function returning but it is not taking anything. Next one display function. Next one the delete function now we are writing the prototypes.

 

voidappend(void);                                            void addatbegin(void);                                    void addatafter(void);                                      int length(void);                                                void  display(void);                                          void delete(void);

 

Speak Your Mind

*