Linked List in C++

Linked List in C++

What is linked list in C++?

Linked linked in C++ are the enhancement of arrays that makes operations on the list more easy. However some operations may like reversing , etc. may be time taking using linked list but its many merits overcomes its demerit. Every node of the linked list is made up of two parts data and pointer.

  • Data :- It stores the data  of the node.
  • Pointer :- It stores the address of next node.

 

Why linked list?

This question that why do we need linked list when arrays are already there?  is very obvious. unlike arrays which allow random access to the elements contained within them, a linked list only allows sequential access to its elements. This sequential memory access help  the linked list to shrink and grow during run time.

Node of a linked list

Construction of in C++

This set of code will create a new empty node in a linked list which will be storing integer type of data.

struct node
{
    int data;
    struct node *next;
};
Linked List in C++ programming

C++ programming code for creating Linked List

#include <iostream>
using namespace std;

struct node 
{
    int num;                
    node *nextptr;             
}*stnode; //node constructed


void createList(int n) //function to create linked list.
{
    struct node *frntNode, *tmp;
    int num, i;
 
    stnode = (struct node *)malloc(sizeof(struct node));
    
        cout<<"Enter the data for node 1: ";
        cin>>num;
        stnode-> num = num;      
        stnode-> nextptr = NULL; //Links the address field to NULL
        tmp = stnode;
 
        for(i=2; i<=n; i++)
        {
            frntNode = (struct node *)malloc(sizeof(struct node)); 
 

            if(frntNode == NULL) //If frntnode is null no memory cannot be allotted
            {
                cout<<" Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Enter the data for node "<<i<<": "; // Entering data in nodes.
                cin>>num;
                frntNode->num = num;         
                frntNode->nextptr = NULL;    
                tmp->nextptr = frntNode;     
                tmp = tmp->nextptr;
            }
        }
    
}

void display() //function to print linked list
{
    struct node *tmp;
    if(stnode == NULL)
    {
        cout<<" No data found in the list";
    }
    else
    {
        tmp = stnode;
        while(tmp != NULL)
        {
            cout<<tmp->num<<"\t";         
            tmp = tmp->nextptr;         
        }
    }
} 
int main()
{
    int n;
		
    cout<<"Enter the number of nodes: ";
    cin>>n;
    createList(n);
    cout<<"\nLinked list data: \n";		
    display();
    return 0;
}
Output:
Enter the number of nodes: 5
Enter the data for node 1: 1
Enter the data for node 2: 2
Enter the data for node 3: 3
Enter the data for node 4: 4
Enter the data for node 5: 5

Linked list data: 
1	2	3	4	5

Advantages of using linked list in C++

  1. Insertion and Deletions are easier and efficient.
  2. Efficient memory allocation i.e no need to pre-allocate memory..
  3. Many complex applications can be easily carried out with linked lists.
  4. During run time they grow and shrink.

Disadvantages of using linked list in C++

  1. Uses more memory than arrays because of the storage used by their pointers.
  2. Reversing traversing a linked list is a complicated task.
  3. Linked lists only allow sequential access.