ITec 2052- Data Structure and Algorithms

Chapter 3. BASIC DATA STRUCTURE

A data structure is a group of data elements grouped together under one name. These data
elements, known as members, can have different types and different lengths. Data
structure is a particular way of storing and organizing data in a computer so that it can be
used efficiently.
Different kinds of data structures are suited to different kinds of applications, and some are
highly specialized to specific tasks. For example, B-trees are particularly well-suited for
implementation of databases, while compiler implementations usually use hash tables to
look up identifiers.
Data structures provide a means to manage large amounts of data efficiently, such as large
databases and internet indexing services. Usually, efficient data structures are a key to
designing efficient algorithms. Some formal design methods and programming languages
emphasize data structures, rather than algorithms, as the key organizing factor in software
design. Storing and retrieving can be carried out on data stored in both main memory and in
secondary memory.

1. Analyzing the Performance of Data Structures

When thinking about a particular application or programming problem, many developers

find themselves most interested in writing the algorithm to tackle the problem at hand, or
adding cool features to the application to enhance the user's experience. Rarely, if ever, will
you hear someone excited about what type of data structure they are using. However, the
data structures used for a particular algorithm can greatly impact its performance. A
common example is finding an element in a data structure. With an array, this process takes
time proportional to the number of elements in the array. With binary search trees or
SkipLists, the time required is sub-linear. When searching large amounts of data, the data
structure chosen can make a difference in the application's performance that can be visibly
measured in seconds or even minutes.

Page 1
 ITec 2052- Data Structure and Algorithms

Since the data structure used by an algorithm can greatly affect the algorithm's
performance, it is important that there exists a rigorous method by which to compare the
efficiency of various data structures. What we, as developers utilizing a data structure, are
primarily interested in is how the data structures performance changes as the amount of
data stored increases. That is, for each new element stored by the data structure, how are
the running times of the data structure's operations effected?

2. Structures

Structures are aggregate data types built using elements of primitive data types. Data
structures are declared in C++ using the following syntax:
struct structure_name {
member_type1 member_name1;
member_type2 member_name2;
member_type3 member_name3;
.
.
} object_names;

where structure_name is a name for the structure type, object_name can be a set of valid
identifiers for objects that have the type of this structure. Within braces { } there is a list
with the data members, each one is specified with a type and a valid identifier as its name.
The struct keyword creates a new user defined data type that is used to declare variables of
an aggregate data type.

The first thing we have to know is that a data structure creates a new type: Once a data
structure is declared, a new type with the identifier specified as structure_name is created
and can be used in the rest of the program as if it was any other type.

For example:

struct product {
int weight;
float price;
};

Page 2
 ITec 2052- Data Structure and Algorithms

We have first declared a structure type called product with two members: weight and price,
each of a different fundamental type.

Once declared, product has become a new valid type name like the fundamental ones int,
char or short and from that point on we are able to declare objects (variables) of this
compound new type, like we have done with apple, banana and melon.

Right at the end of the struct declaration, and before the ending semicolon, we can use the
optional field object_name to directly declare objects of the structure type.

1.1 STACK:

Stack is an Abstract Data Type and common Data Structure, in which insertion and deletion
occur at the same end, is termed (called) a stack. It works on the principle LIFO (Last In, First
Out).

Modern CPUs use stack based architecture for handling function calls and parameter
handling. A stack is a list like structure where stack items can only be added or removed
from the end of the stack. Just like a plate stack in canteens where plates are added to the
top and later removed from the top.

When a function is called, the address of the next instruction is pushed onto the stack.
When the function exits, the address is popped off the stack and execution continues at
that address.

The basic operations in a Stack are:

1. Push:
 In which we push the data into the Stack.
 Push is an operation or function which helps in inserting an element into the stack.
 PUSH refers to adding an element to the stack.
 push (put) item onto stack

Page 3
 ITec 2052- Data Structure and Algorithms

2. Pop:
 In which we remove an element from the Stack.
 POP refers to removing an element from the stack.
 Pop is an operation similar to Deletion which helps in deleting or removing
an element from the stack
 pop (get) item from stack

All insertions and removals are done only from one side of the Stack, which is called the
'top' of the Stack. A stack is generally used in function calls where the local variables are
pushed onto the Stack and when the function returns, it pops the variables from the Stack.

“A stack is an ordered list in which all insertions and deletions are made at one end, called
the top”. Stacks are sometimes referred to as Last In First Out (LIFO) lists.
Stacks have some useful terminology associated with them:

 Push To add an element to the stack

 Pop To remove an element from the stack
 Peek To look at elements in the stack without removing them
 LIFO Refers to the last in, first out behavior of the stack
 FILO Equivalent to LIFO

Simple representation of a stack

Given a stack S=(a[1],a[2],.......a[n]) then we say that a1 is the bottom most element and
element a[i]) is on top of element a[i-1], 1<i<=n.

Page 4
 ITec 2052- Data Structure and Algorithms

The operations of stack is

1. PUSH operations
2. POP operations
Push - push (put) item onto stack
Pop - pop (get) item from stack

Initial Stack Push(8) Pop

TOS=> 8

TOS=> 4 4 TOS=> 4

1 1 1

3 3 3

6 6 6

The Stack ADT

A stack S is an abstract data type (ADT) supporting the following three methods:
push(n) : Inserts the item n at the top of stack

pop() : Removes the top element from the stack and returns that top element. An
error occurs if the stack is empty.

1. Adding an element into a stack.(called PUSH operations ) , Adding element into the TOP
of the stack is called PUSH operation.

Check conditions:
TOP = N , then STACK FULL

Where N is maximum size of the stack.

Page 5
 ITec 2052- Data Structure and Algorithms

1.1 Implementation of Stack using Arrays:

1.1.1 Inserting an element into an array: (PUSH Operation)

The Basic Operations:

Push()
{
if there is room {
put an item on the top of the stack
else
give an error message
}
}
} item /
element 6
Stack Stack

PUSH top 6
Operation
top 8 8
4 4

Array Implementation of Stacks: The PUSH operation

Here, as you might have noticed, addition of an element is known as the PUSH operation.
So, if an array is given to you, which is supposed to act as a STACK, you know that it has to
be a STATIC Stack; meaning, data will overflow if you cross the upper limit of the array. So,
keep this in mind.
Algorithm:
Step-1: Increment the Stack TOP by 1. Check whether it is always less than the Upper Limit
of the stack. If it is less than the Upper Limit go to step-2 else report -"Stack Overflow"
Step-2: Put the new element at the position pointed by the TOP

Page 6
 ITec 2052- Data Structure and Algorithms

Implementation:
static int stack[UPPERLIMIT];
int top= -1; /*stack is empty*/
..
..
main()
{
..
..
push(item);
..
..
}
push(int item)
{
top = top + 1;
if(top < UPPERLIMIT)
stack[top] = item; /*step-1 & 2*/
else
cout<<"Stack Overflow";
}
Note:- In array implementation,we have taken TOP = -1 to signify the empty stack, as this
simplifies the implementation.
1.1 Deleting an element from a stack. (POP operations)
Deleting or Removing element from the TOP of the stack is called POP operations.
Check Condition:

