
BASIC DATA STRUCTURES IN C++
Sanchit Karve
born2c0de
"Accept No Limits"

In this Tutorial I assume that all of you have a working knowledge on how to use
Classes in C++ because all of my data structures are going to be based on them.
I realised that there are a lot of Data Structures Tutorials available but it's
rare to find one that uses OOP. So this one will mainly focus on having a data
structure incorporated as a class.
CODE IS COMPILED IN BORLAND C++ UNLESS OTHERWISE MENTIONED.
We shall cover the following Basic Data Structures in this Tutorial:
1. STACKS
2. QUEUES
3. LINKED LISTS
4. BINARY TREES
We shall also combine data structures together later in this tutorial such as
combining a Linked List along with a Stack etc. We shall also learn about Doubly
Linked Lists and Circular Linked Lists in this Tutorial.
So let's begin without wasting any time.
1) STACKS
Stacks are commonly used Data Structures while writing code. It's concept is
really simple which makes it even simpler to write it in code. Consider this
situation. There are a pile of 5 Books on a Table. You want to add one book to
the pile. What do you do??? You simply add the book on the TOP of the pile. What
if you want the third book from the new 6 book pile? You then lift each book one
by one from the TOP until the third book reaches the top. Then you take the
third book and replace all the others back into the pile by adding them from the
TOP.
If you've noticed I've mentioned the word TOP in Caps. Yes, TOP is the most
important word as far as stacks are concerned. Data is stored in a Stack where
adding of data is permitted only from the top. Removing/Deleting Data is also
done from the top. As Simple as That. Now you may ask where Stacks are used?
Stacks are infact used on every Processor. Each processor has a stack where data
and addresses are pushed or added to the stack. Again the TOP rule is followed
here. The ESP Register adds as a Stack Pointer that refers to the top of the
stack in the Processor. Anyway, since the explaination of how the Processor
Stack works is beyond the subject of this Tutorial, let's write our Stack Data
Structure. Remember some Stack Terminology before continuing. Adding Data to the
Stack is known as Pushing and deleting data from the stack is known as Popping.
#include
#include
#define MAX 10 // MAXIMUM STACK CONTENT
class stack
{
private:
int arr[MAX]; // Contains all the Data
int top; //Contains location of Topmost Data pushed onto Stack
public:
stack() //Constructor
{
top=1; //Sets the Top Location to 1 indicating an empty stack
}
void push(int a) // Push ie. Add Value Function
{
top++; // increment to by 1
if(top
#include
#define MAX 5 // MAXIMUM CONTENTS IN QUEUE
class queue
{
private:
int t[MAX];
int al; // Addition End
int dl; // Deletion End
public:
queue()
{
dl=1;
al=1;
}
void del()
{
int tmp;
if(dl==1)
{
cout<<"Queue is Empty";
}
else
{
for(int j=0;j<=al;j++)
{
if((j+1)<=al)
{
tmp=t[j+1];
t[j]=tmp;
}
else
{
al;
if(al==1)
dl=1;
else
dl=0;
}
}
}
}
void add(int item)
{
if(dl==1 && al==1)
{
dl++;
al++;
}
else
{
al++;
if(al==MAX)
{
cout<<"Queue is Full\n";
al;
return;
}
}
t[al]=item;
}
void display()
{
if(dl!=1)
{
for(int i=0;i<=al;i++)
cout<>>>[15P]>>>[29P]>>>[45N]
Here the data stored within the Data Structure is 12,15,29,45.
As you can see, the pointer with 12 points to the next linked list which is 15
which points to 29 and so on.
This is just a conceptual idea. In Reality all this data is stored in random
places in memory. Using Pointers help us to get all the data in order.
While Adding Data to a Linked List we check for previously added Linked Lists.
Then we reach the last node of the List where the pointer value is NULL and
point it to our newly created linked list, else if there is no previously
existing linked list we simply add one and set it's pointer to NULL.
Deletion is more complex. Suppose we want to delete the data 15. Then we first
find 15. Then we point the pointer which is present with 12 to the data in 29.
Then we delete the node which contains 15 as it's data.
Studying the Following Source code will help you understand and Appreciate the
Linked List:
#include
#include
class linklist
{
private:
struct node
{
int data;
node *link;
}*p;
public:
linklist();
void append( int num );
void add_as_first( int num );
void addafter( int c, int num );
void del( int num );
void display();
int count();
~linklist();
};
linklist::linklist()
{
p=NULL;
}
void linklist::append(int num)
{
node *q,*t;
if( p == NULL )
{
p = new node;
p>data = num;
p>link = NULL;
}
else
{
q = p;
while( q>link != NULL )
q = q>link;
t = new node;
t>data = num;
t>link = NULL;
q>link = t;
}
}
void linklist::add_as_first(int num)
{
node *q;
q = new node;
q>data = num;
q>link = p;
p = q;
}
void linklist::addafter( int c, int num)
{
node *q,*t;
int i;
for(i=0,q=p;ilink;
if( q == NULL )
{
cout<<"\nThere are less than "<data = num;
t>link = q>link;
q>link = t;
}
void linklist::del( int num )
{
node *q,*r;
q = p;
if( q>data == num )
{
p = q>link;
delete q;
return;
}
r = q;
while( q!=NULL )
{
if( q>data == num )
{
r>link = q>link;
delete q;
return;
}
r = q;
q = q>link;
}
cout<<"\nElement "<link )
cout<data;
}
int linklist::count()
{
node *q;
int c=0;
for( q=p ; q != NULL ; q = q>link )
c++;
return c;
}
linklist::~linklist()
{
node *q;
if( p == NULL )
return;
while( p != NULL )
{
q = p>link;
delete p;
p = q;
}
}
void main()
{
linklist ll;
cout<<"No. of elements = "<data=n;
tmp>link=top;
top=tmp;
}
int pop()
{
if(top==NULL)
{
cout<<"\nSTACK EMPTY";
return NULL;
}
node *tmp;
int n;
tmp=top;
n=tmp>data;
top=top>link;
delete tmp;
return n;
}
~lstack()
{
if(top==NULL)
return;
node *tmp;
while(top!=NULL)
{
tmp=top;
top=top>link;
delete tmp;
}
}
};
void main()
{
lstack s;
s.push(11);
s.push(101);
s.push(99);
s.push(78);
cout<<"Item Popped = "<data=n;
tmp>link=NULL;
if(front==NULL)
{
rear=front=tmp;
return;
}
rear>link=tmp;
rear=rear>link;
}
int del()
{
if(front==NULL)
{
cout<<"\nQUEUE EMPTY";
return NULL;
}
node *tmp;
int n;
n=front>data;
tmp=front;
front=front>link;
delete tmp;
return n;
}
~lqueue()
{
if(front==NULL)
return;
node *tmp;
while(front!=NULL)
{
tmp=front;
front=front>link;
delete tmp;
}
}
};
void main()
{
lqueue q;
q.add(11);
q.add(22);
q.add(33);
q.add(44);
q.add(55);
cout<<"\nItem Deleted = "<count();i++)
{
cout<data<link;
}
}
int CL_list::count()
{
node *q;
q=p;
int c=0;
if(p==NULL)
return 0;
else
c++;
while(q>link != p)
{
c++;
q=q>link;
}
return c;
}
void CL_list::del()
{
if(p==NULL)
return;
if(p>link==p)
{
p=NULL;
}
else
{
node *q;
q=p;
while(q>link != p )
q=q>link;
q>link=p>link;
q=p;
p=(q>link == NULL ? NULL : p>link);
delete q;
}
}
void CL_list::addatbeg(int n)
{
node *q,*t;
q=p;
while(q>link!=p)
q=q>link;
t=new node;
t>data=n;
t>link=p;
q>link=t;
p=t;
}
void CL_list::slideshow(float dlay,int x,int y)
{
if(p==NULL)
{
gotoxy(x,y);
cout<<"EMPTY LIST\n";
return;
}
node *q;
q=p;
while(!kbhit())
{
gotoxy(x,y);
cout<<" ";
gotoxy(x,y);
cout<data;
wait(dlay);
q=q>link;
}
}
void CL_list::wait(float t)
{
long time=GetTickCount()+(t*1000L);
while(GetTickCount()<=time)
{
/* WAIT !!! */
}
}
bool CL_list::operator ==(CL_list t)
{
if(t.p==NULL && p==NULL)
return 1;
if(this>count() != t.count())
return 0;
node *q;
q=p;
int flag;
flag=1;
node *a;
a=t.p;
for(int i=1;i<=count();i++)
{
if(a>data!=q>data)
flag=0;
a=a>link;
q=q>link;
}
if(a>data!=q>data)
flag=0;
return flag;
}
bool CL_list::operator !=(CL_list t)
{
return !(this>operator==(t));
}
void main()
{
CL_list a;
a.add(1);
a.add(2);
a.add(3);
a.add(4);
a.addatbeg(128);
a.del(); // 128 is deleted
cout<<"\nLIST DATA:\n";
a.display();
CL_list b=a;
if(b!=a)
printf("\nunEQUAL");
else
printf("\nEQUAL\n");
a.slideshow(1,13,13);
getch();
}
Here once again we have made sure that the last node always points to the first
node. Everything else seems fine. Comments should be enough to explain the code.
The interesting part of this code is the slideshow() function. It plainly
displays the list in an infinite loop which can be terminated by pressing a key.
The wait() function allows the delay while the kbhit() function checks for a
keypress.
Now comes the test. Write a similar linked list only with the following changes:
1) Structure node should be like this:
struct node
{
int data;
node *next; // Pointer to Next Node
node *prev; // Pointer to Previous Node
};
2) Remember that while adding and deleting the next and previous pointers have
to be set up accordingly.
3) Include a display function with a parameter like this:
void linklist::display(int type)
{
if(type==1)
{
// Code for output from First Node to Last node
}
else
{
// Code for output from Last Node to First
}
}
This function is really easy to write if you understand how to use both the next
and previous pointers.
If you still cant write the code mail me with your difficulties at my email add:
born2c0de@hotmail.com
4) BINARY TREES
Uptil now all data structures that we have covered (Stack,Queue,Linked List) are
linear in nature ie. they have a definate order of placement. Now we shall study
Binary Trees which requires a different thought process as it is a non linear
data structure.
A Binary Tree consists of a main node known as the Root. The Root then has two
subsections, ie. the left and the right half. The data subsequently stored
after the root is created depends on it's value compared to the root.
Suppose the root value is 10 and the Value to be added is 15, then the data is
added to the right section of the root.
The Basic idea is that every node can be thought of a binary tree itself. Each
node has two pointers, one to the left and the other to the right. Depending on
the value to be stored, it is placed after a node's right pointer if the value
of the node is lesser than the one to be added or the node's left pointer if
viceversa.
Let's take an Example. To add the Following List of Numbers, we end up with a
Binary Tree like this:
32 16 34 1 87 13 7 18 14 19 23 24 41 5 53
KEY:
[X] X = Root L/R = Data at Left/Right Node of X
[L]<>[R]
ROOT
[32]

