Insert into a Linked List and iterative method to traverse a Linked List in C++

by

Our aim is to Insert into a Linked List, and traverse the linked list from the beginning until the node becomes NULL,i.e until we have gone through all the elements in the Linked list and we also intend to print each element of the Linked List while we traverse it.

Insert into a Linked List and iterative method to traverse a Linked List in C++

#include <bits/stdc++.h> 
using namespace std; 

struct node{
    int value;
    node* next;
    node(int x){
        value=x;
        next=NULL;
    }
};

void traverse(node *head){
    node *temp=head;
    while(temp!=NULL){
        cout<<temp->value<<" ";
        temp=temp->next;
    }
}

int main() 
{ 
	node *head=new node(100);
	head->next=new node(300);
	head->next->next=new node(500);
	head->next->next->next=new node(700);
	traverse(head);
	return 0;
}

Insert into a Linked List

In the main function of the Iterative method, we first create a Linked List. The linked list in our case will be 100, 300, 500, 700. We have used a parameterized constructor inside the structure to initialize the value of the linked list. Whenever we use the new keyword a new node is created with the help of the constructor. Initially, the Linked List is empty.

In the line node *head=new node(100) we create a node with value 100 and make the head pointer point to this node. Next is a self-referential pointer that contains the address of the next node in the linked list. In the line head -> next =new node(300) we basically create a new node with value 300 and the next section of the head will contain the address of the next node. In our case the address of the node with the value 300. Head->next is 300 and head->next->next(300->next) is the address of the next node of 300.

So in the line head->next->next= new node(500), the next section of 300 is made to hold the address of 500. This process continues till we insert all the values (i.e till 700). The end result of the code inside the main function is that we have inserted 100, 300, 500, 700 in the proper order.

An iterative method to traverse a linked list

In the main function, the head points to the first element of the Linked List. In our case, it is 100. In the traverse function, the return type is void because we don’t make any changes during the traversal. Hence there is no need to return anything. When we call the traverse function in the main function we pass a copy of the head pointer. So the traverse function will have its own copy of the head pointer pointing to the beginning of the linked list(100 in our case).

Also, note that any changes to the head pointer in the traverse function will not be reflected in the main function. Now we create another pointer called temp which will also point to the first element of the Linked List. We run the while loop until this temp pointer becomes NULL.

Dry run

During the first iteration, the temp will be pointing to the head. Hence 100 will be printed. When the line temp=temp->next gets executed the temp pointer will now point to the second element of the linked list. In the second iteration, 200 gets printed and the temp is made to point to the third element of the linked list(500). In the third iteration, 500 gets printed and the temp is made to point to the next element in the linked list(700). In the fourth iteration, 700 gets printed and temp=700->next is made NULL(because 700->next is NULL). Now temp becomes NULL.

The condition inside the while loop i.e while(temp!= NULL) is no longer true. Hence we come out of the while loop. Notice that we have printed all the elements of the Linked List in proper order.

The time complexity to traverse the Linked List is O(N) in our case.

Leave a Comment