TOP = -1 , then STACK Underflow

Deletion in stack (POPOperation)

Page 7
 ITec 2052- Data Structure and Algorithms

Pop()

{
if stack not empty {
return the value of the top item
remove the top item from the stack
}
else {
give an error message
}

item /
element 6

top 6 POP
8 operation
top 8
4
4
Stack
Stack
Array Implementation of Stacks: the POP operation

POP is the synonym for delete when it comes to Stack. So, if you're taking an array as the
stack, remember that you'll return an error message, "Stack underflow", if an attempt is
made to Pop an item from an empty Stack. OK.
Algorithm
Step-1: If the Stack is empty then give the alert "Stack underflow" and quit; or else go to
step-2
Step-2: a) Hold the value for the element pointed by the TOP
b) Put a NULL value instead
c) Decrement the TOP by 1

Page 8
 ITec 2052- Data Structure and Algorithms

Implementation:
static int stack[UPPPERLIMIT];
int top=-1;
..
..
main()
{
..
poped_val = pop();
..
..
}
int pop()
{
int del_val = 0;
if(top == -1)
cout<<"Stack underflow"; /*step-1*/
else
{
del_val = stack[top]; /*step-2*/
stack[top] = NULL;
top = top -1;
}
return(del_val);
}
Note: - Step-2:(b) signifies that the respective element has been deleted.

Page 9
 ITec 2052- Data Structure and Algorithms

Full Array implementation of stack example

#include<iostream.h>
#include<stdlib.h>
const int max_size=5;
int stack[max_size];
int top=-1;
void push(int value)
{
if (top<max_size-1)
{
top++;
stack[top]=value;
}
else
cout<<"Stack over flow\n";
}
int pop()
{
if(top==-1)
{
cout<<"Stack under flow\n";
return -1000;
}
else
{
int t=stack[top];
top--;
return t;
}

Page 10
 ITec 2052- Data Structure and Algorithms

}
void display()
{
if (top==-1)
{
cout<<"Stack is empty\n";
{
cout<<"==== contents in the stack==\n";
for(int i=top;i>=0;i--)
cout<<stack[i]<<endl;
}
}
void main()
{
int ch,item;
while(1)
{
cout<<"\n Enter 1 to push\n";
cout<<"\n Enter 2 to pop\n";
cout<<"\n Enter 3 to display\n";
cout<<"\n enter 4 to exit \n";
cin>>ch;
switch (ch)
{
case 1:
cout<<"Enter an item to push\n";
cin>>item;
push(item);
break;

Page 11
 ITec 2052- Data Structure and Algorithms

case 2:
item=pop();
if(item!=-1000)
cout<<item<<" is poped from the stack\n";
break;
case 3:
display();
break;
case 4:
exit(0);
default:
cout<<" No operation\n";
}
}
}
}
1.2 Applications of Stack

As there are many applications in the field of computer science. Here I will list few major
applications of the stack.
1. Stack Data structures are mainly used in evaluating the Expressions and Syntax
parsing.
2. Stack Data Type is used in conversion of Decimal number to Binary number.
3. Stack is used in the application of the Quick Sort to sort a given array or List. Quick
sort is one of the efficient sorting techniques which is based on Divide and conquer
algorithm.
4. Backtrackings is other major applications of stack. In the maze problems
backtracking helps to trace the previous path and each path is stored in the form of
stack data structure.
5. It is useful during the execution of recursive programs

Page 12
 ITec 2052- Data Structure and Algorithms

6. A Stack is useful for designing the compiler in operating system to store local
variables inside a function block.
7. A stack (memory stack) can be used in function calls including recursion.
8. Reversing Data
9. Reverse a List
10. Parsing – It is a logic that breaks into independent pieces for further processing
11. Backtracking
1.3 QUEUE :

Queue is an abstract data type and a common data structure similar to stack. Queue is an
ordered list in which insertions deletion operations are done at different ends. The end at
which insertion is performed is known as rear end. The end at which deletion operation is
performed is known as front end.

Queue follows "First in First out Principle" which implies that the element which is inserted
first is deleted first from the queue. Queue can be implemented using arrays and linked
lists.
for example : Let 1,2,3,4,5 be the five elements inserted and the first element inserted is 1
and next element to be inserted is 2 and soon . To delete an element from the Queue, the
first element to be deleted is 1 which follows First In First Out principle.

The conceptual picture of a queue is something like this:

------------------
values in ----> items in the queue ----> values out
------------------
^ ^
| |
this is the rear of this is the front of
the queue the queue

Queues are a type of container adaptor, specifically designed to operate in a FIFO context
(first-in first-out), where elements are inserted into one end of the container and extracted

Page 13
 ITec 2052- Data Structure and Algorithms

From the other.

Think of people standing in line. A queue is a First-In-First-Out (FIFO) data structure. Items
can only be added at the rear of the queue, and the only item that can be removed is the
one at the front of the queue. Elements are pushed into the "back" of the specific container
and popped from its "front".

Queue is a particular kind of abstract data type or collection in which the entities in the
collection are kept in order and the principal (or only) operations on the collection are the
addition of entities to the rear terminal position, known as enqueue, and removal of entities
from the front terminal position, known as dequeue.

This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the
first element added to the queue will be the first one to be removed. This is equivalent to
the requirement that once a new element is added, all elements that were added before
have to be removed before the new element can be removed. Often a peek or front
operation is also entered, returning the value of the front element without dequeuing it. A
queue is an example of a linear data structure, or more abstractly a sequential collection.
In General
 It is a data structure that has access to its data at the front and rear.
 It operates on FIFO (Fast In First Out) basis.
 It uses two pointers/indices to keep track of information/data.
 It has two basic operations:
o enqueue - inserting data at the rear of the queue
o dequeue – removing data at the front of the queue

Page 14
 ITec 2052- Data Structure and Algorithms

dequeue enqueue

Front Rear
“A queue is an ordered list in which all insertions at one end called REAR and deletions are
made at another end called FRONT”. queues are sometimes referred to as First In First Out
(FIFO) lists.
Example
1. The people waiting in line at a bank cash counter form a queue.
2. In computer, the jobs waiting in line to use the processor for execution. This queue
is called Job Queue.
Operations of Queue
There are two basic queue operations. They are,
Enqueue – Inserts an item / element at the rear end of the queue. An error occurs if the
queue is full.
Dequeue – Removes an item / element from the front end of the queue, and returns it to
the user. An error occurs if the queue is empty.

1.2.1 Inserting an element into a queue

Procedure addq (item : items);

{add item to the queue q}
begin
if rear=n thenqueuefull
else begin
rear :=rear+1;
q[rear]:=item;
end;
end;{of addq}

Page 15
 ITec 2052- Data Structure and Algorithms

1.2.2. Deletion in a queue

proceduredeleteq (var item : items);

{delete from the front of q and put into item}
begin
if front = rear thenqueueempty
else begin
front := front+1
item := q[front];
end;
end
1.3 Application of queue
Queues remember things in first-in-first-out (FIFO) order. Good for fair (first come first
served) ordering of actions.
1.4 Circular Queue:
Location of queue is viewed in a circular form. The first location is viewed after the
last one. Overflow occurs when all the locations are filled.