[16]<>[34]
 
[1]<>[18] >[87]
  
  [41]<
  
  >[53]
 
 >[19]
 >[23]
 >[24]

>[13]

[7]<>[14]
[5]<
Here's How:
**: KEEP ADDING DATA IN THE TREE ON PAPER AFTER EACH STEP BELOW TO UNDERSTAND
HOW THE TREE IS FORMED.
1) Since 32 is the First Number to be added, 32 becomes the root of the tree.
2) Next Number is 16 which is lesser than 32 Hence 16 becomes left node of 32.
3) 34. Since 34 > 32 , 34 becomes the right node of the ROOT.
4) 1. Since 1 < 32 we jump to the left node of the ROOT. But since the left node
has already been taken we test 1 once again. Since 1 < 16, 1 becomes the left
node of 16.
5) 87. Since 87 > 32 we jump to the right node of the root. Once again this
space is occupied by 34. Now since 87 > 34, 87 becomes the right node of 34.
6) 13. Since 13 < 32 we jump to left node of the root. There, 13 < 16 so we
continue towards the left node of 16. There 13 > 1, so 13 becomes the right
node of 1.
7) Similarly work out addition till the end ie. before Number 53.
8) 53. Since 53 > 32 we jump to the right node of the root. There 53 > 34 so we
continue to the right node of 34. There 53 < 87 so we continue towards the
left node of 87. There 53 > 41 so we jump to the right node of 41. Since the
Right node of 41 is empty 53 becomes the right node of 41.
This should give you an idea of how a Binary Tree works. You must know that:
1) The linking of nodes to nodes in a Binary Tree is one to one in nature
ie. a node cannot be pointed by more than 1 node.
2) A Node can point to two different subnodes at the most.
Here in the binary tree above there are a few nodes whose left and right
pointers are empty ie. they have no subnode attached to them. So Nodes 5,14,18,
19,23,24,41 have their left nodes empty.
There are three popular ways to display a Binary Tree. Displaying the trees
contents is known as transversal. There are three ways of transversing a tree iw.
in inorder,preorder and postorder transversal methods. Description of each is
shown below:
PREORDER:
1) Visit the root.
2) Transverse the left leaf in preorder.
3) Transverse the right leaf in preorder.
INORDER:
1) Transverse the left leaf in inorder.
2) Visit the root.
3) Transverse the right leaf in inorder.
POSTORDER:
1) Transverse the left leaf in postorder.
2) Transverse the right leaf in postorder.
3) Visit the root.
Writing code for these three methods are simple if we understand the recursive
nature of a binary tree. Binary tree is recursive, as in each node can be
thought of a binary tree itself. It's just the order of displaying data that
makes a difference for transversal.
Deletion from a Binary Tree is a bit more difficult to understand. For now just
remember that for deleting a node, it is replaced with it's next inorder
successor. I'll explain everything after the Binary Tree code.
Now that you've got all your Binary Tree Fundas clear, let's move on with the
Source code.
#include
#define YES 1
#define NO 0
class tree
{
private:
struct leaf
{
int data;
leaf *l;
leaf *r;
};
struct leaf *p;
public:
tree();
~tree();
void destruct(leaf *q);
tree(tree& a);
void findparent(int n,int &found,leaf* &parent);
void findfordel(int n,int &found,leaf *&parent,leaf* &x);
void add(int n);
void transverse();
void in(leaf *q);
void pre(leaf *q);
void post(leaf *q);
void del(int n);
};
tree::tree()
{
p=NULL;
}
tree::~tree()
{
destruct(p);
}
void tree::destruct(leaf *q)
{
if(q!=NULL)
{
destruct(q>l);
del(q>data);
destruct(q>r);
}
}
void tree::findparent(int n,int &found,leaf *&parent)
{
leaf *q;
found=NO;
parent=NULL;
if(p==NULL)
return;
q=p;
while(q!=NULL)
{
if(q>data==n)
{
found=YES;
return;
}
if(q>data>n)
{
parent=q;
q=q>l;
}
else
{
parent=q;
q=q>r;
}
}
}
void tree::add(int n)
{
int found;
leaf *t,*parent;
findparent(n,found,parent);
if(found==YES)
cout<<"\nSuch a Node Exists";
else
{
t=new leaf;
t>data=n;
t>l=NULL;
t>r=NULL;
if(parent==NULL)
p=t;
else
parent>data > n ? parent>l=t : parent>r=t;
}
}
void tree::transverse()
{
int c;
cout<<"\n1.InOrder\n2.Preorder\n3.Postorder\nChoice: ";
cin>>c;
switch(c)
{
case 1:
in(p);
break;
case 2:
pre(p);
break;
case 3:
post(p);
break;
}
}
void tree::in(leaf *q)
{
if(q!=NULL)
{
in(q>l);
cout<<"\t"<data<r);
}
}
void tree::pre(leaf *q)
{
if(q!=NULL)
{
cout<<"\t"<data<l);
pre(q>r);
}
}
void tree::post(leaf *q)
{
if(q!=NULL)
{
post(q>l);
post(q>r);
cout<<"\t"<data<data==n)
{
found=1;
x=q;
return;
}
if(q>data>n)
{
parent=q;
q=q>l;
}
else
{
parent=q;
q=q>r;
}
}
}
void tree::del(int num)
{
leaf *parent,*x,*xsucc;
int found;
// If EMPTY TREE
if(p==NULL)
{
cout<<"\nTree is Empty";
return;
}
parent=x=NULL;
findfordel(num,found,parent,x);
if(found==0)
{
cout<<"\nNode to be deleted NOT FOUND";
return;
}
// If the node to be deleted has 2 leaves
if(x>l != NULL && x>r != NULL)
{
parent=x;
xsucc=x>r;
while(xsucc>l != NULL)
{
parent=xsucc;
xsucc=xsucc>l;
}
x>data=xsucc>data;
x=xsucc;
}
// if the node to be deleted has no child
if(x>l == NULL && x>r == NULL)
{
if(parent>r == x)
parent>r=NULL;
else
parent>l=NULL;
delete x;
return;
}
// if node has only right leaf
if(x>l == NULL && x>r != NULL )
{
if(parent>l == x)
parent>l=x>r;
else
parent>r=x>r;
delete x;
return;
}
// if node to be deleted has only left child
if(x>l != NULL && x>r == NULL)
{
if(parent>l == x)
parent>l=x>l;
else
parent>r=x>l;
delete x;
return;
}
}
void main()
{
tree t;
int data[]={32,16,34,1,87,13,7,18,14,19,23,24,41,5,53};
for(int i=0;i<15;i++)
t.add(data[i]);
t.transverse();
t.del(16);
t.transverse();
t.del(41);
t.transverse();
}
OUTPUT:
1.InOrder
2.Preorder
3.Postorder
Choice: 1
1
5
7
13
14
16
18
19
23
24
32
34
41
53
87
1.InOrder
2.Preorder
3.Postorder
Choice: 2
32
18
1
13
7
5
14
19
23
24
34
87
41
53
1.InOrder
2.Preorder
3.Postorder
Choice: 3
5
7
14
13
1
24
23
19
18
53
87
34
32
Press any key to continue
NOTE: Visual C++ may give Runtime Errors with this code. Compile with Turbo C++.
Just by looking at the output you might realise that we can print out the whole
tree in ascending order by using inorder transversal. Infact Binary Trees are
used for Searching [ Binary Search Trees {BST} ] as well as in Sorting.
The Addition of data part seems fine. Only the deletion bit needs to be
explained.
For deletion of data there are a few cases to be considered:
1) If the leaf to be deleted is not found.
2) If the leaf to be deleted has no subleafs.
3) If the leaf to be deleted has 1 subleaf.
4) If the leaf to be deleted has 2 subleafs.
Dealing with the first case is simple, we just mention an error message and
leave it out there.
In the second case since the node has no subnodes, the memory occupied by this
should be freed and either the left link or the right link of the parent of this
node should be set to NULL. Which of these should be set to NULL depends upon
whether the node being deleted is a left child or a right child of its parent.
In the third case we just adjust the pointer of the parent of the leaf to be
deleted such that after deletion it points to the child of the node being
deleted.
The last case in which the leaf to be deleted has to subleaves of its own is
rather complicated.The whole logic is to locate the inorder successor, copy it's
data and reduce the problem to simple deletion of a node with one or zero leaves.
Consider in the above program...(Refer to the previous tree as well) when we are
deleting 16 we search for the next inorder successor. So we simply set the data
value to 5 and delete the node with value 5 as shown for cases 2 and 3.
That's all for Binary Trees. Binary Trees are used for various other things
which even include Compression algorithms,binary searching,sorting etc. A lot of
Huffman,ShannonFano and other Compression algorithms use Binary Trees. If you
want source code of these Compression codes you can freely contact me at my mail
address.
That wraps up this Data Structure Tutorial. There are a lot more structures that
i'd love to mention such as Sparse Matrices, Graphs etc. but since the aim of
this tutorial was to give an introduction to Data Structures i decided not to
include them in this Tutorial. Maybe I can save them for another Tutorial that
starts from this point itself...later...
If you have any problems in understanding the text or the source code do let me
know. Any valuable comments and suggestions are welcome.
Sanchit Karve
born2c0de
"Accept No Limits"

[EOF]