Array based list Implementation
What is Array based list?
this project contains following list of functions. Every function is called by a menu option.
C++ Project Overview:
This code below can be used by beginners as a small project or assignment during semester. It contains menu based working using 19 functions. You can add more functions in it and can extend it to any level using your own customization.
Current size basically shows that how many items are in a list, so in order to get size of list the function below will be used that will print value of ‘Current size (cs)’.
void check_size_of_list()
The function below can be used to swap any two items in a list. You have to pass the positions of items that you want to swap. This thing will give you instant result and function will not have to find the values first. It will directly go to the positions and then swap items. Suppose you want to swap items at position 2 and 4 in list so.
What is Array based list?
- It is a data structure that is used to store data in a single array.
- Also known as backing array.
- They allow you to randomly access any item in list by providing constant time access to any value in array.
- They cannot expand or shrink.
- They are not very dynamic. It means if you want to add or remove data in somewhere middle of the list you will need to shift all elements in the array either to fill the gap caused by removal of item or to make a space for inserting an item.
- If number of elements exceed the size of backing array then an expensive operations needs to be performed. The operation is to make a new array of size larger than previous array and shift all the elements of previous array in new array accordingly before making new insertions.
this project contains following list of functions. Every function is called by a menu option.
- Create list
- Delete list
- Clear list
- Display list
- add item in list
- add item at particular place
- remove item from list
- remove item from particular position
- swap items by position
- find item in list
- find item by position
- copy list
- update item
- update item by position
- check size of list
- get element
- check if list is full
- check if list is empty
C++ Project Overview:
This code below can be used by beginners as a small project or assignment during semester. It contains menu based working using 19 functions. You can add more functions in it and can extend it to any level using your own customization.
/*inclusion of header files*/
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
////////////////////////////////////////////
/*initialization of global variables and dynamic array */
/*By global variable we mean the variables that can be used anywhere in whole code*/
int total_size=0; // shows total size of list is zero
int *list=new int[total_size]; // dynamically creating array with size ‘0’
int cs=0; //shows that current size of list is zero
int cl=-1; //shows that list is not created yet, “cl=clear”
///////////////////////////////////////////
/*declaration of functions */
/*Below Is the list of functions that we will be using in our code*/
/*00*/void menu();
/*01*/void create_list();
/*02*/void delete_list();
/*03*/void clear_list();
/*04*/void display_list();
/*05*/void add_item(int);
/*06*/void add_item_by_position(int,int);
/*07*/void remove_item();
/*08*/void remove_item_by_position();
/*09*/void swapp_items(int,int);
/*10*/void swapp_items_by_position(int,int);
/*11*/int find_item(int);
/*12*/int find_item_by_pos(int);
/*13*/void copy_list();
/*14*/void update_item(int,int);
/*15*/void update_item_by_position(int,int);
/*16*/void check_size_of_list();
/*17*/int get_element_by_position(int);
/*18*/int isfull();
/*19*/int isempty();
//////////////////////////////////////////////////////////////////////////////////////
The function that is written below will work throughout the code to display a menu of various functions. You will be prompted to enter the corresponding number of function you want to use and move ahead.
//////////////////////////////////////////////////////////////////////////////////////
void menu()
{
system("pause");
system("cls");
int option;
cout<<"****welcome to list application****\n";
cout<<"press 0 to exit\n"; //
cout<<"press 1 to create list\n"; //
cout<<"press 2 to delete list\n"; //
cout<<"press 3 to clear list\n"; //
cout<<"press 4 to display list\n"; //
cout<<"press 5 to add item in list\n"; //
cout<<"press 6 to add item at particular position\n"; //
cout<<"press 7 to remove item from list\n";
cout<<"press 8 to remove item from particular position\n";
cout<<"press 9 to swap items\n";//
cout<<"press 10 to swap items by position\n";//
cout<<"press 11 to find item in list\n"; //
cout<<"press 12 to find item by position\n"; //
cout<<"press 13 to copy list\n";//
cout<<"press 14 to update item\n"; //
cout<<"press 15 to update item by position\n"; //
cout<<"press 16 to check size of list\n"; //
cout<<"press 17 to get element\n"; //
cout<<"enter 18 to check if list is full\n"; //
cout<<"enter 19 to check if list is empty\n"; //
cout<<"enter option:";
cin>>option;
///////////////////////////////////////////////////
switch(option)
{
case 0:
{
exit(0); //built in function to exit from program
}
break;
//////////////////////////////////////////////////
case 1:
{
create_list();
menu();
}
break;
/////////////////////////////////////////////////
case 2:
{
delete_list();
menu();
}
break;
////////////////////////////////////////////////
case 3:
{
clear_list();
menu();
}
break;
////////////////////////////////////////////////
case 4:
{
display_list();
menu();
}
break;
///////////////////////////////////////////////
case 5:
{
int it;
if(cl==-1)
cout<<"list is not created\n";
else
if(isfull()==1)
cout<<"list is already full\n";
else
do
{
cout<<"enter item:";
cin>>it;
if(find_item(it)==1)
cout<<"item is already in list\n";
}
while(find_item(it)==1);
add_item(it);
cout<<"item added successfully in list\n";
cs++;
}
menu();
break;
//////////////////////////////////////////////
case 6:
{
int it,pos;
if(cl==-1)
cout<<"list is not created\n";
else
do
{
cout<<"enter item:";
cin>>it;
if(find_item(it)==1)
cout<<"item is already in list\n";
}
while(find_item(it)==1);
cout<<"enter position:";
cin>>pos;
if(cl==1&&pos<cs)
{
for(int i=cs-1;i>pos-1;i--)
{
list[i+1]=list[i];
}
add_item_by_position(it,pos);
cout<<"item added successfully at pos :"<<pos<<endl;
cs++;
}
else
if(cl==1&&pos>=cs&&pos< total_size)
{
list[cs]=it;
cs++;
}
else
cout<<"position out of range\n";
}
menu();
break;
/////////////////////////////////////////////
case 7:
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
remove_item();
cout<<"item is successfully removed\n";
}
menu();
break;
////////////////////////////////////////////
case 8:
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
remove_item_by_position();
cout<<"item successfully deleted\n";
}
menu();
break;
////////////////////////////////////////////
case 9:
{
int it1,it2;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
do
{
cout<<"enter item 1: ";
cin>>it1;
if(find_item(it1)!=1)
cout<<"item is not in list\n";
}
while(find_item(it1)!=1);
do
{
cout<<"enter item 2: ";
cin>>it2;
if(find_item(it1)!=1)
cout<<"item is not in list\n";
}
while(find_item(it2)!=1);
swapp_items(it1,it2);
cout<<"items successfully swapped\n";
}
menu();
break;
///////////////////////////////////////////
case 10:
{
int pos1,pos2;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
do
{
cout<<"enter position 1:";
cin>>pos1;
}
while(pos1<0||pos1>=cs);
do
{
cout<<"enter position 2:";
cin>>pos2;
}
while(pos2<0||pos2>=cs);
swapp_items_by_position(pos1,pos2);
cout<<"items successfully swapped\n";
}
menu();
break;
////////////////////////////////////////////
case 11:
{
int it;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
{
cout<<"enter item to check its presence in list\n";
cin>>it;
find_item(it);
if(find_item(it)==1)
{
cout<<"item is present in list";
int i=0;
while(list[i]!=it)
{
i++;
}
cout<<"at position "<<i<<endl;
}
else
cout<<"item not found\n";
}
menu();
}
break;
//////////////////////////////////////////////
case 12:
{
int pos;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
{
do
{
cout<<"enter position to find its item\n";
cin>>pos;
}
while(pos<0||pos>ts);
find_item_by_pos(pos);
}
menu();
}
break;
//////////////////////////////////////////////
case 13:
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
copy_list();
cout<<"list copied successfully\n";
}
menu();
break;
/////////////////////////////////////////////
case 14:
{
int it1,it2;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
{
do
{
cout<<"enter item to be updated\n";
cin>>it1;
if(find_item(it1)!=1)
cout<<"item is not in list\n";
}
while(find_item(it1)!=1);
do
{
cout<<"enter new item to be replaced\n";
cin>>it2;
if(find_item(it2)==1)
cout<<"item is already in list\n";
}
while(find_item(it2)==1);
update_item(it1,it2);
}
}
menu();
break;
////////////////////////////////////////////
case 15:
{
int it,pos;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
{
do
{
cout<<"enter item:";
cin>>it;
if(find_item(it)==1)
cout<<"item already present\n";
}
while(find_item(it)==1);
cout<<"enter position:";
cin>>pos;
if(pos<cs)
update_item_by_position(it,pos);
else
cout<<"item at "<<pos<<" is not available to be updated\n";
}
}
menu();
break;
///////////////////////////////////////////
case 16:
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
check_size_of_list();
}
menu();
break;
//////////////////////////////////////////
case 17:
{
int a,pos;
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
do
{
cout<<"enter position to get from list:";
cin>>pos;
}
while(pos<0||pos>cs);
a=get_element_by_position(pos);
cout<<"here is your item from list :"<<a<<endl;
}
menu();
break;
//////////////////////////////////////////
case 18:
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
if(isfull()==1)
cout<<"list is full\n";
else
cout<<"list is not full\n";
}
menu();
break;
/////////////////////////////////////////
case 19:
{
if(cl==-1)
cout<<"list is not created\n";
else
if(isempty()==1)
cout<<"list is empty\n";
else
cout<<"list is not empty\n";
}
menu();
break;
/////////////////////////////////////////
default:
cout<<"invalid option\n";
menu();
break;
//////////////////////////////////////////
} //switch closed
} //funtion closed
/////////////////////////////////////////////////////////////////////////////////////////////////
/*definitions of functions*/
/*////////////////////////////////////////////////////////////////////////////////////
The function
below will be used to create a list. In this function you will have to
dynamically create a list first. As initially the total size of list was set to
zero so that user can create a list of the size of its own choice and
requirement. Total size could be any but make sure that it should be greater
than current size of list. After entering total size enter current size of list
that should be exactly the number of items you want to insert in list.
Suppose we set total_size to 10.
And current size (cs) to 5.
To avoid any
errors we have put a check while getting value from user. You’ll be prompted to
enter current size again and again if it is less than 1 or exceeds total size
of list. After checking your list will be dynamically created.
After
creation of list you will be prompted to insert items in a list. To avoid
duplication, we have put a check on each entry. Whenever you will insert item
in list, [find_item()] function will run and compare all previously inserted
items of list with newly inserted item. If it is different, it will be entered
otherwise it will prompt again and again to enter new value/item.
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
////////////////////////////////////////////////////////////////////////////////////*/
void create_list()
{
int it;
cout<<"enter total size of list:";
cin>>total_size ;
do
{
cout<<"enter current size of list:";
cin>>cs;
}
while(cs<1||cs>=ts);
int i=0;
while(i<cs)
{
cout<<"enter item:";
cin>>it;
if(find_item(it)!=1)
{
list[i]=it;
i++;
}
else
cout<<"item already present\n";
} //while closed
cl=1;
} //function closed
The function
below can be considered as a heart of the code as it will work for insertion of
any new entry in list to check for duplication. It will return 1 that means
true if new entry of item matches already existing item in list. Otherwise it
will return 0 that means false.
Working:
We will pass
any item that we want to check for duplication to this function. It will start
checking from them item present at first number of list till end of list. Each
time it will compare the item passed to it with item at particular position. It
will continue till it reaches end of list or find a duplicate item. If there is
no duplicate item and function has reached end of list, it will return 0.
int find_item(int it)
{
int i;
for(i=0;i< total_size;i++)
if(list[i]==it)
return 1;
}
The function below will randomly access any item whose position you will pass to it, and then it will return you that item.
int find_item_by_pos(int pos)
{
cout<<"item at position "<<pos<<" is "<< list[pos]<<endl;
return 1;
}
/*Suppose you pass pos = 3
This function will return you 30.
According to list.*/
The function
below will be used to display status of list whenever needed. But before
displaying it will check if list is empty? Or if list is not created yet. If
any of the two options come true, it will display the message accordingly.
Otherwise it will simply display a list.
void display_list()
{
if(cs==0)
cout<<"list is empty\n";
else
if(cl==-1)
cout<<"list is not created\n";
else
for(int i=0;i<cs;i++)
cout<<list[i]<<endl;
}
/*Output: After the listed you have created first by inserting 5 items, if you will run this function the output you will have will be like:
10
20
30
40
50
*/
/*////////////////////////////////////////////////////////////////////////////////////
The function below will simply delete the list by giving negative value to “cl”. Must note that array can never have negative value, but if you assign it this value it means that it doesn’t exist.
///////////////////////////////////////////////////////////////////////////////////*/
void delete_list()
{
if(cl==-1)
cout<<"list is not created\n";
else
cl=-1;
cout<<"list is successfully deleted\n";
}
////////////////////////////////////////////////////////////////////////////////////
/*////////////////////////////////////////////////////////////////////////////////////
The function below will clear the list i-e only remove items from the list. By doing this, list will come to its initial form. It will exist but will be empty. We have put check before clearing the list to check if list exists or not and if it exists is it already clear or not. The function will work if list exists and contains some values otherwise it will show a default message that you already set.
///////////////////////////////////////////////////////////////////////////////////*/
void clear_list()
{
if(cl==-1)
cout<<"list is not created\n";
else
if(cs==0)
cout<<"list is already empty\n";
else
cs=0;
cout<<"list is successfully cleared\n";
}
The function below will add item at unallocated location right after last item in list.
void add_item(int item)
{
list[cs]=item;
}
It will add
item to specific location in list. For eg you want to insert item at 7th
location then,
10
|
20
|
30
|
40
|
50
|
70
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
void add_item_by_position(int item,int
pos)
{
list[pos]=item;
}
This
function will return 1 if current size is equal to total size indicating list if full and there is no
more space to add more item
10
|
20
|
30
|
40
|
50
|
60
|
70
|
80
|
90
|
100
|
1 2 3 4 5 6 7 8 9 10
Cs/Ts
int isfull()
{
if(cs== total_size)
return 1;
else
return -1;
}
This
function will return 0 if current size is zero that indicates list is empty
1 2 3 4 5 6 7 8 9 10
Cs=0
Ts
int isempty()
{
if(cs==0)
return 1;
else
return 0;
}
The function
below will be used to update and item in a list . Suppose you want to update
item 40 to 80 then use this function.
Before
update:
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
After
update:
10
|
20
|
30
|
80
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
void update_item(int it1,int it2)
{
if(find_item(it1)==1)
{
int i;
for(i=0;list[i]!=it1;i++)
int a=list[i];
list[i]=it2;
cout<<"at"<<i<<"="<<list[i]<<endl;
cout<<"item successfully updated\n";
}
else
cout<<it1<<"is not in list\n";
}
The function
below will be used to update and item in a list by defining position at which
place you want to update an item. Suppose you want to update item 40 to 80 and
40 is at position ‘4’ then use this function, pass the position at new item to
the function. The function will replace the existing value with new value at
position passed as argument.
Before
update:
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
After
update:
10
|
20
|
30
|
80
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
////////////////////////////////////////////////////////////////////////////////////*/
void update_item_by_position(int it,int
pos)
{
int
a=list[pos];
list[pos]=it;
cout<<"item at position
"<<pos<<" is successfully updated\n";
cout<<"old item
was:"<<a<<endl;
cout<<"new item is
:"<<it<<endl;
}
Current size basically shows that how many items are in a list, so in order to get size of list the function below will be used that will print value of ‘Current size (cs)’.
void check_size_of_list()
{
cout<<"current size of list
is:"<<cs<<endl;
}
The function
below can be used to directly get the item present at particular position.
Suppose in list below you want to get item present t position 4, so just pass number
‘4’ as argument and function will return ’40’.
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
/////////////////////////////////////////////////////////////////////////////*/
int get_element_by_position(int pos)
{
return list[pos];
}
/*///////////////////////////////////////////////////////////////////////////////////
The function
below can be used to swap any two items in a list. You have to pass the items
that you want to swap. The function will first find both values in a list and
then swap them. Suppose you want to swap 20 and 40 in list so.
Before
swapping:
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
After
swapping:
10
|
40
|
30
|
20
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
void swapp_items(int it1,int it2)
{
int j=0,k=0;
do
{
j++;
}
while(list[j]!=it1);
do
{
k++;
}
while(list[k]!=it2);
int temp=0;
temp=list[j];
list[j]=list[k];
list[k]=temp;
}
The function below can be used to swap any two items in a list. You have to pass the positions of items that you want to swap. This thing will give you instant result and function will not have to find the values first. It will directly go to the positions and then swap items. Suppose you want to swap items at position 2 and 4 in list so.
Before
swapping:
10
|
20
|
30
|
40
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
After
swapping:
10
|
40
|
30
|
20
|
50
|
1 2 3 4 5 6 7 8 9 10
Cs
Ts
////////////////////////////////////////////////////////////////////////////////////*/
void swapp_items_by_position(int pos1,int
pos2)
{
int temp=0;
temp=list[pos1];
list[pos1]=list[pos2];
list[pos2]=temp;
}
/*/////////////////////////////////////////////////////////////////////////////////
The function
below can be used to copy list items from one list to another.
////////////////////////////////////////////////////////////////////////////////*/
void copy_list()
{
int i,j;
int *c_list=new int[cs];
for(i=0;i<cs;i++)
c_list[i]=list[i];
cout<<"your copied list
is\n";
for(j=0;j<cs;j++)
cout<<c_list[j]<<endl;
}
/*////////////////////////////////////////////////////////////////////////////////
The function
below can be used to remove an item from list. You have to pass the item you want
to delete. The function will first find item in list then delete it.
void remove_item()
{
int it;
do
{
cout<<"enter item to delete from list:";
cin>>it;
if(find_item(it)!=1)
cout<<"item is not in list\n";
}
while(find_item(it)!=1);
int i=0;
do
{
i++;
}
while(list[i]!=it);
int a;
a=list[i];
for(int j=i;j<cs-1;j++)
{
list[j]=list[j+1];
}
cs--;
}
/*/////////////////////////////////////////////////////////////////////////////
The function below can be used to remove an item from list. You have to pass the position from which you want to delete item. The function will go to that position in list then delete it.
//////////////////////////////////////////////////////////////////////////////*/
void remove_item_by_position()
{
int pos;
do
{
cout<<"enter position:";
cin>>pos;
if(pos<0||pos>cs)
cout<<"there is no item at position "<<pos<<endl;
}
while(pos<0||pos>cs);
int a;
a=list[pos];
for(int i=pos;i<cs;i++)
{
list[i]=list[i+1];
}
cs--;
}
////////////////////////////////////////////////////////////////////////////////
/* start of main*/
////////////////////////////////////////////////////////////////////////////////////
int main()
{
menu();
getch();
}
/*end of main */
Download c++ source code
Sample input outputs
Select option create list
Display all items in list option 4
This C++ project has developed by a student and can be improve student like you. You may found bugs in it but they are meant to be solve by you. It is very good for learning to change the logic or flow of code according to your need
Sample input outputs
Select option create list
Display all items in list option 4
This C++ project has developed by a student and can be improve student like you. You may found bugs in it but they are meant to be solve by you. It is very good for learning to change the logic or flow of code according to your need
i have some problem in my program related with list ... i want your help
ReplyDeletegreat reach
ReplyDelete