The circular array implementation of a queue with MAX_SIZE can be simulated as follows:

12 11
13 10
9
MAX_SIZE - 1 8
0 7
1 6
2 5
3 4

Analysis:
Consider the following structure: int Num[MAX_SIZE];
We need to have two integer variables that tell:
- the index of the front element
- the index of the rear element

Page 16
 ITec 2052- Data Structure and Algorithms

We also need an integer variable that tells:

- the total number of data in the queue
int FRONT =-1,REAR =-1;
int QUEUESIZE=0;

 To enqueue data to the queue

o check if there is space in the queue
QUEUESIZE<MAX_SIZE ?
Yes: - Increment REAR
REAR = = MAX_SIZE ?
Yes: REAR = 0
- Store the data in Num[REAR]
- Increment QUEUESIZE
FRONT = = -1?
Yes: - Increment FRONT
No: - Queue Overflow

 To dequeue data from the queue

o check if there is data in the queue
QUEUESIZE > 0 ?
Yes: - Copy the data in Num[FRONT]
- Increment FRONT
FRONT = = MAX_SIZE ?
Yes: FRONT = 0
- Decrement QUEUESIZE
No: - Queue Underflow

Implementation:
const int MAX_SIZE=100;
int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;

void enqueue(int x)
{
if(QUEUESIZE<MAX_SIZE)
{
REAR++;
if(REAR = = MAX_SIZE)
REAR=0;
Num[REAR]=x;
QUEUESIZE++;
if(FRONT = = -1)
FRONT++;
}

Page 17
 ITec 2052- Data Structure and Algorithms

else
cout<<"Queue Overflow";
}
int dequeue()
{
int x;
if(QUEUESIZE>0)
{
x=Num[FRONT];
FRONT++;
if(FRONT = = MAX_SIZE)
FRONT = 0;
QUEUESIZE--;

}
else
cout<<"Queue Underflow";
return(x);
}

Another Algorithm Circular Queue Insert

Void CQInsert ( int queue[ ], front, rear, item)

{
if ( front = = 0 )
front = front +1;
if ( ( ( rear = maxsize ) && ( front = = 1 ) ) || ( ( rear ! = 0 )&& ( front = rear +1)))
{
Cout<< “ queue overflow “;

if( rear = = maxsize )

rear = 1;
else
rear = rear + 1;
q [ rear ] = item;
}
}

Page 18
 ITec 2052- Data Structure and Algorithms

Algorithm Circular Queue Delete

Int CQDelete ( queue [ ], front, rear )
{
if ( front = = 0 )
Cout<<” queue underflow “;
else
{
item = queue [ front ];
if(front = = rear )
{
front = 0; rear = 0;
}
else if ( front = = maxsize )
{
front = 1;
}
else
front = front + 1;
}
return item;
}
Priority Queue
A priority queue is a collection of elements such that each element has been assigned a
priority and such that the order in which elements are deleted and processed comes from
the following rules:
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which
they were added to the queue.
Two types of queue are

Page 19
 ITec 2052- Data Structure and Algorithms

1. Ascending Priority Queue

2. Descending Priority Queue
1. Ascending Priority Queue
Collection of items into which item can be inserted arbitrarily & from which
only the smallest item can be removed.
2. Descending Priority Queue
Collection of items into which item can be inserted arbitrarily & from which
only the largest item can be removed.
- is a queue where each data has an associated key that is provided at the
time of insertion.
- Dequeue operation deletes data having highest priority in the list
- One of the previously used dequeue or enqueue operations has to be
modified
Example: Consider the following queue of persons where females have higher
priority than males (gender is the key to give priority).

Abebe Alemu Aster Belay Kedir Meron Yonas

Male Male Female Male Male Female Male
Dequeue()- deletes Aster
Abebe Alemu Belay Kedir Meron Yonas
Male Male Male Male Female Male
Dequeue()- deletes Meron
Abebe Alemu Belay Kedir Yonas
Male Male Male Male Male

Now the queue has data having equal priority and dequeue operation deletes the
front element like in the case of ordinary queues.
Dequeue()- deletes Abebe
Alemu Belay Kedir Yonas
Male Male Male Male
Dequeue()- deletes Alemu

Belay Kedir Yonas

Male Male Male
Thus, in the above example the implementation of the dequeue operation need to be
modified.

Page 20
 ITec 2052- Data Structure and Algorithms

Demerging Queues

- is the process of creating two or more queues from a single queue.

- used to give priority for some groups of data

Example: The following two queues can be created from the above priority queue.
Aster Meron Abebe Alemu Belay Kedir Yonas
Female Female Male Male Male Male Male

Algorithm:
create empty females and males queue
while (PriorityQueue is not empty)
{
Data=DequeuePriorityQueue(); // delete data at the front
if(gender of Data is Female)
EnqueueFemale(Data);
else
EnqueueMale(Data);
}

Application of Queues

i. Print server- maintains a queue of print jobs

ii. Disk Driver- maintains a queue of disk input/output requests

iii. Task scheduler in multiprocessing system- maintains priority queues of processes

iv. Telephone calls in a busy environment –maintains a queue of telephone calls

Simulation of waiting line- maintains a queue of persons.

Page 21
 ITec 2052- Data Structure and Algorithms

Linked List
1. Linked Lists

Note from me:

Linked list: - is a data structure consisting of a group of nodes which together represents a sequence.

- Each node is composed of (made up of) data and a reference (pointer) which points to the next node in the
sequence. The last node is linked to a terminator (null) used to signify the end of the list.
- Linked list can be used to implement several other common abstract data types. Including:

 Lists
 Stacks
 Queues
 Associative arrays, etc.

Linked list is one of the fundamental data structures, and can be used to implement other
data structures. In a linked list there are different numbers of nodes. Each node is consists
of two fields. The first field holds the value or data and the second field holds the reference
to the next node or null if the linked list is empty.

Each record of a linked list is often called an element or node. The field of each node that
contains the address of the next node is usually called the next link or next pointer. The
remaining fields are known as the data, information, value, cargo, or payload fields. The
head of a list is its first node. The tail of a list may refer either to the rest of the list after the
head, or to the last node in the list.

The linked list is generally pictured as a list of linear nodes that are tethered together
somehow. In C/++, you generally have a structure which contains data and a pointer to the
next structure container which contains data and a pointer to the next structure container...
and so on. The linked list's main advantage is that it doesn't contain data in a contiguous

Page 22
 ITec 2052- Data Structure and Algorithms

way and rather, a flexible way. This allows for fast insertion and better overall iteration. The
linked list is often even used as the basis for other containers (such as queue or stack
containers).

The linked list is used in many libraries/applications and for a good reason. The following
are advantages it has over other containers,

 Efficient insertion and erasure of elements anywhere in the container (constant

time).
 Iterating over the elements in forward order (linear time).
 Efficient moving elements and block of elements within the container or even
between different containers (constant time).

Linked lists are the most basic self-referential structures. Linked lists allow you to have a
chain of structs with related data.

