C++ Linked Lists – Tutorials Art

C++ linked list is a type of linear data structures that save dynamic data. Linked lists consists of nodes. Each node in a linked list connects to the nodes next to it. The implementation of linked list is based on pointers. The below diagram shows a linked list containing 4 nodes.

Nodes are the base of linked list. The first node in the linked list is Head. The head of a linked list can help access all other nodes of it. The last node of the linked list does not point to any node and stores NULL address. Each node in a linked list consists of two parts:

Data: The first part of linked list is the data part that contains data in the form of int, char, float, double etc.
Pointer: The second part is the pointer that points to the address of the next node. The pointer connects one node to another.

The below code shows how to define a node for linked list. The code defines struct node that has two parts. An int type data variable and a pointer next.

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

Nodes are the building blocks of linked lists. After creating and understanding a node structure, programmer can easily create C++ linked lists. For example, the below code shows how to create a singly linked list.

Linked List

The following code creates and displays a linked list. The struct node creates nodes containing a data item of type int and a reference pointer. Note that the code initializes the head as NULL.

The function insert() having return type void, creates the linked list by inserting integer values as data. It takes an integer value data_val as its parameter. The next pointer points to the head. It creates a new node with a data_val and pointer pointing to head. After first iteration of insert(4) call, the linked list consists of a single node having data value 4 with its pointer pointing to NULL.

The function display() that displays the linked list has return type void. It creates a pointer ptr of node type. It starts at the head of the linked list and until the pointer points to NULL address, it keeps printing the data items of the linked list.

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *next;
};
struct node* head = NULL;
void insert(int data_val) {
   struct node* new_node = (struct node*) malloc(sizeof(struct node));
   new_node->data = data_val;
   new_node->next = head;
   head = new_node;
}
void display() {
   struct node* ptr;
   ptr = head;
   while (ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
int main() {
   insert(4);
   insert(9);
   insert(3);
   insert(5);
   insert(2);
   insert(1);
   cout<<"This is the C++ linked list: ";
   display();
   return 0;
}

The output of the above code after compilation is:

C++ Linked List Applications

C++ Linked List is an important data structure that has various programming and real life applications. Linked list can be used in following concepts of programming:

Dynamic memory allocation by creating vacant blocks of linked list.
Stack and queues implementation
Representing Graphs and Hash Tables by using linked lists to store the address of adjacent vertices
Creating directory of entities
Representation of Sparse Matrices
Performing arithmetic operations like addition, subtraction, multiplication, division on long integers
Polynomials manipulation by saving constant values in the nodes of linked lists

Other than programming, linked list has real life applications too. For example:

Linked list maintain picture gallery navigation. Image viewer keeps track of forward and previous images using linked lists.
Linked list maintain URL navigations. Previous and next web pages address is maintained in the nodes of linked lists.
Song Player uses linked list to maintain song queues to maintain previous and next songs.
Linked lists help achieve undo functionality in software systems.