C++ Linked List Data Structure (with examples)

- February 08, 2018
Linked list is a linear data structure. It is a list or chain of nodes where each node stores data as well as points to the next node (and previous node also for double linked list) in the list. It means that each node contains the data and also the location of the next node. Thus each node of the list is linked logically with the next node through a linkpointer. The head of a linked list is its first node. The tail of a linked list refers to the last node in the list. Last node has a Null reference. A node may contain data of any type. However, all nodes of the list contain the same type data. A simple linked list is shown in the following image.
Simple Linked List Example

Each node of the linked list has two parts:

  1. Data part: It stores the actual data. It can consist of one or more fields. These fields are known as data, information, value, cargo, or payload fields. 
  2. Next part: It stores the memory address of the next node. It is usually, known as next link or next pointer. If there is no next node, then a null value is stored in it, to mark the end of the list. 

In the above image, nodes of the linked list contain two fields: one field contains an integer value and other contains a link to the next node. The last node is linked to a terminator that indicates the end of the list.
There are two types of linked lists:

  • Singly linked list
  • Doubly linked list

What is Singly Linked List

A type of linked list in which each node contains the data of node and the address  of next node only, is called singly linked list. Sometimes, it is also simply called single linked list It does not contain the address of the previous node. It can be accessed or visited from beginning to its end (such as only in one direction). The singly linked list is also known as one-way list or one-way chain.
In singly linked list, each node consists of at least two fields. The first field contains the data. This field is called data field (more than one data fields can be used in a node to store information). The second field contains the pointer or link to the next node in the list. This field is called next link or next painter field. The next link field of the last node contains a NULL value. The singly linked list that has no node is called empty list. It has a value NULL. Following diagram shows singly linked list with two data fields and one next pointer field.
Singly linked list with two data fields

The pointer variable “Start” contains the memory address of the first node of the list. A linked list is accessed with the reference to the address of its first node. Suppose memory address of the first node is 109. The second node is created and its memory address is stored in the next-pointer member of first node. Suppose its memory address is 105. In the above diagram, 2007 and 1000 represent the memory addresses of third node and fourth node respectively. The last node of the list contains a NULL value in its next-pointer field.

Representation of Singly Linked List

The storage technique of linked list is different than linear array. The linked list uses dynamic memory allocation  i.e. it allocates memory for new list elements as needed. The elements or items of a linked list are stored in memory in scattered form but these are linked together through pointers. Each element or item of the linked list is called an object. One object may contain one or more fields. Each node of linked list contains at least two fields. One field is used to store data and the other to store address of memory location of the next object. In this way, the nodes of list are linked together in the form of a chain.

For example, in C++, a structure of a "student" for creating node is defined as:
struct student
{
   int roll_no;
   char name [5];
   student *link;
};
In the above example, two members "roll_no" and "name" are defined to Store  data values for node. The "link" is defined as a pointer to the object "student" which will be used as next-pointer. It is used to store the memory address. It contains the memory address of the next node in the chain.

In C++, the "new" operator is used to create a new node during program execution. This operator allocates memory for the specified object and returns its memory address to the pointer variable. Its general syntax is as follows:
ptr = new object_name;
ptr It represents the pointer to an object.
object_name It represents the name of object. It may be the name of a defined class or structure.
Following statements declares a pointer variable "start" to an object "student" and creates a node of "student".
      student   *start;
      start = new student;
The first statement declares the pointer type variable "start" that points to the structure type object "student". It is used to store the memory address of the first or starting object in the singly linked list. In the second statement, the "new" operator is used that creates a new node and allocates memory of the node to pointer variable  "start".
The operator "->" (hyphen and greater than sign) is used to access the data of pointer type objects. In order to store data value in field "roll_no" and "NULL" value to next-pointer, the assignment statements are:
      start -> roll_no = 12;
      start -> link = NULL;
Suppose the memory address is 10162 is assigned to pointer variable "start". The storage memory will be as following image:
Linked list storage memory adress diagram

While creating a new node, the address of the previous node is stored in a pointer variable. The memory address of newly created item is stored in the pointer field of the previous node.
The representation of singly linked list having nodes in memory is shown in the following image:
C++ Linear Linked List example diagram

