Linked List in C++

Linked list is a type linear data structure, in which  the elements are not stored at contiguous memory locations like array. Each element is linked using pointers as shown in the image:

The last element in the linked list points to NULL. Moreover, Linked list can grow or shrink in size during execution of a program. It can be made just as long as required. It does not waste memory space like array. When array is not full, it waste the memory. And more important, Linked list provide flexibility in allowing the items to be rearranged efficiently by inserting and deleting elements. In array we need to shift the elements while inserting and deleting elements.

This post is written to highlight how to code linked list in c++ , because many people know linked list concept very well but they struggle while writing code.

In linked list each element is called as node. We define node using structure 

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

In this post we write code for adding element in the list at last. First we create node with input data then We check emptiness of linked list by by checking condition  head == NULL . If list is not empty we traverse the list to find last node of the list. We find list node by checking condition traverse->next != NULL . When this condition fails, we get the last node. Once we traversed to last node, we can easily add the element at last of list as shown in fig. below.

The code for inserting element is as below:

    tmp = createNode();
    tmp->data = n;
    tmp->next = NULL;

    if(head == NULL){
        head = tmp;
    }
    else{
        traverse = head;
        while(traverse->next != NULL){
            traverse= traverse->next;
        }
        traverse->next= tmp;
        }

Full source code: 

#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};

node *head=NULL;

node *createNode(){
node *tmp;
tmp = new node;
return tmp;
}

void insertNode(){
node *tmp,*traverse;
int n;
cout<<"Enter -1 to End"<<endl;
cout<<"Enter the values to be added in List"<<endl;
cin>>n;
while( n!=-1){
    tmp = createNode();
    tmp->data = n;
    tmp->next = NULL;

    if(head == NULL){
        head = tmp;
    }
    else{
        traverse = head;
        while(traverse->next != NULL){
            traverse= traverse->next;
        }
        traverse->next= tmp;
        }
   cout<<"Enter the value to be added in the list"<<endl;
   cin>>n;

}
}
void printlist(){
node *traverse = head;
cout<<"List..\n";
while(traverse != NULL){

    cout<<traverse->data<<" ";
    traverse = traverse->next;
}
}
int main(){

  int option;
  do{
    cout<<"\n---------------Main Menu-------------------"<<endl;
    cout<<"1 :Create List"<<endl;
    cout<<"2. Print List"<<endl;
    cout<<"3. Exit"<<endl;
    cin>>option;

    switch(option){
    case 1:insertNode();
           break;
    case 2:printlist();
           break;
    }
  }while(option != 3);

}

Output: 

That's all for now!