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
#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 
#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
#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

Advantages of using linked list in C++

  1. Insertion and Deletions are easier and more efficient.
  2. Efficient memory allocation i.e unlike arrays there is no need to pre-allocate memory.
  3. Many complex applications can be easily carried out with linked lists.
  4. During the 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.
  4. Data caching is not good

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java