Linked list in C++

A linked list is a versatile data structure. In this structure, values are linked to one another with the help of addresses.

I have written in an earlier post about how to create a linked list in C. 

C++ has a library - standard template library which has list, stack, queue etc. data structures. But if you were to implement these data structures yourself in C++, how will you implement?

If you just use new, delete, cout and cin, and then claim it is your c++ program, you are not conforming to OOPS concept. Remember you have to "keep it together". Keep all the functions and variables together - in a class.

You have to have class called linked list in which there are methods - append, delete, display, insert, find, find_last. And there will also be a data - head.

Defining node

We need a structure for all these nodes. A struct can be used for this purpose, just like C.

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

Next we need to define our class. Which has one data member - head

class linked_list
{
private:
  node * head;
public:
   linked_list();
   void append(int val);
   node* find_last();
   void display();  
   void insert_beg(int n);
};

OK. Done. Remember how we almost crashed the program because we forgot to initialize head to NULL. We don't want that happening.

We should set head to NULL. And we know that a data member can not be initialized inside class declaration. So where does initialization of head appear?

It happens in the constructor. Let us write the constructor.

linked_list::linked_list()
{
   head = NULL;
}

Now we are ready to write our append function. (I am skipping create_node function for the sake of brevity)

An append function must

1. Allocate memory for the node and populate it with data
2. If list is empty, set this as head.
3. If not, find the last node of the list
• Link the new node to last node

void linked_list::append(int val)
{
    node *newnode = new node;//allocate memory
    newnode->val = val;//fill value
    newnode->next = NULL;//next is null
    if(head==NULL)
       head = newnode;
    else
    {
       node * last = find_last( );
       if(last !=NULL)
           last->next = newnode;
    } 
}

Where is the find_last function? This function returns the address of last node of the list. This last node will be linked to new node.

node* linked_list::find_last()
{
   node *temp = head;
   while(temp && temp->next) 
     temp  = temp->next;
   return temp;
}

Now we are ready to write our display function. How many parameters does it take?

0. Zero. Because we already have head with us ;) . We just have to traverse the nodes until pointer becomes NULL.

Which pointer? head (pointer to first node)? Here is the gotcha for you. If you use head variable  while traversing, by the end of display function, head variable becomes NULL. And your list is lost.

Do not be so careless about head here. :)

void linked_list::display( )
{
    cout<<"Your list is ";
    for(node*temp=head;temp!=NULL;temp = temp->next)
    {
 cout<<temp->val<<"  "; 
    }
    cout<<endl;
} 

Let us have a look at the complete class and a driver program. There are also find_node(int) and delete_node(int) functions .

#include<iostream>
using namespace std;
struct node
{
    int val;
    struct node *next;
};
class linked_list
{
private:
  node * head;
public:
   linked_list(); 
   void append(int val);
   node* find_last();
   void display();  
   void insert_beg(int n);
   node* find_node(int n);
   node* find_previous_node(node*nd);
   bool delete_node(int n);
};
linked_list::linked_list()
{
   head = NULL;
}

node* linked_list::find_last()
{
   node *temp = head;
   while(temp && temp->next) 
     temp  = temp->next;
   return temp;
}
void linked_list::append(int val)
{
    node *newnode = new node;
    newnode->val = val;

    newnode->next = NULL; 

    if(head==NULL)
       head = newnode;
    else
    {
        node * last = find_last( );
        if(last !=NULL)
           last->next = newnode;
    } 
}
node *linked_list::find_node(int num)
{
    node *temp = head;
    while(temp!=NULL && temp->val!=num)
 temp = temp->next;
    return temp;
}
node *linked_list::find_previous_node(node*nd)
{
     node *temp = head;
     while(temp!=NULL && temp->next!=nd)
 temp = temp->next;
    return temp;
}
bool linked_list::delete_node(int num)
{
    node *delnd = find_node(num);
    if(delnd==NULL)
      return false;
    node *prevnode = find_previous_node(delnd);
    if(prevnode==NULL)
    {
      /*head does not have previous node.we are deleting first node of list*/
      head = head->next;
      delete delnd;
    }else
    {
       prevnode->next = delnd->next;
       delete delnd;
     }
    return true;
}

void linked_list::insert_beg(int val)
{
    node *newnode = new node;
    newnode->val = val;
   
    newnode->next = head;
    head = newnode;
}
void linked_list::display( )
{
    cout<<"Your list is ";
    for(node*temp=head;temp!=NULL;temp = temp->next)
    {
       cout<<temp->val<<"  "; 
    }
    cout<<endl;
} 

int main()
{
   linked_list l1;
   while(true)
   {
        int n;
        cout<<"Enter value (-1 to stop)";
        cin>>n;
        if(n==-1)
           break;
           l1.append(n);
   }
   l1.display();
   int n;
   cout<<"Enter a value to be added to the begining of the list";
   cin>>n;
   l1.insert_beg(n);
   l1.display();
   while(true)
   {
        int n;
        cout<<"Enter value to be deleted (-1 to stop)";
        cin>>n;
        if(n==-1)
           break;
        if(l1.delete_node(n))
           cout<<"Node deleted successfully";
         else
           cout<<"Could not delete the node";
         l1.display();
    }       
}
   
   

Tell me now. Don't you LOVE C++?

You can download the program from here