The above list is a linear linked list. It does not occupy consecutive memory locations (like an array). Each element or item of the list is at a different location. These are at memory addresses 1015, 1029, 5100 and 3012. Each node has a pointer variable that holds the address of next node. The pointer of the last node does not point to any node. It contains NULL value. The whole list is accessed with reference of the pointer object that holds the starting address of the linked list.
Deleting Node
The memory allocated through "new" operator will be reserved for a node until the program is terminated. This may create many problems if the size of program is very large.

We can de-allocate the memory allocated with "new" operator and it can be re-allocated for other parts of current program or operating system. The "delete" operator is used to de-allocate memory occupied by a node. The general syntax of "delete" operator is given below:
      delete ptr;
ptr It represents the pointer variable which holds the memory address of the node you want to delete from the memory.

Linked List Example Programs


Example program 1: The following source code of the C++ program create a new linked list of a student records and print the records on the screen.
#include<iostream>
#include<string>
using namespace std;
struct std_node
{
   int roll_no;
   char name[15];
   std_node *link;
};
class std_list
{
   private:
      std_node (void)
      {
          start = NULL;
      }
      void insert (int, char []);
      void display (void);
};
void main(void)
{
   std_list obj;
   int rn, rec = 1;
   char nm[15];
   do
   {
      cout<<"Enter Record #"<<rec<<endl;
      cout<<"Enter roll number?";
      cin>>rn;
      cout<<"Enter name ?";
      cin>>nm;
      obj .insert (rn, nm);
      rec++;
   } while (rec<=5);
   cout<<endl<<"Data of the list:"<<endl;
   obj .display ();
  &nbsp return 0;
}
// member function to add new node
void std_list :: insert (int code, char [])
{
// to create first node and assign data to it
if (start == NULL)
  {
   start = new std_node;
   start -> roll_no = code;
   strcpy (start -> name, n);
   start -> link = NULL;
  }
else
  {
   current = start;
   //go to end of list
   while (current -> link;
   // create new node at end and assign data to it
   temp = new std_node;
   temp -> roll_no = code;
   strcpy (temp -> name, n);
   temp -> link = NULL;
   current -> link = temp;
  }
}
// member function to display records of students
void std_list :: display (void)
 {
   int c = 1;
   current = start;
   while (current != NULL)
   {
      cout<<"Record #"<<endl;
      cout<<Roll number:"<<current -> roll_no<<endl;
      cout<<"Name:"<<current -> name<<endl;
      current = current -> link;
      c++;
   }
 }
Example Program 2: The following program creates a linked list having 5 real values and finds largest and smallest values from list.
#include<iostream>
using namespace std;
struct node
{
   float n;
   node *link;
};
class list
{
   private:
      node *start, *current, *temp;
   public:
      list (void)
   {
      start = NULL;
   }
   void insert (float);
   void display (void);
 };
void main (void)
 {
   list obj;
   float x;
   cout<<"Enter 5 real values\n";
   for (int i = 1; i<= 5; i++)
   {
       cin>>x;
       obj .insert (x);
   }
   cout<<endl<<"Data of the list:"<<endl;
   obj .display ();
   getch();
 }
// member function to add new node
void list :: insert (float data)
 {
   // to create first node and assign data to it
   if (start == NULL)
   {
      start = new node;
      start -> n = data;
      start -> link = NULL;
   }
else
 {
   current = start;
   // go to end of list
   while (current -> link != NULL)
      current = current -> link;
   // create new node at end and assign data to it
   temp = new node;
   temp -> n = data;
   temp -> link = NULL;
   current -> link = temp;
 }
}
// member function to find largest and smallest values and to display data on screen
void list :: display (void)
 {
   float max, min;
   current = start;
   max = min = current -> n;
   while (current != NULL)
  {
      cout<<current -> n<<endl;
      if (max<current ->n) max = current -> n;
      if (min>current -> n) min = current -> n;
      current = current -> link;
   }
cout<<"\n Largest value is : "<<max<<endl;
cout<<"Smallest value is: "<<min<<endl;
 }
If you execute this program the output will be as follows:

Enter 5 real values
5.2
689.3
12.5
17.8
14.2

Data of the list:
5.2
689.29998
12.5
17.799999
14.2

Largest value is: 689.299988
Smallest value is: 5.2