Linked List in C++

What is linked list in C++?

Linked List in C++ is data structures and alternative to arrays, where 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 the next node.
Linked List in C++

What is a Linked List ?

A linked list is a chain of nodes that are connected to one another using pointers. Each node in a linked list has the following two things –

  • Data: Value stored in Linked List Data Structure
  • Next Pointer: Contains the address to the next node

Comparison with Arrays

Arrays are sequential and contiguous structures. Linked lists are non-contiguous structures i.e. each node in the linked list is scattered all over memory and need not be contiguous.

This has a significant advantage as in the case of arrays we need to pre-declare the size of the array 

  1. We can not increase the size of the array on requirement once the size is defined
  2. If the declared size of the array is too large and the requirement later is lesser, the size of the array can not be reduced, thus waste of memory.

However, in the case of Linked List, we can increase/decrease the size or number of nodes in real-time.

Node of a linked list

Types of Linked List

There are three types of Linked lists majorly –

Construction of a Linked List 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;
};
class Node{
    public:
    int data;
    Node *next;
};

Operations on Linked List in C++

Insertion operations on linked list

  • Insertion at beginning
  • Insertion at end
  • Insertion in between of nodes.

Deletion operations on linked list

  • Deletion at beginning
  • Deletion at end
  • Deletion of a specific node.

Other operations on linked list

  • Reverse a linked list
  • Search an element in linked list
  • Find middle of the linked list
  • Fold a linked list
 
Linked List in C++ programming

C++ Code for Creating/Deleting from a  Linked List

We will cover the following methods –

  • Method 1: Using struct
  • Method 2: Using class but with external functions
  • Method 3: Using class and member functions
Run
#include<iostream>
using namespace std;

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

void insertFront(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
}

void deleteFront(struct Node** head){
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        cout << "Linked List Empty, nothing to delete" ; 
        return; 
    }
   // move head to next node
   *head = (*head)->next;
   cout << "Value deleted: " << temp->data << endl;
   free(temp);
 }
void display(struct Node* node){ 
   cout << "\n\n";
   // as linked list will end when Node is Null
  
   while(node!=NULL){ 
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n" << endl;
} 
int main() {
 struct Node* head = NULL;

 // Need '&' i.e. address as we need to change head
 insertFront(&head,6);
 insertFront(&head,12);
 insertFront(&head,18);
 insertFront(&head,24);
 insertFront(&head,30);

 // No '&' as head is not changed
  display(head);

  deleteFront(&head); 
  deleteFront(&head); 
  display(head);
  return 0; 
}

Output

30 24 18 12 6 

Value deleted: 30
Value deleted: 24


18 12 6
Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

void insertFront(Node** head, int data){
    
    Node* newNode = new Node();
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
}

void deleteFront(Node** head){
    Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        cout << "Linked List Empty, nothing to delete" ; 
        return; 
    }
   // move head to next node
   *head = (*head)->next;
   cout << "Value deleted: " << temp->data << endl;
   free(temp);
} 
void display(Node* node){
   cout << "\n\n"; 
  
  // as linked list will end when Node is Null 
  while(node!=NULL){
     cout << node->data << " ";
     node = node->next;
  }
 cout << "\n" << endl;
}

int main() { 
   Node* head = NULL; 
   
  // Need '&' i.e. address as we need to change head 
  insertFront(&head,6); 
  insertFront(&head,12);
  insertFront(&head,18);
  insertFront(&head,24); 
  insertFront(&head,30); 
  
  // No '&' as head is not changed
  display(head); 
  
  deleteFront(&head); 
  deleteFront(&head); 
  
  display(head); 
  return 0;
}

Output

30 24 18 12 6 

Value deleted: 30
Value deleted: 24

18 12 6
Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        void insertFront(int data);
        void deleteFront();
        void display();
};

void LinkedList::insertFront(int data){
    
    Node* newNode = new Node();
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = head;

    //re-assign head to this newNode
    head = newNode;
}

void LinkedList::deleteFront(){
    Node* temp = head;
  
    // if there are no nodes in Linked List can't delete
    if(head == NULL){
        cout << "Linked List Empty, nothing to delete" ; 
        return; 
    }
   
    // move head to next node
    head = head->next; 
    cout << "Value deleted: " << temp->data << endl; 
    free(temp); 
 }

void LinkedList::display(){ 
    cout << "\n\n"; 
    // temporary variable to traverse 
    Node* node = head; 

   // as linked list will end when Node is Null
   while(node!=NULL){ 
     cout << node->data << " ";
     node = node->next; 
   }
   cout << "\n" << endl;
}

int main()
{
   LinkedList* linked_list = new LinkedList();

   // Need '&' i.e. address as we need to change head
   linked_list->insertFront(6);
   linked_list->insertFront(12);
   linked_list->insertFront(18);
   linked_list->insertFront(24); 
   linked_list->insertFront(30); 

   // No '&' as head is not changed 
   linked_list->display(); 

   linked_list->deleteFront();
   linked_list->deleteFront();
  
   linked_list->display();
  
   return 0;
}

Output

30 24 18 12 6 

Value deleted: 30
Value deleted: 24

18 12 6