Array vs. Linked lists

Arrays are simple and fast but we must specify their size at construction time. This has its
own drawbacks. If you construct an array with space for n, tomorrow you may need
n+[Link] comes a need for a more flexible system.

The principal benefit of a linked list over a conventional array is that the list elements can
easily be inserted or removed without reallocation or reorganization of the entire structure
because the data items need not be stored contiguously in memory or on disk. Linked lists
allow insertion and removal of nodes at any point in the list, and can do so with a constant
number of operations if the link previous to the link being added or removed is maintained
during list traversal.

An array allocates memory for all its elements lumped together as one block of memory.
In contrast, a linked list allocates space for each element separately in its own block of
memory called a "linked list element" or "node". The list gets is overall structure by using
pointers to connect all its nodes together like the links in a chain.

Page 23
 ITec 2052- Data Structure and Algorithms

Each node contains two fields: a "data" field to store whatever element type the list holds
for its client, and a "next" field which is a pointer used to link one node to the next node.

Advantages of Linked Lists

Flexible space use by dynamically allocating space for each element as needed. This implies
that one need not know the size of the list in advance. Memory is efficiently utilized.

A linked list is made up of a chain of nodes. Each node contains:

• the data item, and

• a pointer to the next node

2.1. Single linked List

Singly linked lists contain nodes which have a data field as well as a next field, which points
to the next node in line. A singly linked linear list is a recursive data structure, because it
contains a pointer to a smaller object of the same type.

A singly linked list whose nodes contain two fields: an integer value and a link to the
next node

Linkedlist Node {
data // The value or data stored in the node
next // A reference to the next node, null for last node
}

The singly-linked list is the easiest of the linked list, which has one link per node.

2.1.1. Creating Linked Lists in C++

Page 24
 ITec 2052- Data Structure and Algorithms

A linked list is a data structure that is built from structures and pointers. It forms a chain of
"nodes" with pointers representing the links of the chain and holding the entire thing
together. A linked list can be represented by a diagram like this one:

This linked list has four nodes in it, each with a link to the next node in the series. The last
node has a link to the special value NULL, which any pointer (whatever its type) can point
to, to show that it is the last link in the chain. There is also another special pointer, called
Start (also called head), which points to the first link in the chain so that we can keep track
of it.
A single head pointer points to the first node in the list. Each node contains a single .next
pointer to the next node. The .next pointer of the last node is NULL. The empty list is
represented by a NULL head pointer.

2.1.2. Defining the data structure for a linked list

The key part of a linked list is a structure, which holds the data for each node (the name,
address, age or whatever for the items in the list), and, most importantly, a pointer to the
next node. Here we have given the structure of a typical node:
struct node
{ char name[20]; // Name of up to 20 letters
int age;
float height; // In metres
node *next;// Pointer to next node
};
struct node *start_ptr = NULL;

The important part of the structure is the line before the closing curly brackets. This gives a
pointer to the next node in the list. This is the only case in C++ where you are allowed to
refer to a data type (in this case node) before you have even finished defining it!

Page 25
 ITec 2052- Data Structure and Algorithms

We have also declared a pointer called start_ptr that will permanently point to the start of
the list. To start with, there are no nodes in the list, which is why start_ptr is set to NULL.

Exercise: -
A library wants to manage its books with a computer program. A book is characterized by
the author, the title and the ISBN number. Write down a useful node struct for this case.

2.1.3. Adding a node to the list

The first problem that we face is how to add a node to the list. For simplicity's sake, we will
assume that it has to be added to the end of the list, although it could be added anywhere
in the list (a problem we will deal with later on).

Firstly, we declare the space for a pointer item and assign a temporary pointer to it. This is
done using the new statement as follows:

temp
Node *temp;
?
temp = new node;

We can refer to the new node as *temp, i.e. "the node that temp points to". When the
fields of this structure are referred to, brackets can be put round the *temp part, as
otherwise the compiler will think we are trying to refer to the fields of the pointer.
Alternatively, we can use the arrow pointer notation.
Having declared the node, we ask the user to fill in the details of the person, i.e. the name,
age, address or whatever:

cout << "Please enter the name of the person: ";

cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout <<"Please enter the height of the person: ";
cin >> temp->height;
temp->next = NULL;

Page 26
 ITec 2052- Data Structure and Algorithms

The last line sets the pointer from this node to the next to NULL, indicating that this node,
when it is inserted in the list, will be the last node. Having set up the information, we have
to decide what to do with the pointers. Of course, if the list is empty to start with, there's
no problem - just set the Start pointer to point to this node (i.e. set it to the same value as
temp):
if (start_ptr == NULL)
start_ptr = temp;

Examples: -
1. Insert at the front

First we create a structure “node”. It has two members and first is int data which will store
the information and second is node *next which will hold the address of the next node.
Linked list structure is complete so now we will create linked list. We can insert data in the
linked list from 'front' and at the same time from 'back’. Now we will examine how we can
insert data from front in the linked list.

struct node
{
int data; // will store information
node *next; // the reference to the next node
};

At first initialize node type.

node *head = NULL; //empty linked list
Then we take the data input from the user and store in the node info variable. Create a
temporary node node *temp and allocate space for it.

node *temp; //create a temporary node

temp = new node; //allocate space for node

Page 27
 ITec 2052- Data Structure and Algorithms

Then place info to temp->data. So the first field of the node *temp is filled. Now temp->next
must become a part of the remaining linked list (although now linked list is empty but
imagine that we have a 2 node linked list and head is pointed at the front) So temp->next
must copy the address of the *head (Because we want insert at first) and we also want that
*head will always point at front. So *head must copy the address of the node *temp.

Figure: Insert at first

temp->data = info; // store data(first field)

temp->next=head; // store the address of the pointer
head(second field)
head = temp; // transfer the address of 'temp' to
'head'

2. Traverse

Now we want to see the information stored inside the linked list. We create node *temp1.
Transfer the address of *head to *temp1. So *temp1 is also pointed at the front of the linked
list. Linked list has 3 nodes.

Page 28
 ITec 2052- Data Structure and Algorithms

We can get the data from first node using temp1->data. To get data from second node, we
shift *temp1 to the second node. Now we can get the data from second node.

while( temp1!=NULL )
{
cout<< temp1->data<<" ";// show the data in the linked
list
temp1 = temp1->next; // tranfer the address of 'temp-
>next' to 'temp'
}

Figure: Traverse

This process will run until the linked list’s next is NULL.

3. Insert from back

Insert data from back is very similar to the insert from front in the linked list. Here the extra
job is to find the last node of the linked list.

node *temp1; // create a temporary node

temp1=(node*)malloc(sizeof(node)); // allocate space for node
temp1 = head; // transfer the address of 'head' to 'temp1'
while(temp1->next!=NULL) // go to the last node
temp1 = temp1->next; //tranfer the address of 'temp1->next'
to 'temp1'
Now, Create a temporary node node *temp and allocate space for it. Then place info to temp-
>data, so the first field of the node node *temp is filled. node *temp will be the last node of the
linked list. For this reason, temp->next will be NULL. To create a connection between linked

Page 29
 ITec 2052- Data Structure and Algorithms

