C++ Linked List

This post was written to demonstrate how to implement linked list in C++. So, without further ado, let us begin with a brief overview.

A linked list is a linear data structure in which each item is referred to as a node, and each node has two sections, one containing data and the other containing the address of the next node. To learn more in depth, see the "Linked List in Data Structure" post.

All of the C++ codes and programs in this post are for the singly linked list. But first, let's draw a picture of a linked list (a singly linked list). As an example of a linked list in C++, consider the following figure.

The words "Linked," "Lists," "Are," "Data," and "Structures" are the first part of the linked list nodes, which is also called the part or section that contains the data, and the other part (the second part) is the address part, which contains the address of the next node.

C++ Linked List Example Programs

In this post, I'll write and include the C++ programs below as examples of how to implement the linked list in C++. These programs assist you in practically grasping the concept of linked list in C++.

Insertion at the beginning of a list
Insertion at the end of a list
Deletion from the beginning of a list
Traversal of a list

Insertion at the beginning of a list

In this program,

The pointer start points to the beginning of the list.
Function create_new_node() takes one integer argument, allocates memory to create a new node, and returns the pointer to the new node. (return type: node *)
The function insert_at_beg() takes a node * pointer as an argument and inserts this node at the beginning of the list.
The display() function takes a node * type pointer as an argument and displays the list from this pointer to the end.

Following is the program that illustrates the insertion at the beginning of a list in C++.

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *start, *newptr, *save, *ptr;

node *create_new_node(int);
void insert_at_beg(node *);
void display(node *);

int main()
{
   start = NULL;
   int inf;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      cout << "\nCreating a new node...!";
      newptr = create_new_node(inf);
      if (newptr != NULL)
      {
         cout << "\n\nA new node was successfully created!\n";
      }
      else
      {
         cout << "\nWe're sorry...!..we're unable to create a new node...!..we're aborting!";
         return 0;
      }
      cout << "\nInserting this node at the top of the list now. \n";
      insert_at_beg(newptr);
      cout << "\nThe node was successfully inserted at the top of the list.\n";
      cout << "Now the list is:\n";
      display(start);
      cout << "\nWant to enter more nodes? (y/n): ";
      cin >> ch;
   }
   return 0;
}

node *create_new_node(int n)
{
   ptr = new node;
   ptr->info = n;
   ptr->next = NULL;
   return ptr;
}
void insert_at_beg(node *np)
{
   if (start == NULL)
   {
      start = np;
   }
   else
   {
      save = start;
      start = np;
      np->next = save;
   }
}
void display(node *np)
{
   while (np != NULL)
   {
      cout << np->info << " -> ";
      np = np->next;
   }
   cout << "!!\n";
}

Following is the initial output produced by the above program:

Now type a number, say 22, and hit the ENTER key to insert the new item at the beginning of the list. The following snapshot shows the sample output after doing so.

To continue feeding the information or items, type "y" and press the ENTER key, or type anything else to exit the program. Let me try some more inputs and show you a sample run using the screenshot below:

c++ linked list insertion at beginning of list

Insertion at the end of a list

In this program,

The start pointer points to the beginning of the list, and the rear pointer points to the last node.
Function create_new_node() takes only one parameter, allocates memory to create a new node, and returns the pointer to the new node. (return type: node *)
insert_in_end() accepts a node * pointer as an argument and inserts it at the end of the list.
display() accepts a node * type pointer as an argument and displays the list from this pointer to the end.

Consider the following program as an example of insertion at the end of a list:

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *start, *newptr, *save, *ptr, *rear;

node *create_new_node(int);
void insert_in_end(node *);
void display(node *);

int main()
{
   start = rear = NULL;
   int inf;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      cout << "\nCreating a new node...!";
      newptr = create_new_node(inf);
      if (newptr != NULL)
      {
         cout << "\n\nA new node was successfully created!\n";
      }
      else
      {
         cout << "\nWe're sorry...!..we're unable to create a new node...!..we're aborting!";
         return 0;
      }
      cout << "\nThis node is now being added to the end of the list. \n";
      insert_in_end(newptr);
      cout << "\nThe node was successfully inserted at the end of the list.\n";
      cout << "Now the list is:\n";
      display(start);
      cout << "\nWant to enter more nodes ? (y/n): ";
      cin >> ch;
   }
   return 0;
}

node *create_new_node(int n)
{
   ptr = new node;
   ptr->info = n;
   ptr->next = NULL;
   return ptr;
}

void insert_in_end(node *np)
{
   if (start == NULL)
   {
      start = rear = np;
   }
   else
   {
      rear->next = np;
      rear = np;
   }
}

void display(node *np)
{
   while (np != NULL)
   {
      cout << np->info << " -> ";
      np = np->next;
   }
   cout << "!!\n";
}

The following box shows the sample run of the above program with some user inputs of 1, 2, and 3 as three items of the linked list.

Enter information for the new node: 1

Creating a new node...!

A new node was successfully created!

This node is now being added to the end of the list.

The node was successfully inserted at the end of the list.
Now the list is:
1 -> !!

Want to enter more nodes ? (y/n): y
Enter information for the new node: 2

Creating a new node...!

A new node was successfully created!

This node is now being added to the end of the list.

