C++ - Linked List

A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node as shown in the below image:

The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL. Linked list can be visualized as a chain of nodes, where every node points to the next node.

Types of Linked List

The types of linked list are mentioned below:

Singly Linked List: can be traversed only in forward direction.
Doubly Linked List: can be traversed in forward and backward directions.
Circular Singly Linked List: Last element contains link to the first element as next.
Circular Doubly Linked List: Last element contains link to the first element as next and the first element contains link of the last element as previous.

Implementation of Singly Linked List

Representation:

In C++, singly linked list can be created using a class and a Node using structures as shown below:

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    }
};

Create a Singly Linked List

Let us create a simple singly linked list which contains three data nodes.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    } 
};

// test the code  
int main() {
  //create an empty LinkedList
  LinkedList MyList;

  //Add first node.
  Node* first = new Node();
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList.head = first;       

  //Add second node.
  Node* second = new Node();
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second; 

  //Add third node.
  Node* third = new Node();
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third;

  return 0;
}

Traverse a Singly Linked List

A singly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    }

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }    
};

// test the code  
int main() {
  //create an empty LinkedList
  LinkedList MyList;

  //Add first node.
  Node* first = new Node();
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList.head = first;       

  //Add second node.
  Node* second = new Node();
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second; 

  //Add third node.
  Node* third = new Node();
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third;

  //print the content of list
  MyList.PrintList();
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30