list and the new node, the last node of the existing linked list node *temp1`s second field
temp1->next is pointed to node *temp.

Figure: Insert at last

node *temp; // create a temporary node

temp = (node*)malloc(sizeof(node)); // allocate space for node
temp->data = info; // store data(first field)
temp->next = NULL; // second field will be null(last node)
temp1->next = temp; // 'temp' node will be the last node

4. Insert after specified number of nodes

Insert data in the linked list after specified number of node is a little bit complicated. But
the idea is simple. Suppose we want to add a node after 2nd position. So, the new node
must be in 3rd position. The first step is to go the specified number of node. Let, node
*temp1 is pointed to the 2nd node now.
cout<<"ENTER THE NODE NUMBER:";
cin>>node_number; // take the node number from user
node *temp1; // create a temporary node
temp1 = new node; // allocate space for node
temp1 = head;

Page 30
 ITec 2052- Data Structure and Algorithms

for( int i = 1 ; i < node_number ; i++ )

{
temp1 = temp1->next; // go to the next node

if( temp1 == NULL )

{
cout<<node_number<<" node is not exist"<< endl;
break;
}
}

Now, Create a temporary node node *temp and allocate space for it. Then place info to temp-
>next , so the first field of the node node *temp is filled.

node *temp; // create a temporary node

temp = (node*)malloc(sizeof(node)); // allocate space for node
temp->data = info; // store data(first field)

To establish the connection between new node and the existing linked list, new node’s next
must pointed to the 2nd node’s (temp1) next. The 2nd node’s (temp1) next must pointed to
the new node(temp).

temp->next = temp1->next; //transfer the address of

temp1->next to temp->next
temp1->next = temp; //transfer the address of temp to temp1->next

Page 31
 ITec 2052- Data Structure and Algorithms

Figure: Insert after specified number of nodes

It is harder to add a node if there are already nodes in the list. In this case, the secret is to
declare a second pointer, temp2, to step through the list until it finds the last node.

Node *temp2;
temp2 = start_ptr;// We know this is not NULL - list not empty!
while (temp2->next != NULL)
{
temp2 = temp2->next; // Move to next link in chain
}
The loop will terminate when temp2 points to the last node in the chain, and it knows when
this happened because the next pointer in that node will point to NULL. When it has found
it, it sets the pointer from that last node to point to the node we have just declared:
temp2->next = temp;

The link temp2->next in this diagram is the link joining the last two nodes. The full code for
adding a node at the end of the list is shown below, in its own little function:
void add_node_at_end ()
{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data

temp = new node;
cout << "Please enter the name of the person: ";

Page 32
 ITec 2052- Data Structure and Algorithms

cin >> temp->name;

cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->next = NULL;

// Set up link to this node

if (start_ptr == NULL)
start_ptr = temp;
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->next != NULL)
{ temp2 = temp2->next;
// Move to next link in chain
}
temp2->next = temp;
}
}
Exercise: -

Assume that our linked list is sorted by age. So if we add a new node, we have to put
it at the right position in the list. Modify the above code dealing with this new
requirement.
2.1.4. Displaying the list of nodes

Having added one or more nodes, we need to display the list of nodes on the screen. This is
comparatively easy to do. Here is the method:

1. Set a temporary pointer to point to the same thing as the start pointer.
2. If the pointer points to NULL, display the message "End of list" and stop.
3. Otherwise, display the details of the node pointed to by the start pointer.
4. Make the temporary pointer point to the same thing as the next pointer of the node
it is currently indicating.
5. Jump back to step 2.

Page 33
 ITec 2052- Data Structure and Algorithms

The temporary pointer moves along the list, displaying the details of the nodes it comes
across. At each stage, it can get hold of the next node in the list by using the next pointer of
the node it is currently pointing to. Here is the C++ code that does the job:
Node *temp;
temp = start_ptr;
do
{ if (temp == NULL)
cout << "End of list" << endl;
else
{ // Display details for what temp points to
cout << "Name : " << temp->name << endl;
cout << "Age : " << temp->age << endl;
cout << "Height : " << temp->height << endl;
cout << endl; // Blank line

// Move to next node (if present)

temp = temp->next;
}
} while (temp != NULL);

Check through this code, matching it to the method listed above. It helps if you draw a
diagram on paper of a linked list and work through the code using the diagram.

2.1.5. Navigating through the list

One thing you may need to do is to navigate through the list, with a pointer that moves
backwards and forwards through the list, like an index pointer in an array. This is certainly
necessary when you want to insert or delete a node from somewhere inside the list, as you
will need to specify the position.
We will call the mobile pointer current. First of all, it is declared, and set to the same value as
the start_ptr pointer:
node *current;
current = start_ptr;
Notice that you don't need to set current equal to the address of the start pointer, as they
are both pointers. The statement above makes them both points to the same thing:

Page 34
 ITec 2052- Data Structure and Algorithms

It's easy to get the current pointer to point to the next node in the list (i.e. move from left to
right along the list). If you want to move current along one node, use the next field of the
node that it is pointing to at the moment:
current = current->next;

In fact, we had better check that it isn't pointing to the last item in the list. If it is, then there
is no next node to move to:
if (current->next == NULL)
cout << "You are at the end of the list." << endl;
else
current = current->next;

Moving the current pointer back one step is a little harder. This is because we have no way
of moving back a step automatically from the current node. The only way to find the node
before the current one is to start at the beginning, work our way through and stop when we
find the node before the one we are considering at the moment. We can tell when this
happens, as the next pointer from that node will point to exactly the same place in memory
as the current pointer (i.e. the current node).

previous current
Start

NULL

Page 35
 ITec 2052- Data Structure and Algorithms

First of all, we had better check to see if the current node is also first the one. If it is, then
there is no "previous" node to point to. If not, check through all the nodes in turn until we
detect that we are just behind the current one (Like a pantomime - "behind you!")
if (current == start_ptr)
cout << "You are at the start of the list" << endl;
else
{ node *previous; // Declare the pointer
previous = start_ptr;

while (previous->next != current)

{ previous = previous->next;
}
current = previous;
}

The else clause translates as follows: Declare a temporary pointer (for use in this else clause
only). Set it equal to the start pointer. All the time that it is not pointing to the node before
the current node, move it along the line. Once the previous node has been found, the
current pointer is set to that node - i.e. it moves back along the list.
Now that you have the facility to move back and forth, you need to do something with it.
Firstly, let's see if we can alter the details for that particular node in the list:
cout << "Please enter the new name of the person: ";
cin >> current->name;
cout << "Please enter the new age of the person : ";
cin >> current->age;
cout << "Please enter the new height of the person: ";
cin >> current->height;

The next easiest thing to do is to delete a node from the list directly after the current
position. We have to use a temporary pointer to point to the node to be deleted. Once this
node has been "anchored", the pointers to the remaining nodes can be readjusted before
the node on death row is deleted. Here is the sequence of actions:

1. Firstly, the temporary pointer is assigned to the node after the current one. This is
the node to be deleted:

Page 36
 ITec 2052- Data Structure and Algorithms

current temp

NULL

2. Now the pointer from the current node is made to leap-frog the next node and point
to the one after that:
current temp

NULL

3. The last step is to delete the node pointed to by temp.

Here is the code for deleting the node. It includes a test at the start to test whether the
current node is the last one in the list:
if (current->next == NULL)
cout << "There is no node after current" << endl;
else
{ node *temp;
temp = current->next;
current->next = temp->next; // Could be NULL
delete temp;
}
Here is the code to add a node after the current one. This is done similarly, but we haven't
illustrated it with diagrams:
if (current->next == NULL)
add_node_at_end();
else
{ node *temp;
new temp;
get_details(temp);
// Make the new node point to the same thing as
// the current node
temp->next = current->next;
// Make the current node point to the new link

Page 37
 ITec 2052- Data Structure and Algorithms

// in the chain
current->next = temp;
}

We have assumed that the function add_node_at_end() is the routine for adding the node to
the end of the list that we created near the top of this section. This routine is called if the
current pointer is the last one in the list so the new one would be added on to the end.

Similarly, the routine get_temp(temp) is a routine that reads in the details for the new node
similar to the one defined just above.
2.1.6. Deleting a node from the list

When it comes to deleting nodes, we have three choices: Delete a node from the start of
the list, delete one from the end of the list, or delete one from somewhere in the middle.
For simplicity, we shall just deal with deleting one from the start or from the end.

When a node is deleted, the space that it took up should be reclaimed. Otherwise the
computer will eventually run out of memory space. This is done with the delete instruction:

delete temp; // Release the memory pointed to by temp

However, we can't just delete the nodes willy-nilly as it would break the chain. We need to
reassign the pointers and then delete the node at the last moment. Here is how we go
about deleting the first node in the linked list:

temp = start_ptr; // Make the temporary pointer

// identical to the start pointer

Page 38
 ITec 2052- Data Structure and Algorithms

Now that the first node has been safely tagged (so that we can refer to it even when the
start pointer has been reassigned), we can move the start pointer to the next node in the
chain:
start_ptr = start_ptr->next; // Second node in chain.

delete temp; // Wipe out original start node

Here is the function that deletes a node from the start:

void delete_start_node()
{ node *temp;
temp = start_ptr;
start_ptr = start_ptr->next;
delete temp;
}

Deleting a node from the end of the list is harder, as the temporary pointer must find where
the end of the list is by hopping along from the start. This is done using code that is almost
identical to that used to insert a node at the end of the list. It is necessary to maintain two
temporary pointers, temp1 and temp2. The pointer temp1 will point to the last node in the list
and temp2 will point to the previous node. We have to keep track of both as it is necessary
to delete the last node and immediately afterwards, to set the next pointer of the previous
node to NULL (it is now the new last node).

Page 39
 ITec 2052- Data Structure and Algorithms

1. Look at the start pointer. If it is NULL, then the list is empty, so print out a "No nodes
to delete" message.
2. Make temp1 point to whatever the start pointer is pointing to.
3. If the next pointer of what temp1 indicates is NULL, then we've found the last node
of the list, so jump to step 7.
4. Make another pointer, temp2, point to the current node in the list.
5. Make temp1 point to the next item in the list.
6. Go to step 3.
7. If you get this far, then the temporary pointer, temp1, should point to the last item in
the list and the other temporary pointer, temp2, should point to the last-but-one
item.
8. Delete the node pointed to by temp1.
9. Mark the next pointer of the node pointed to by temp2 as NULL - it is the new last
node.

Let's try it with a rough drawing. This is always a good idea when you are trying to
understand an abstract data type. Suppose we want to delete the last node from this list:

Firstly, the start pointer doesn't point to NULL, so we don't have to display a "Empty list,
wise guy!" message. Let's get straight on with step2 - set the pointer temp1 to the same as
the start pointer:

The next pointer from this node isn't NULL, so we haven't found the end node. Instead, we
set the pointer temp2 to the same node as temp1

Page 40
 ITec 2052- Data Structure and Algorithms

and then move temp1 to the next node in the list:

Going back to step 3, we see that temp1 still doesn't point to the last node in the list, so we
make temp2 point to what temp1 points to
start_ptr

NULL

temp 2 temp1

and temp1 is made to point to the next node along:

Eventually, this goes on until temp1 really is pointing to the last node in the list, with temp2
pointing to the penultimate node:

Page 41
 ITec 2052- Data Structure and Algorithms

start_ptr

NULL

temp 2 temp1

Now we have reached step 8. The next thing to do is to delete the node pointed to by temp1

and set the next pointer of what temp2 indicates to NULL:

We suppose you want some code for all that! All right then ....
void delete_end_node()
{ node *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else
{ temp1 = start_ptr;
while (temp1->next != NULL)
{ temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL; } }
The code seems a lot shorter than the explanation!

Page 42
 ITec 2052- Data Structure and Algorithms

Now, the sharp-witted amongst you will have spotted a problem. If the list only contains
one node, the code above will malfunction. This is because the function goes as far as the
temp1 = start_ptr statement, but never gets as far as setting up temp2. The code above has to
be adapted so that if the first node is also the last (has a NULL next pointer), then it is
deleted and the start_ptr pointer is assigned to NULL. In this case, there is no need for the
pointer temp2:

void delete_end_node()
{ node *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else
{ temp1 = start_ptr;
if (temp1->next == NULL)// This part is new!
{ delete temp1;
start_ptr = NULL;
}
else
{ while (temp1->next != NULL)
{ temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL;
}
}

Example: -

1. Deleting node from front (first)

Delete a node from linked list is relatively easy. First, we create node *temp. Transfer the
address of *head to *temp. So *temp is pointed at the front of the linked list. We want to
delete the first node. So transfer the address of temp->next to head so that it now pointed to
the second node. Now free the space allocated for first node.

Page 43
 ITec 2052- Data Structure and Algorithms

node *temp; // create a temporary node

temp = (node*)malloc(sizeof(node)); // allocate space for node
temp = head; // transfer the address of 'head' to 'temp'
head = temp->next; // transfer the address of 'temp->next' to 'head'
free(temp);

Figure: Delete at first node

2. Deleting node from back (end)

The last node`s next of the linked list always pointed to NULL. So when we will delete the last
node, the previous node of last node is now pointed at NULL. So, we will track last node and
previous node of the last node in the linked list. Create temporary node * temp1 and
*old_temp.