The node was successfully inserted at the end of the list.
Now the list is:
1 -> 2 -> !!

Want to enter more nodes ? (y/n): y
Enter information for the new node: 3

Creating a new node...!

A new node was successfully created!

This node is now being added to the end of the list.

The node was successfully inserted at the end of the list.
Now the list is:
1 -> 2 -> 3 -> !!

Want to enter more nodes ? (y/n): n

Process returned 0 (0x0)   execution time : 12.724 s

Deletion from the beginning of a list

In this program,

The start pointer points to the beginning of the list, and the rear pointer points to the last node.
The function create_new_node() takes one integer argument, allocates memory to create a new node, and returns the pointer to the new node. (return type: node *)
The function insert_node() takes a node * type pointer as an argument and inserts this node at the end of the list.
And the function delete_node() deletes a node from the beginning of the list being pointed to by the start pointer.

Consider the following program as an example program that illustrates the deletion from the beginning of a list.

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *start, *newptr, *save, *ptr, *rear;

node *create_new_node(int);
void insert_node(node *);
void display_node(node *);
void delete_node();

int main()
{
   start = rear = NULL;
   int inf;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nWe're sorry...!..we're unable to create a new node...!..we're aborting!";
         return 0;
      }
      insert_node(newptr);
      cout << "\nWant to enter more nodes ? (y/n): ";
      cin >> ch;
   }
   do
   {
      cout << "Now the list is:\n";
      display_node(start);
      cout << "\nWant to delete the first node? (y/n): ";
      cin >> ch;
      if (ch == 'y' || ch == 'Y')
         delete_node();
   } while (ch == 'y' || ch == 'Y');

   return 0;
}

node *create_new_node(int n)
{
   ptr = new node;
   ptr->info = n;
   ptr->next = NULL;
   return ptr;
}

void insert_node(node *np)
{
   if (start == NULL)
      start = rear = np;
   else
   {
      rear->next = np;
      rear = np;
   }
}

void delete_node()
{
   if (start == NULL)
      cout << "Underflow...!!\n";
   else
   {
      ptr = start;
      start = start->next;
      delete ptr;
   }
}

void display_node(node *np)
{
   while (np != NULL)
   {
      cout << np->info << " -> ";
      np = np->next;
   }
   cout << "!!\n";
}

Let me now demonstrate a sample run of the above program with some user inputs initially to add items to the list, and then I will provide other user inputs at program runtime to delete the items from the beginning of the newly created list.

Enter information for the new node: 1

Want to enter more nodes ? (y/n): y
Enter information for the new node: 2

Want to enter more nodes ? (y/n): y
Enter information for the new node: 3

Want to enter more nodes ? (y/n): y
Enter information for the new node: 4

Want to enter more nodes ? (y/n): n
Now the list is:
1 -> 2 -> 3 -> 4 -> !!

Want to delete the first node? (y/n): y
Now the list is:
2 -> 3 -> 4 -> !!

Want to delete the first node? (y/n): y
Now the list is:
3 -> 4 -> !!

Want to delete the first node? (y/n): y
Now the list is:
4 -> !!

Want to delete the first node? (y/n): y
Now the list is:
!!

Want to delete the first node? (y/n): y
Underflow...!!
Now the list is:
!!

Want to delete the first node? (y/n): n

Process returned 0 (0x0)   execution time : 23.079 s

Traversal of a list

In this program,

The "start" pointer points to the beginning of the list, and the "rear" pointer points to the last node.
The function create_new_node() takes one parameter, allocates memory to create a new node, and returns the pointer to the new node. (return type: node *)
The function insert_node() takes a "node *" type pointer as an argument and inserts this node at the end of the list.
And the function traversal() takes a "node *" type pointer as an argument and displays the list from this pointer till the end of the list.

Consider the following program as an example.

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *start, *newptr, *save, *ptr, *rear;

node *create_new_node(int);
void insert_node(node *);
void travers(node *);

int main()
{
   start = rear = NULL;
   int inf;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nWe're sorry...!..we're unable to create a new node...!..we're aborting!";
         return 0;
      }
      insert_node(newptr);
      cout << "\nWant to enter more nodes ? (y/n): ";
      cin >> ch;
      cout << "\n";
   }
   cout << "Now the list is:\n";
   travers(start);

   return 0;
}

node *create_new_node(int n)
{
   ptr = new node;
   ptr->info = n;
   ptr->next = NULL;
   return ptr;
}

void insert_node(node *np)
{
   if (start == NULL)
      start = rear = np;
   else
   {
      rear->next = np;
      rear = np;
   }
}

void travers(node *np)
{
   while (np != NULL)
   {
      cout << np->info << " -> ";
      np = np->next;
   }
   cout << " !!\n";
}

Let me now show you a sample run of the preceding program to help you understand it practically.

Enter information for the new node: 10

Want to enter more nodes ? (y/n): y

Enter information for the new node: 20

Want to enter more nodes ? (y/n): y

Enter information for the new node: 30

Want to enter more nodes ? (y/n): n

Now the list is:
10 -> 20 -> 30 ->  !!

Process returned 0 (0x0)   execution time : 11.452 s

C++ Quiz

« Previous Tutorial Next Tutorial »