Data Structures in C++ : Linked List Implementation

Linked List

Data Structures in C++: linked list

Data structures in C++ have a lot of things. But I will explain in this hub about what is a linked list. A linked list is a data structure which implements efficient dynamic memory allocation. A linked list is suitable for the situations when memory utilization is of utmost importance.

Data Structures in C++ : Single Linked List Implementation

A linked list in C++ is implemented as follows:

A class is defined with member data and member functions along with a self referential pointer say next.

This next pointer by default points to NULL. A start pointer is created which holds the address for the first node. Each node’s next pointer points to the next node. And the last node’s next points to NULL.

Node: A node is an unnamed object of the class.

Unnamed object: When a pointer of a class is created, an unnamed object is created in memory. And the address of this unnamed object is stored in the pointer.

Data Structures in C: Linked List

Consider a scenario: You are speaking at a seminar and you see that there are people sitting in a row. You want to have introduction of each person. So you say “Each person will tell his name and will ask the person sitting next to him to tell his name”. In this case consider yourself as start pointer because you pointed to the first person. Each person points to the person next to him. And the last person will point to nothing means NULL.

NOW Consider this scenario: You are a programmer. A mobile company is going to organize an exhibition of its products. The company wants to get details of visitors who came to exhibition. The company asks you to make a program. You cannot predict how many visitors will come. So you decide to implement linked list. You have written a program which asks to create a visitor and if the user says yes it stores details like name, address and phone of the visitor. The program has no wastage of memory as it allocates memory for as many visitors as many visitors come to exhibition. The program uses single linked list implementation to store the data. 

Program of Single Linked List

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
class visitor
{
char name[30];
char address[50];
long phone;
public:
visitor *next;
void getdata()
{
cout<<"\nEnter Details for New visitor\n";
cout<<"\nEnter The Name\n";
gets(name);
cout<<"\nEnter The Address\n";
gets(address);
cout<<"\nEnter Phone Number";
cin>>phone;
}
void putdata()
{
cout<<"\nName:"<<name<<"\nAddress:"<<address<<"\nPhone:"<<phone;
}
};
visitor *start=NULL,*ptr=NULL;
//A start and ptr pointers are created which point to NULL  
void main()
{
clrscr();
char ans;
cout<<"\nDo you want to create a New Vistor? Type Y/y for yes\n";
cin>>ans;
while(ans=='y'||ans=='Y')
{
visitor *newvisitor=new visitor;
/* A newvisitor pointer is created in memory dynamically at runtime by using new operator. newvisitor pointer has address of an unnamed object of visitor type. */

if(start==NULL)       // In case of first visitor  
{
start=ptr=newvisitor; /* start and ptr will have the address of unnamed  
                        first object of visitor type*/

newvisitor->getdata(); /* data is input for the first unnamed object 
                          through newvisitor.*/
newvisitor->next=NULL;   // First unnamed objectâs next points to NULL
}
else   // if second visitor onwards 
{
ptr->next=newvisitor; /* the previous visitorsâs next points to the 
                         latest visitor.*/
ptr=newvisitor;      // ptr now points to the latest visitor
newvisitor->getdata(); /* data is data is input for the second onwards 
                        unnamed object through newvisitor.

newvisitor->next=NULL; /* Second onwards  unnamed objectâs next points 
                         to NULL*/
}
cout<<"\nDo you want to create a New Vistor? Type Y/y for yes\n";
cin>>ans;
}
cout<<"\nDo you want to See the Linked List? Type Y/y for yes\n";
cin>>ans;
if(ans=='y'||ans=='Y')
 {
 for(ptr=start;ptr!=NULL;ptr=ptr->next)
/* ptr is initialized with first unnamed objectâs address. It runs till it is NULL. It forwards by taking each unnamed objectâs nextâs address.*/ 
ptr->putdata(); // data is displayed for each unnamed object
 }
getch();
}

OUTPUT

Do you want to create a New Visitor? Type Y/y for yes

y

Enter Details for New visitor

Enter The Name

John

Enter The Address

12/23 Salt Lake

Enter Phone Number

12334

Do you want to create a New Vistor? Type Y/y for yes

y

Do you want to create a New Vistor? Type Y/y for yes

y

Enter Details for New visitor

Enter The Name

johny

Enter The Address

78/89 Calcutta

Enter Phone Number

8907

Do you want to create a New Vistor? Type Y/y for yes

Enter Details for New visitor

Enter The Name

tony

Enter The Address

LIg 103 Kanpur

Enter Phone Number

875436

Do you want to create a New Vistor? Type Y/y for yes

n

Do you want to See the Linked List? Type Y/y for yes

y

Name:John

Address:12/23 Salt Lake

Phone:12334

Name:johny

Address:78/89 Calcutta

Phone:8907

Name:tony

Address:LIg 103 Kanpur

Phone:875436