// create a temporary node

node *temp1;
temp1 = (node*)malloc(sizeof(node)); // allocate space for node
temp1 = head; //transfer the address of
head to temp1
node *old_temp; // create a temporary node
old_temp = (node*)malloc(sizeof(node)); // allocate space for
node

while(temp1->next!=NULL) // go to the last node

{
old_temp = temp1; // transfer the address of 'temp1' to
'old_temp'
temp1 = temp1->next; // transfer the address of
'temp1->next' to 'temp1'
}

Page 44
 ITec 2052- Data Structure and Algorithms

Now node *temp1 is now pointed at the last node and *old_temp is pointed at the previous
node of the last node. Now rest of the work is very simple. Previous node of the last node
old_temp will be NULL so it become the last node of the linked list. Free the space allocated
for last lode.

old_temp->next = NULL; // previous node of the last node is null

free(temp1);

Figure: Delete at first last

3. Delete specified number of node

To delete a specified node in the linked list, we also require to find the specified node and
previous node of the specified node. Create temporary node * temp1, *old_temp and allocate
space for it. Take the input from user to know the number of the node.

node *temp1; // create a temporary node

temp1 = (node*)malloc(sizeof(node)); // allocate space for node
temp1 = head; // transfer the address of 'head' to 'temp1'

node *old_temp; // create a temporary node

