Linked List in C++

A Linked List in C++ is a dynamic data structure that grows and shrinks in size when the elements are inserted or removed. In other words, memory allocated or de-allocated only when the elements are inserted or removed. Thus, it means that no memory is allocated for the list if there is no element in the list. An element can be inserted and removed in the linked list at any position.

A Linked list is a linear collection of elements called nodes, where each node consists of two parts info and a pointer pointing to the next node. The nodes of the linked list usually are not stored in contiguous memory locations. A representation of a linked list with four nodes is

The left part of each node represents information, and the other part represents a pointer containing the address of the next node in the list.

Each linked list-contains a pointer variable start which contains the address of the first node in the list. The last node of the list includes the null value in the pointer field, representing the end of the linked list.

To implement a linked list that is a collection of nodes of the same type, we use self-referential structures, a structure having a reference to itself. It can define as,

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

This declaration of structure node consists of two members, the first one is the information part, and the other one is a self-referential pointer member, which points to the next node of the list. The above Node declaration of the structure node can depicted as,

#include<conio.h>
#include <iomanip.h>
#include <iostream.h>
struct node {
 int info;
 node *next;
};
class linked_list {
 node* start;
 public:
  linked_list()
   {start = NULL;}
  void create() ;
  void display();
  ~linked_list();
};
int main() {
 clrscr();
 linked_list l1; //creating an object representing linked list
 l1.create() ;
 cout<<"linkedlist is :";
 l1.display();
 getch(); return 0;
}
void linked_list::create() {
 node* ptr;
 char ch='y';
 int x;
 while(ch='y') {
  ptr = new node; //creating a node dynamically
  cout<<"enter info. part of new node = ";
  cin>>x;
  ptr->info = x;//assign value x to info part of new node
  ptr->next = start;
  start = ptr;
  cout.flush();
  cout<<"\nwant to input more: n to quit\n";
  cin>>ch;
 }
}
void linked_list::display() {
 node *ptr = start; //temporary pointer to first node
 while(ptr != NULL) {
  cout<<ptr->info<<'\t';
  ptr=ptr->next;
 }
linked_list::~linked_list() {
 node *ptr = start;
 cout<<"destroying... linked list\n";
 while(ptr!=NULL) {
  ptr = ptr->next; //pointing to next node
  delete start; // delete first node
  start=ptr; //update start with address of second node
 }
}
Output :
Enter info part of new node = 30
want to input more ? (y/n) = y
Enter info part of new node = 20
Want to input more ? (y/n) = y
Enter info part of new node = 10
Want to input more ? (y/n) = n
linked list is : 10 20 30
Releasing memory

Explanation: In the above program, we create a class linked_list with a private data member start, a pointer of type struct node containing the address of the first node of the linked list. The class also contain public member functions create(), display() and a constructor and destructor. The create() member function creates a linked list by repeatedly inserting nodes at the beginning of the linked list until the user presses any character other than ‘y’. The member function display( ) prints the information part of all the nodes of the linked list. The statement

linked_list l1;

on execution creates an object l1 of class linked_list and constructor with no parameter called which initializes the data member start to NULL. Thus an empty linked list is created.

The statement,

l1.create();

on execution, invokes create( ) member function to insert nodes into the linked list. The statement,

ptr=new node;

In defining the member function, create() allocating memory to the new node dynamically and stores its starting address in pointer ptr. The statement,

ptr->info = x;

stores the value of x in the information part of the node pointed to by ptr. The statements

ptr->next = start;
start = ptr;

first positions the next pointer of ptr to point to start, and then the start pointer points to the newly created node. Thus, the newly inserted node becomes the starting node of the linked list. It can illustrate in the following figure that we are inserting a new node with information 10 to a linked list with 2 nodes.

The statement, l1.display(); in main( ) invokes display( ) member function, which displays the information part of every node by traversing the linked list starting from the first node to the last node. In-display( ), we have created a pointer of type node which points to the node currently being displayed. The statement,

ptr = start;

points ptr to the first node in the linked list. As the end of the linked list is indicated by NULL, the while loop tests the current value of ptr to check whether it is NULL or not. If the ptr is not NULL, then the loop displays the information part of the current node (to which ptr points) and assign ptr the address of the next node in the linked list. The loop terminates when ptr = NULL, and this way information part of all the nodes of the linked list is displayed. Finally, when object l1 goes out of scope, the destructor is called, which destroyed the linked list by explicitly deallocating memory to all the linked list nodes.

#include<conio.h>
#include <iomanip.h>
#include <iostream.h>
struct node {
 int info;
 node* next;
};
class linked_list { 
 node* start;
 node* search(int);
 public:
   linked_list()
    {start = NULL; }
   void create();
   void insert();
   void display();
   ~linked_list();
};
int main() {
  clrscr();
  linked list l1;
  l1.create() ;
  cout<<"linked list before insertion: "·
  l1.display() ;
  l1.insert();//inserting a node after given node
  cout<<"linked list after insertion: "·
  l1.display() ;
  getch(); return 0;
}
void linked_list::create() {
  node*ptr;
  char ch='y';
  while(ch='y') {
   ptr = new node;
   cout<<"enter info. part of new node:";
   cin>>ptr->info;
   ptr->next = start;
   start = ptr;
   cout.flush();
   cout<<"\nwant to input more: n to quit\n";
   cin>>ch;
 }
}
void linked_list::display() {
  node *pt=start;
  while(ptr!=NULL) {
   cout<<ptr->info<<'\t';
   ptr=ptr->next;
  }
}
linked_list::~linked_list() {
  node *pt=start;
  cout<<"destroying...linked_list \n";
  while(ptr!=NULL) {
    ptr=ptr->next;
    delete start;
    start=ptr;
  }
}
void linked_list::insert() {
  node *loc;
  int x;
  cout<<"\nEnter info after which u want to insert a node=";
  cin>>x;
  loc = search(x) ;/* finding location of node after which insertion take place */
  if (loc=NULL)
    cout<<"Location not found";
  else {
    node* ptr;
    ptr=new node; I/creating node dynamically to insert
    cout<<"Enter info of new node";
    cin>>ptr->info;
    //connect new node to linked list after 'loc'
    ptr->next=loc->next;
    loc->next=ptr;
  }
}
 node* linked_list::search(int item) {
   node* ptr;
   ptr=start;
   while(ptr!=NULL) {
    if (ptr->info=item)
      return(ptr); //location found and return
      ptr = ptr->next;
   }
   return NULL; //location not found
}
Output :
Enter info.part of new node = 30
Want to input more ? (y/n) = y
Enter info part of new node = 20
Want to input more ? (y/n) = y
Enter info part of new node = 10
Want to input more ? (y/n) = n
Linked list before insertion : 10 20 30
Enter info after which you want to insert a node = 20
Enter info of new node = 25
Linked list after insertion : 10 20 25 30
Releasing Memory

Explanation: The above program inserts a new node after a given node in the linked list. For this, we have defined a public member function insert() in the class linked_list. This class contains a private member function search() that searches the location after which a new node inserted.

After creating and displaying a linked list, the statement.

l1.insert();

in main() on execution invokes the member function insert() through object l1, which inserts a new node after a given node.

The statement cin>>x; in insert() function prompts the user to input a value equal to a node’s information after which you want to insert. The statement loc = search(x); in the definition of insert() invokes private member function search(), which searches the location of the node having information part equal to x after which a new node will be inserted. If the search is successful, this function returns the address of the matched node. Otherwise, it returns a NULL value—the returned address stored in the pointer loc in the function insert().

Now, if loc is NULL, no new node is inserted. Otherwise, we create a new code and add information to it. The new node connected with the linked list after a given node having address loc using the following statements,

ptr->next = loc->next;
loc->next = ptr;

This program is similar to the previous program except that instead of the insert() function, we have the del_node() member function, which is declared in the class’s public section and define outside the class as follows.

void linked_list :: del_node() {
 if(start == NULL) //empty linked list
  cout<<"Onderflow";
 else {
  int x;
  cout<<"\nEnter info. part of node to be deleted";
  cin>>x;
  if(start->info==x) //match occur with first node
  {
    cout<<"Deletinq first node";
    node *save=start;
    start = start->next;
    delete save; //releasing memory
  }
  else {
    node *prev,*ptr;
    prev=start;
    ptr=start->next;
    while(ptr!=NULL) {
      if(ptr->info==x) {
         prev->next = ptr->next;//deleting made
         delete ptr; //free memory of deleted node
       }
      else {
         prev=ptr;
         ptr=ptr->next;
      }
    }
  }
 }
}

The main() function from where the execution actually starts look like as shown

int main() {
 linked_list l1;
 l1.create();
 cout<<"Linked list before deleting mode";
 s1.display() ;
 l1.del_node();
 cout<<"Linked list after deleting a node:";
 l1.display();
 return 0;
}

Explanation: The above program deletes a given node from the linked list. For this, we have defined a public member function del_node() in the class Iinked_list. After creating and displaying the linked list, the statement,

l1.del_node();

in main() on execution, invokes the member function del_node() through object l1 for deleting a given node in the linked list. In the definition of the del_node( ) member function, we first check whether a linked list is empty or not. If it is empty (start = NULL), we display the underflow message and exit from the function. It linked list is not empty. We search for the location of the node to delete.

The statement, cin>>x, prompts the user to input a value equal to the node’s information that you want to delete. We first compare the information part of the first node with the inputted value x using condition if (start->info==x), and if it is TRUE, we delete the first node and release its memory as shown. If this condition becomes FALSE, we create two pointer variables prev and ptr of the node type. The ptr pointer variables find the node’s location to deleted, and the previous variable points to the node preceding ptr.

If the node to delete exists in the linked list and ptr points to this node, then the statement.

prev->next=ptr->next;

in while loop, position the next pointer of the previous node of the node to be deleted to point to this node’s successor. It can be seen in Figure, where we want to delete a node with info part 20. The next statement, delete ptr; releases the memory of this node