old_temp = (node*)malloc(sizeof(node)); // allocate space for node
old_temp = temp1; // transfer the address of 'temp1' to 'old_temp'
cout<<"ENTER THE NODE NUMBER:";

Page 45
 ITec 2052- Data Structure and Algorithms

cin>>node_number; // take location

for( int i = 1 ; i < node_number ; i++ )
{
old_temp = temp1; // store previous node
temp1 = temp1->next; // store current node

}
Now node *temp1 is now pointed at the specified node and *old_temp is pointed at the
previous node of the specified node. The previous node of the specified node must connect
to the rest of the linked list so we transfer the address of temp1->next to old_temp->next. Now
free the space allocated for the specified node.
old_temp->next = temp1->next; // transfer the address of
'temp1->next' to 'old_temp->next'
free(temp1);

4. Sort nodes

It is just like ordinary array sorting First we create two temporary node node *temp1, *temp2
and allocate space for it. Transfer the address of first node to temp1 and address of second
node to temp2. Now check if temp1->data is greater than temp2->data. If yes then exchange the
data. Similarly, we perform this checking for all the nodes.

Page 46
 ITec 2052- Data Structure and Algorithms

node *temp1; // create a temporary node

temp1 = (node*)malloc(sizeof(node)); // allocate space for node

node *temp2; // create a temporary node

temp2 = (node*)malloc(sizeof(node)); // allocate space for node

int temp = 0; // store temporary data value

for( temp1 = head ; temp1!=NULL ; temp1 = temp1->next )

{
for( temp2 = temp1->next ; temp2!=NULL ; temp2 = temp2->next )
{
if( temp1->data > temp2->data )
{
temp = temp1->data;
temp1->data = temp2->data;
temp2->data = temp;
}
}
}

2.1 Doubly Linked Lists

That sounds even harder than a linked list! Well, if you've mastered how to do singly linked
lists, then it shouldn't be much of a leap to doubly linked lists

A doubly linked list is one where there are links from each node in both directions:

Page 47
 ITec 2052- Data Structure and Algorithms

You will notice that each node in the list has two pointers, one to the next node and one to
the previous one - again, the ends of the list are defined by NULL pointers. Also there is no
pointer to the start of the list. Instead, there is simply a pointer to some position in the list
that can be moved left or right.

The reason we needed a start pointer in the ordinary linked list is because, having moved on
from one node to another, we can't easily move back, so without the start pointer, we
would lose track of all the nodes in the list that we have already passed. With the doubly
linked list, we can move the current pointer backwards and forwards at will.

4.3.1 Creating Doubly Linked Lists

The nodes for a doubly linked list would be defined as follows:
struct node{
char name[20];
node *nxt; // Pointer to next node
node *prv; // Pointer to previous node
};
node *current;
current = new node;
current->name = "Fred";
current->nxt = NULL;
current->prv = NULL;
We have also included some code to declare the first node and set its pointers to NULL. It
gives the following situation:

Page 48
 ITec 2052- Data Structure and Algorithms

We still need to consider the directions 'forward' and 'backward', so in this case, we will
need to define functions to add a node to the start of the list (left-most position) and the
end of the list (right-most position).

4.3.2 Adding a Node to a Doubly Linked List

void add_node_at_start (string new_name)
{ // Declare a temporary pointer and move it to the start
node *temp = current;
while (temp->prv != NULL)
temp = temp->prv;
// Declare a new node and link it in
node *temp2;
temp2 = new node;
temp2->name = new_name; // Store the new name in the node
temp2->prv = NULL; // This is the new start of the list
temp2->nxt = temp; // Links to current list
temp->prv = temp2;
}

void add_node_at_end ()
{ // Declare a temporary pointer and move it to the end
node *temp = current;
while (temp->nxt != NULL)
temp = temp->nxt;
// Declare a new node and link it in
node *temp2;
temp2 = new node;
temp2->name = new_name; // Store the new name in the node
temp2->nxt = NULL; // This is the new start of the list
temp2->prv = temp; // Links to current list
temp->nxt = temp2;
}
Here, the new name is passed to the appropriate function as a parameter. We'll go through
the function for adding a node to the right-most end of the list. The method is similar for
adding a node at the other end. Firstly, a temporary pointer is set up and is made to march
along the list until it points to last node in the list.

Page 49
 ITec 2052- Data Structure and Algorithms

Start_Ptr

After that, a new node is declared, and the name is copied into it. The nxt pointer of this
new node is set to NULL to indicate that this node will be the new end of the list.
The prv pointer of the new node is linked into the last node of the existing list.
The nxt pointer of the current end of the list is set to the new node.

3.3.3. Deleting a Node from a Doubly Linked List:

Let us assume that the list having at least one node. Then, the procedure for delete a node
from the doubly linked list as follows,

Void delete_dl()

node *temp;

if (start_ptr==NULL)

cout<< “ The list is empty”;

else

start_ptr=temp;

delete *temp;

start_ptr =temp->next; // The starting becomes NULL

Page 50
 ITec 2052- Data Structure and Algorithms

Trees

5.0 Introduction:

A tree is a set of nodes and edges that connect pairs of nodes. It is an abstract model of a
hierarchical structure. Rooted tree has the following structure:
 One node distinguished as root.
 Every node C except the root is connected from exactly other node P. P is C's parent,
and C is one of C's children.
 There is a unique path from the root to the each node.
 The number of edges in a path is the length of the path.

5.1 Tree Terminology:

Let us consider the following tree structure,

Page 51
 ITec 2052- Data Structure and Algorithms

H I J

K L M

Full binary tree: a binary tree where each node has either 0 or 2 children.

Balanced binary tree: a binary tree where each node except the leaf nodes has left and right
children and all the leaves are at the same level.

Complete binary tree: a binary tree in which the length from the root to any leaf node is
either h or h-1 where h is the height of the tree. The deepest level should also be filled from
left to right.

Binary search tree (ordered binary tree) : a binary tree that may be empty, but if it is not
empty it satisfies the following.
 Every node has a key and no two elements have the same key.
 The keys in the right subtree are larger than the keys in the root.
 The keys in the left subtree are smaller than the keys in the root.
 The left and the right subtrees are also binary search trees.

Page 52
 ITec 2052- Data Structure and Algorithms

5.2 Data structure of Binary Tree:

DataModel *RootDataModelPtr=NULL;
5.3Operation on Binary Tree:

Consider the following definition of binary search tree.

struct Node
{
int Num;
Node * Left, *Right;
};
Node *RootNodePtr=NULL;

5.3.1 Insertion:
When a node is inserted the definition of binary search tree should be preserved. Suppose
there is a binary search tree whose root node is pointed by RootNodePtr and we want to
insert a node (that stores 17) pointed by InsNodePtr.

Page 53
ITec 2052- Data Structure and Algorithms

Page 54
ITec 2052- Data Structure and Algorithms

Page 55
 ITec 2052- Data Structure and Algorithms

5.3.2 Traversing:
Binary search tree can be traversed in three ways.
a. Pre order traversal - traversing binary tree in the order of parent, left and right.
b. Inorder traversal - traversing binary tree in the order of left, parent and right.
c. Postorder traversal - traversing binary tree in the order of left, right and parent.

Page 56
 ITec 2052- Data Structure and Algorithms

5.4 Applications for Binary Tree Traversal:

Page 57
ITec 2052- Data Structure and Algorithms

Page 58
 ITec 2052- Data Structure and Algorithms

5.5 Searching:

Page 59
 ITec 2052- Data Structure and Algorithms

5.6 Deletion:

Page 60
ITec 2052- Data Structure and Algorithms

Page 61
ITec 2052- Data Structure and Algorithms

Page 62
ITec 2052- Data Structure and Algorithms

Page 63
ITec 2052- Data Structure and Algorithms

Page 64
ITec 2052- Data Structure and Algorithms

Page 65
ITec 2052- Data Structure and Algorithms

Page 66
ITec 2052- Data Structure and Algorithms

Page 67
 ITec 2052- Data Structure and Algorithms

Graph Data Structure

Mathematical graphs can be represented in data structure. We can represent a graph

using an array of vertices and a two-dimensional array of edges. A graph data
structure is a collection of nodes that have data and are connected to other nodes.
Let's try to understand this by means of an example. On facebook, everything is a
node. That includes User, Photo, Album, Event, Group, Page, Comment, Story,
Video, Link,
Note...anything that has data is a node.
Every relationship is an edge from one node to another. Whether you post a photo,
join a group, like a page etc., a new edge is created for that relationship.

All of facebook is then, a collection of these nodes and edges. This is because
facebook uses a graph data structure to store its data.
More precisely, a graph is a data structure (V,E) that consists of

• A collection of vertices V
• A collection of edges E, represented as ordered pairs of vertices (u,v)

Page 68
 ITec 2052- Data Structure and Algorithms

In the graph,
V = {0, 1, 2, 3}

E = {(0,1), (0,2), (0,3), (1,2)}

G = {V, E}

Graph Terminology

• Vertex − each node of the graph is represented as a vertex. In the following

example, the labeled circle represents vertices. Thus, A to G are vertices. We
can represent them using an array as shown in the following image. Here A
can be identified by index 0. B can be identified using index 1 and so on.
• Edge − Edge represents a path between two vertices or a line between two
vertices. In the following example, the lines from A to B, B to C, and so on
represents edges. We can use a two-dimensional array to represent an array as
shown in the following image. Here AB can be represented as 1 at row 0,
column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations
as 0.
• Adjacency − Two node or vertices are adjacent if they are connected to each
other through an edge. In the following example, B is adjacent to A, C is
adjacent to B, and so on.
• Path − Path represents a sequence of edges between the two vertices. In the
following example, ABCD represents a path from A to D.
• Directed Graph: A graph in which an edge (u,v) doesn't necessary mean that
there is an edge (v,

Page 69
 ITec 2052- Data Structure and Algorithms

u) as well. The edges in such a graph are represented by arrows to show the
direction of the edge.
• Labelled graph or weighted graph A graph is said to be labelled if every edge in
the graph is assigned some data. In a weighted graph, the edges of the graph
are assigned some weight or length. The weight of an edge denoted by w(e) is
a positive value which indicates the cost of traversing the edge. Figure shows
a weighted graph.
• Loop An edge that has identical end-points is called a loop. That is, e = (u, u).
Size of a graph The size of a graph is the total number of edges in it.

Page 70
 ITec 2052- Data Structure and Algorithms

Basic Operations
Following are basic primary operations of a Graph −

• Add Vertex − Adds a vertex to the graph.

• Add Edge − Adds an edge between the two vertices of the graph.
Display Vertex − Displays a vertex of the graph.
• Check if element is present in graph
• Graph Traversal
• Finding path from one vertex to another

Graph Representation
Graphs are commonly represented in two ways: They are:
1. Sequential representation by using an adjacency matrix.
2. Linked representation by using an adjacency list that stores the neighbors of a
node using a linked list.

1. Adjacency Matrix
An adjacency matrix is 2D array of V x V vertices. Each row and column
represent a vertex. If the value of any element a[i][j] is 1, it represents that
there is an edge connecting vertex i and vertex j.
The adjacency matrix for the graph we created above is

Page 71
 ITec 2052- Data Structure and Algorithms

Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0);
making the adjacency matrix symmetric about the diagonal.
Edge lookup (checking if an edge exists between vertex A and vertex B) is extremely
fast in adjacency matrix representation but we have to reserve space for every
possible link between all vertices (V x V), so it requires more space.

2. Adjacency List
An adjacency list represents a graph as an array of linked list.
The index of the array represents a vertex and each element in its linked list
represents the other vertices that form an edge with the vertex.
The adjacency list for the graph we made in the first example is as follows:

An adjacency list is efficient in terms of storage because we only need to store the
values for the edges. For a graph with millions of vertices, this can mean a lot of
saved space. DFS algorithm

Traversal means visiting all the nodes of a graph. Depth first traversal or Depth first
Search is a recursive algorithm for searching all the vertices of a graph or tree data
structure.

Page 72
 ITec 2052- Data Structure and Algorithms

DFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two
categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the
visited list to the top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

DFS example

Let's see how the Depth First Search algorithm works with an example. We
use an undirected graph with 5 vertices.

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list
and putting all its adjacent vertices in the stack.

Page 73
 ITec 2052- Data Structure and Algorithms

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent
nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of

the stack and visit it.

Page 74
 ITec 2052- Data Structure and Algorithms

After we visit the last element 3, it doesn't have any unvisited adjacent nodes,
so we have completed the Depth First Traversal of the graph.

Page 75
 ITec 2052- Data Structure and Algorithms

Breadth first search (BFS)

Traversal means visiting all the nodes of a graph. Breadth first traversal or
Breadth first Search is a recursive algorithm for searching all the vertices of a
graph or tree data structure.

BFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two
categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding
cycles.

The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of a queue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't
in the visited list to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that
we cover every vertex, we can also run the BFS algorithm on every node

BFS example

Let's see how the Breadth First Search algorithm works with an example. We
use an undirected graph with 5 vertices.

Page 76
 ITec 2052- Data Structure and Algorithms

We start from vertex 0, the BFS algorithm starts by putting it in the Visited list
and putting all its adjacent vertices in the stack.

Next, we visit the element at the front of queue i.e. 1 and go to its adjacent
nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of

the queue and visit 3, which is at the front of the queue.

Page 77
 ITec 2052- Data Structure and Algorithms

Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is
already visited. We visit it.

Since the queue is empty, we have completed the Depth First Traversal of
the graph.

Page 78