Classes and objects

Chapter – 4: Data Structures

Introduction
Data is a collection of raw facts that are calculated or manipulated by computers. Processed
data is called information.
Data structure: It is a specialized format for organizing and storing data.
Data representation: Computer memory is used to store the data which is required for
processing. This process is known as data representation. Data structure is a method of
storing data in memory so that it can be used efficiently.
The study of data structures deals with:
1. Logical or mathematical description of structure.
2. Implementation of structure on a computer.
3. Analysis of structure which includes determining amount of space in memory and
optimization of time taken for processing.
Classification of data structures
Data structures are divided into two as
1. Primitive
2. Non-primitive data structures
Primitive data structures:
Data structures that are directly operated upon by machine-level instructions are known as
primitive data structures.
The integers, real (float), logical data, character data, pointer and reference are primitive
data structures.

Operations on primitive data structures

The various operations that can be performed on primitive data structures are:
Create: Create operation is used to create a new data structure.
This operation reserves memory space for the program elements. It can be
carried out at compile time and run-time.
Destroy: Destroy operation is used to destroy or remove the data structures from the
memory space.
When the program execution ends, the data structure is automatically
destroyed and the memory allocated is eventually de-allocated.
C++ allows the destructor member function to destroy the object.
Select: Select operation is used by programmers to access the data within data structure.
This operation updates or alters data.
www.vidyasanskaar.com Page 1 of 22
 Classes and objects

Update: Update operation is used to change data of data structures.

Non primitive data structures:
 Non-primitive data structures are more complex data structures that are derived from
the primitive data structures.
Non-primitive data structures are classified as arrays, lists and files.
 Data structures under lists are classified as linear and non-linear data structures.
Linear data structure
 This data structure has homogenous elements, where, each element is referred by an
index.
 Example: Stack, Queues and Linked Lists
 Elements of linear data structures will have linear relationship between them with
sequential memory locations.
Non-linear data structure
 In non-linear data structure, a data item is connected to several other data items.
 Every data item is attached to several other data items in a way that is specific for
reflecting relationships.
 Examples: Trees and Graphs
Operations on Non-linear data structure
The basic operations on non-linear data structures are as follows:
 Traversal: The process of accessing each data item exactly once to perform any
operation is called traversing.
 Insertion: The process of adding a new data item into the given collection of data
items is called insertion.
 Deletion: The process of removing an existing data item from the given collection of
data items is called deletion.
 Searching: The process of finding the location of a data item in the given
collection of data items is called searching.
 Sorting: The process of arranging data items in ascending or descending order is
called sorting.
 Merging: The process of combining the data items of two structures to form a single
structure is called merging.
Arrays: An array is a collection of homogeneous data items.
Types of Arrays:
 One-dimension
 Two-dimensional Array
 Multi-dimensional array

www.vidyasanskaar.com Page 2 of 22
 Classes and objects

One-dimension Array
An array with only one subscript is called one-dimensional array.
Syntax: data-type Array-name [size];
Size of the array in memory
The size of the array in memory is given by:
Total size = Length * size of data type
For example, int a[10];
Total size = 10 x 2bytes = 20bytes
Length of the array: Length= UB – LB + 1. Here, UB is the largest index,
called the upper bound

LB is the smallest index, called the lower bound.

Note that, Length = UB when LB = 1.

Representation of Linear Arrays in memory:

 Let A is a linear array in the memory of the computer.

 The elements of the array are stored in successive memory locations.
 The computer does not need to keep track of the address of every element of the
array.
 But needs to keep track only of the address of the first element denoted by Base(A)
and called the base address of A.
 Using base address the computer calculates the address of any element of A by the
following formula: LOC (A[k]) = Base (A) + w (k-lower bound)
Here, w is the number of words per memory cell for the array LA.

Consider the array A that contains 5 elements.

The position of the element A[3] is calculated as:

LOC(A[k]) = Base(A) + w(k – LB)
LOC(A[3]) = 2000 + 1(3 – 0)
= 2000 + 3
=2003

LOC(A[k]) = Base(A) + w(k – LB)

LOC(A[3]) = 2000 + 2(3 – 0)
= 2000 + 2(3)
=2006

www.vidyasanskaar.com Page 3 of 22
 Classes and objects

Operations on one-dimensional array

Traversing: Accessing each element of the array exactly once to do some operation.
Searching: Finding the location of an element in the array.
Sorting: Arranging the elements of the array in some order.
Insertion: Inserting an element into the array.
Deletion: Removing an element from the array.
Merging: Combining one or more arrays to form a single array.
Traversing a Linear Array
 Traversing is the process of visiting each subscript at least once from the beginning
to last element.
Algorithm: Let A be a linear array with LB and UB as lower bound and upper bound. This
algorithm traverses the array A by applying the operation PROCESS to each element of A.
1. for I = LB to UB
PROCESS A[I]
End of for
2. Exit
Searching an element
It refers to finding the location of the element in a linear array.
The most common methods are linear search and binary search.
Linear Search or Sequential search
 The element to be searched is compared with each element of the array one by one from
the beginning till end of the array.
Algorithm:A is the name of the array with N elements. ELE is the element to be searched.
This algorithm finds the location LOC where the search ELE element is
stored.
Step 1: LOC = -1
Step 2: for P = 0 to N-1
if( A[P] = ELE)
LOC = P
GOTO 3
End of if
End of for
Step 3: if(LOC >= 0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit
www.vidyasanskaar.com Page 4 of 22
 Classes and objects

Binary Search:

This method compares the search element with the middle element of the array.
If the comparison does not match, the element is searched either at the right-half of the
array or at the left-half of the array.
Algorithm: A is the sorted array with LB as lower bound and UB as the upper bound
respectively. Let B, E, M denote beginning, end and middle locations of the
segments of A.
Step 1: set B = 0, E= n-1 LOC= -1
Step 2: while (B <= E)
M= int(B+E)/2
if(ELE = A[M]
loc = M
GOTO 3
else
if(ELE <A[M])
E = M-1
else
B = M+1
End of while
Step 3: if(LOC >= 0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit
Insertion an element
 Insertion refers to inserting an element into the array.
 A new element can be inserted provided the array is large enough to accommodate the
new element.
Algorithm: A is the array with N elements. ITEM is the element to be inserted in the
position P.
Step 1: for I = N-1 downto P
A[I+1] = A[I]
End of for
Step 2: A[P] = ITEM
Step 3: N = N+1
Step 4: Exit

www.vidyasanskaar.com Page 5 of 22
 Classes and objects

Deleting an element from the array

 Deletion refers to removing an element into the array.
 When an element is to be deleted from a particular position, all the subsequent elements
are shifted into the lower order positions.
Algorithm: A is the array with N elements. ITEM is the element to be deleted in the
position
and it is stored into the variable Item.
Step 1: Item = A[P]
Step 2: for I = P to N-1
A[I] = A[I+1]
End of for
Step 2: N = N-1
Step 4: Exit
Sorting the elements
 Sorting is the arrangement of elements of the array in some order.
 There are various methods like bubble sort, shell sort, selection sort, quick sort, heap
sort, insertion sort etc.
Insertion Sort:
The first element of the array is assumed to be in the correct position. The next
element is considered as the key element and compared with the elements before the key
element and is inserted in its correct position.
Example: Consider the following list of numbers 70 30 40 10 80 stored in the consecutive
locations.

Step 1: Assuming 70 in correct position 30 is compared with 70. Since 30 is less the list
now is 30 70 40 10 8 0
Step 2: Now 40 is the key element. First it is compared with 30. Since it is greater it is then
compared with 70. Since 40 is less than 70 it is inserted before 70. The list now is
30 40 70 10 80
Step 3: Now 10 is the key element. First it is compared with 70. Since it is less it is
exchanged. Next it is compared with 40 and it is exchanged. Finally it is compared
with 30 and placed in the first position. The list now is 10 30 40 70 80
Step 4: Now 80 is the key element and compared with the sorted elements and placedin
the position. Since 80 is greater than 70 it retains its position.
Algorithm:Let A be an array with N unsorted elements. The following algorithm sorts the
elements in order.

Step 1: for I = 1 to N-1

Step 2: J=I
While ( J >= 1)

www.vidyasanskaar.com Page 6 of 22
 Classes and objects

If( A[J] < A[J-1])

Step 3: temp = A[J]
A[J] = A[J-1]
A[J-1] = temp
If end
J = J-1

While end
For end
Step 4: Exit

Two-dimensional arrays
An array with two subscripts is called two-dimensional array.
We logically represent the elements of two-dimensional array as rows and columns.
Representation of 2-dimensional array in memory
 Suppose A is the array of order m x n. To store m*n number of elements, we need m*n
memory locations.
 The elements should be in contiguous memory locations.
 There are two methods:
Row-major order
Column-major order
Row-major order
Let A be the array of order m x n. In row-major order, all the first-row elements are
stored in sequential memory locations and then all the second-row elements are stored and
so on.
Base(A) is the address of the first element. The memory address of any element
A[I][J] can be obtained by the formula
LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
where W is the number of words per memory location.
Column-major order
Let A be the array of order m x n. In column-major order, all the first-column
elements are stored in sequential memory locations and then all the second-column
elements are stored and so on.
Base(A) is the address of the first element. The memory address of any element
A[I][J] can be obtained by the formula
LOC(A[I][J]) = Base(A) + W[(I-LB) + m(J-LB)]
where W is the number of words per memory location.

www.vidyasanskaar.com Page 7 of 22
 Classes and objects

Example: Consider the array A of order 25 x 4 with base value 2000 and one word per
memory location. Find the address of A[12][3] in row-major order and column-major order.
Solution: Given Base(A) = 2000, m = 25, n=4
W = 1, I = 12, J = 3
Row-major order: LOC(A[I][J]) = Base(A) + W[n(I-1) + (J-1)]
LOC(A[12][3]) = 2000 + 1[4(12-1)+(3-1)]
= 2000 + 4(11 + 2)
= 2000 + 4(13)
= 2052

Column-major order: LOC(A[I][J]) = Base(A) + W[ (I-1) + m(J-1)]

LOC(A[12][3]) = 2000 + 1[(12-1)+25(3-1)]
= 2000 + 1(11 + 50)
= 2000 + 61
= 2061
Applications of arrays
1. Arrays are used to implement other data structures such as heaps, hash tables,
queues, stacks and strings etc.
2. Arrays are used to implement mathematical vectors and matrices.
3. Many databases include one-dimensional arrays whose elements are records.
Advantages of arrays
1. It is used to represent multiple data items of same type by using only single name.
2. It can be used to implement other data structures like linked lists, stacks, queues,
trees, graphs etc.
3. Two-dimensional arrays are used to represent matrices.
Disadvantages of arrays
1. We must know in advance that how many elements are to be stored in array.
2. Array is static structure. It means that array is of fixed size. The memory which is
allocated to array cannot be increased or reduced.
3. Since array is of fixed size, if we allocate more memory than requirement then the
memory space will be wasted. If we allocate less memory than requirement, then it
will create problem.
4. The elements of array are stored in consecutive memory locations. So insertions and
deletions are very difficult and time consuming.
STACKS
A stack is an ordered collection of items where the insertion of an item and the removal of
an existing item always take place at the same end.

www.vidyasanskaar.com Page 8 of 22
 Classes and objects

This end is commonly referred to as the “top”. The end opposite to top is the base.

The most recently added item is the one that is in position to be removed first. This ordering
principle is sometimes called LIFO, last-in first-out.

Representation of stacks in memory

The representation of a stack in the memory can be done in two ways.
Static representation using arrays
Dynamic representation using linked lists

Array Representation of a Stack

Stack can be represented using a one-dimensional array.
A block of memory is allocated to store the items to the full capacity of the stack.
The items into the stack are stored in a sequential order from the first location of the
memory block.
A pointer TOP contains the location of the top element of the stack.
A variable MAXSTK contains the maximum number of elements that can be stored in the
stack.
The condition TOP = MAXSTK indicates that the stack is full and TOP = NULL indicates
that the stack empty.
Linked representation of stacks

 We can increase the size of the array at runtime by creating a new node.
 So it is better to implement stack data structure using Linked list.

Inserting a node
Insertion operation refers to Inserting an element into stack.
We create a new node and insert an element into the stack.
To follow LIFO principle, a node should be inserted at the end of the linked list.
Deletion
 Deletion operation of an element refers to deleting a node from the Linked list.
 Deletion can be done by deleting the top-most item from the stack.
 So to delete an item, the last node of the linked list is deleted.
Operation Stack
The stack operations are given below:
stack(): Creates a new stack that is empty. It needs no parameters and returns an
empty stack.

push(item):Adds a new item to the top of the stack. It needs the item and returns
nothing.

www.vidyasanskaar.com Page 9 of 22
 Classes and objects

pop(): Removes the top item from the stack. It needs no parameters and returns
the item. The stack is modified.
peek(): Returns the top item from the stack but does not remove it. It needs no
parameters. The stack is not modified.
isEmpty(): Tests whether the stack is empty. It needs no parameters and returns a
Boolean value.
size(): Returns the number of items on the stack. It needs no parameters and
returns an integer.

Algorithm for PUSH Operation

Step 1: If TOP = N-1 then [check overflow]
PRINT “Stack is full”
Exit
End of If
Step 2: TOP = TOP + 1 [Increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return

Algorithm for POP Operation

Step 1: If TOP = NULL then [check underflow]

PRINT “Stack is empty”
Exit
End of If
Step 2: ITEM = STACK[TOP] [Copy the top element]
Step 3: TOP = TOP – 1 [Decrement the top]
Step 4: Return

Application of Stacks
 To reverse a word.
 “Undo” mechanism in text editors; this operation is accomplished by keeping all text
changes in a stack.
 Backtracking: This is a process when you need to access the most recent data
element in a series of elements. Back-tracking simply means popping a next choice
from the stack.
 Language processing:
Space for parameters and local variables is created internally using a stack.
Compiler’s syntax check for matching braces is implemented by using stack.
Support for recursion
 Conversion of decimal number into binary
 To solve tower of Hanoi
 Expression evaluation and syntax parsing
 Conversion of infix expression into pre-fix and post-fix.

www.vidyasanskaar.com Page 10 of 22
 Classes and objects

 Rearranging railroad cars

 Quick sort
 Stock span problem
 Runtime memory management

Queues: A queue is an ordered collection of items where the addition of new items and the
removal of existing items always take place at different ends.
Insertion and deletion is performed according to the first-in first-out (FIFO) principle.
In a queue only two operations are allowed enqueue and dequeue.
Enqueue means to insert an item into the back of the queue and dequeue means
removing the front item.
Queue is also called as FIFO list, i.e. First-In-First-Out. Here insertions are limited to
one end of the list called the rear, whereas deletions are limited to other end called as
front.
Types of queues:
Queue can be of four types:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended queue)
Simple Queue: In Simple queue insertion occurs at the rear end of the list, and deletion
occurs at the front end of the list.
Circular Queue: A circular queue is a queue in which all nodes are treated as circular such
that the last node follows the first node.

Priority Queue: A priority queue is a queue that contains items that have some preset
priority. An element can be inserted or removed from any position depending on some
priority.

Dequeue (Double Ended queue):

It is a queue in which insertion and deletion takes place at both the ends.

Operations on queue

The queue operations are given below.

Queue(): creates a new queue that is empty. It needs no parameters and returns an empty
queue.
enqueue(item): adds a new item to the rear of the queue. It needs the item and returns
nothing. This operation is generally called as push.
dequeue(): removes the front item from the queue. It needs no parameters and returns
the item. The queue is modified. This operation is generally called as pop.
www.vidyasanskaar.com Page 11 of 22
 Classes and objects

isEmpty(): tests to see whether the queue is empty. It needs no parameters and returns a
Boolean value.
size(): returns the number of items in the queue. It needs no parameters and returns
an integer.

Memory representation of a queue using arrays

 Queue is represented in memory linear array.

 Let QUEUE linear queue.
 Two pointer variables called FRONT and REAR are maintained. FRONT contains the
location of the element to be removed and REAR contains location of the last element
inserted.
 The condition FRONT = NULL indicates that the queue is empty and the condition
REAR = N -1 indicates that the queue is full.

Memory representation of a queue using linked list

Queues are also represented using linked lists. In queues an item should be inserted
from rear end and an item should be removed from the front end. The pointer front contains
location of the first node of the linked list and another pointer rear contains location of the
last node.
Inserting an item into the queue (Enqueue)
Algorithm:
Step 1: If REAR = N-1 Then [Check for overflow]
PRINT “Overflow”
Exit
Step 2: If FRONT = NULL Then [Check whether QUEUE is empty]
FRONT = 0
REAR = 0
Else
REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

Algorithm for deletion

Step 1: If FRONT = NULL Then [Check whether QUEUE is

empty]
PRINT “Underflow”
Exit
Step 2: ITEM = QUEUE[FRONT]
Step 3: If FRONT = REAR Then [If QUEUE has only one
element]

www.vidyasanskaar.com Page 12 of 22
 Classes and objects

FRONT = NULL
REAR = NULL
Else
FRONT = FRONT + 1 [Increment FRONT pointer]
Step 3: Return

4.7.5 Applications of queues

 Simulation
 Various features of operating system
 Multi-programming platform systems
 Different type of scheduling algorithm
 Round robin technique or Algorithm
 Printer server routines
 Various applications software is also based on queue data structure
 Operating systems often maintain a queue of processes that are waiting for a
particular event to occur.
LINKED LISTS

Disadvantage of using arrays:

Arrays cannot be easily extended or reduced to fit the data set.
During insertion, the array elements are shifted into higher order memory locations.
During deletion, elements ate shifted into lower order memory locations.
Advantages of linked list over array:
Linked Lists addresses these limitations of arrays. The linked list uses dynamic memory
allocations.
In linked list, the nodes need not necessarily represent a set of consecutive memory
locations (or contiguous memory locations).
Linked list
A linked list is a linear collection of data elements called nodes and the linear order is given
by means of pointers.
Each node contains two fields: the data field and link field.
The data field contains the information and the link field contains the address of the next
node in the list.
The link field of the last node contains null.
Types of linked lists
There are three types of linked lists.
1. Singly linked list (SLL)
2. Doubly linked list (DLL)
3. Circular linked list (CLL)
Singly linked list
www.vidyasanskaar.com Page 13 of 22
 Classes and objects

There is only one link field in each node.

A singly linked list contains two fields in each node – the data field and link field.
Circular linked lists
The link field of the last node contains the address of the first node first node.
In a circular linked list, it is possible to reach any node from any other node.

Doubly linked lists

Each node is points both to the next node and also to the previous node.
In doubly linked list each node contains three parts – FORW, BACK and INFO.
BACK: It is a pointer field containing the address of the previous node.
FORW: It is a pointer field that contains the address of the next node.
INFO: It contains the actual data.
In the first node, if BACK contains NULL and FORW field of the last node contains
NULL.

Operations on linked lists:

The operations that are performed on linked lists are:
 Creating a linked list
 Traversing a linked list
 Inserting an item into a linked list
 Deleting an item from the linked list
 Searching an item in the linked list
 Merging two or more linked lists
Creating a linked list
We start with a node and create nodes, link to the starting node sequentially.
The pointer START contains the location of the first node and the link field of the last
node contains NULL.
Elements can be inserted anywhere in the linked list and any node can be deleted.
The nodes of a linked list can be created by the following structure declaration.
struct Node struct Node
{ {
int data; OR int data;
Node *link; Node *link;
} }*node1, *node2;
Node *node1, *node2;

Self-addressing pointer: The link field contains a pointer variable that refers the same
node structure.
The above declaration creates two variable structures, node1 and node2.

www.vidyasanskaar.com Page 14 of 22
 Classes and objects

Each structure will be taken as node, another node cannot be inserted.

Also, there may be cases where the memory needs of a program can only be determined
during runtime.
To do this, programs need to dynamically allocate memory, for which the C++ language
use the operators new and delete.

Operator new and new[]

Memory is dynamically allocated using operator new. Operator new is followed by a
data type specifier.
If a sequence of elements is required, the number is enclosed within square brackets.
The operator new returns a pointer to the beginning of the new block of memory
allocated.
Syntax: pointer = new datatype;
pointer = new datatype [number_of_elements]

Example 1: int *p;

p = new int;

Example 2: int *tmp;

tmp = new int [5];

Operator delete and delete[]

If memory is no longer needed, it can be freed so that the memory becomes available
again for other requests of dynamic memory. For this purpose the operator delete is
used.
Syntax: delete pointer;
delete [] pointer;

The argument to delete shall be the pointer to a memory block.

We can allocate memory space to the linked list as follows:

Node *newNode; //newNode is declared as pointer of type Node

p = new Node; //Allocate memory space to Node and return its address
to p
data(p) = num;
link(p) = NULL;
Traversing a linked list
Traversing is the process of accessing each node of the linked list exactly once to
perform some operation.
To traverse a linked list, steps to be followed are:
1. Move to the first node.
2. Fetch the data from the node and perform the required operation.
www.vidyasanskaar.com Page 15 of 22
 Classes and objects

3. Advance the pointer to the next node.

4. Repeated Step 2 and step 3 until all the nodes are visited.

Algorithm
Step 1: p = START [Initialize p to first node]
Step 2: while p != NULL
Step 3: PROCESSdata(p) [Fetch the data]
Step 4: p = link(p) [Advance p to next node]
Step 5: End of while
Step 6: Return

Memory allocation to a linked list

To insert a node to the linked list, the deleted node should be inserted into the linked list.
The operating system of the computer maintains a special list called avail list that
contains only the unused deleted nodes.
Whenever a node is deleted from the linked list, its memory is added to the avail list and
whenever a node is to be inserted into the linked list, a node is deleted from the avail list
and is inserted into the linked list.
Avail list is also called as the free-storage list or free-pool.
Inserting a node into the linked list
A node can be inserted into the linked list only if there are free nodes available in the
avail list.
Accordingly, there are three types of insertions.
1. Inserting a node at the beginning of the linked list
2. Inserting a node at the given position.
3. Inserting a node at the end of the linked list
Inserting a node at beginning of the linked list
Start is pointer that contains the memory address of the first node.
To insert an item into the linked list, the following procedure is used.
1. Create a new node.
2. Fill data into the data field of the new node.
3. Mark its next pointer field as null.
4. Attach this newly created node to start.
5. Make the new node as the first node.

Algorithm (inst-beg):
1. P  new node;
2. Data(p)  num;
3. Link(p)  START
www.vidyasanskaar.com Page 16 of 22
 Classes and objects

4. START  P
5. RETURN

Inserting a node at the end of the linked list

To insert at the end, we have to traverse the liked list to know the address of the last node.

Algorithm (inst-end)
1. START
2. [Identify the last node in the list]
a. p  START
b. while p ≠ NULL
p next(p)
while end
3. N  new Node [Create new node copy the address to the pointer N]
4. data(N) item
5. link(N)  NULL
6. link(p)  N
7. RETURN
Inserting a node at a given position

The following procedure inserts a node at the given position.

Algorithm (INST-POS): This algorithm inserts item into the linked list at the given position.

1. START
2. count  0
p1  START
3. while (p1 != NULL)
count count +1
p1  link(p1)
while end
4. if (pos = 1)
call function INST-BEG()
else
if (pos = count +1)
call function INST-END()
else
if( pos<= count)
p1  START
for i = 1;i <= pos; i++)
p1  next(p1)
for end
www.vidyasanskaar.com Page 17 of 22
 Classes and objects

[create] p2  new node

data(p2)  item
link(p2)  link(p1)
link(p1)  p2
else
PRINT “ Invalid position “
5. RETURN

Garbage collection
The operating system of the computer periodically collects all the deleted space into the
free-storage list. This technique of collecting deleted space into free-storage list is called as
garbage collection.
Deleting an item from the linked list
The deletion operation is classified into three types:
1. Deletion of the first node
2. Deletion of the last node
3. Deletion of the node at the given position
Underflow
If we try to delete a node from the linked list which is empty, the condition is called
as underflow.
Deletion of the first node
We can easily delete the first node of the linked list by changing the START to point to
the second node of the linked list.
If there is only one node in the liked list, the START can be stored with NULL.
Algorithm (DELE-BEG):
1. START
2. p START
3. PRINT data(p)
4. START link(p)
5. free(p)
6. RETURN
Deleting a node at the end
To delete the last node, we should find location of the second last node.
By assigning NULL to link field of the second last node, last node of the linked list can
be deleted.
Algorithm (DELE-END)
1. START
2. p2 START
3. while ( link(p2) != NULL)
p1  p2
p2 link(p2)
while end

www.vidyasanskaar.com Page 18 of 22
 Classes and objects

4. PRINT data(p2)
5. link(p1)  NULL
Free(p1)
6. STOP

Deleting a node at the given position

To delete a node at the given position, the following procedure is used.
1. Find location of the node to be deleted and the previous node.
2. Delete the node by changing the location of the previous node of the node to be
deleted to the next node of the node to be deleted.
Algorithm (DELE-POS)

1. START
2. count 0
p1  START
3. while(p1 != NULL)
count = count +1
p1 link(p1)
while end
4. if(pos = 1)
CALL DELE-BEG()
else
if(pos = count)
CALL DELE-END()
else
if(pos<= count)
p2  START
for i = 1 to pos
p1  p2
p2 link(p2)
for end
PRINT data(p2)
link(p1) link(p2)
free(p2)
else PRINT “Invalid position”
5. RETURN

Non-linear data structure

A non-linear data structure is a data structure in which a data item is connected to

several other data items, so that a given data item has the possibility to reach one-or-
more data items.
The data items in a non-linear data structure represent hierarchical relationship. Each
data item is called a node.
www.vidyasanskaar.com Page 19 of 22
 Classes and objects

Examples of non-linear data-structures are Graphs and Trees.

Advantages: Uses memory efficiently as contiguous memory is not required for allocating
data items.
The length of the data items is not necessary to be known prior to allocation.
Disadvantage: Overhead of the link to the next data item.

TREES
A tree is a data structure consisting of nodes organized as a hierarchy - see figure.
Terminology
A node is a structure which may contain a value, a condition, or represent a separate
data structure.
Each node in a tree has zero or more child nodes
A node that above the child is called the parent node.
A node has at most one parent.
Nodes that do not have any children are called leaf nodes. They are also referred to as
terminal nodes.
The height of a node is the length of the longest downward path to a leaf from that node.
The height of the root is the height of the tree.
The depth of a node is the length of the path to its root (i.e., its root path).
The topmost node in a tree is called the root node. The root node will not have parent.
An internal node or inner node is any node of a tree that has child nodes and is thus not a
leaf node.
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.
Binary trees
The simplest form of tree is a binary tree.
A binary tree is a tree in which each node has at most two descendants - a node can have
just one but it can’t have more than two.
A binary tree consists of:
a. a node (called the root node) and
b. left and right sub-trees.
Both the sub-trees are themselves binary trees.
Root Node
Node at the “top” of a tree - the one from which all operations on the tree begins.
The root node may not exist (a NULL tree with no nodes in it) or have 0, 1 or 2 children
in a binary tree.
Leaf Node Node at the “bottom” of a tree - farthest from the root.
Leaf nodes have no children.
www.vidyasanskaar.com Page 20 of 22
 Classes and objects

Complete Tree Tree in which each leaf is at the same distance from the root. i.e. all the
nodes have maximum two subtrees.
Height Number of nodes which must be traversed from the root to reach a leaf of a
tree.

GRAPHS
A graph is a set of vertices and edges which connect them.
A graph is a collection of nodes called vertices, and the connections between them,
called edges.
Undirected and directed graphs
When the edges in a graph have a direction, the graph is called a directed graph or
digraph, and the edges are called directed edges or arcs.
Neighbors and adjacency
A vertex that is the end-point of an edge is called a neighbor of the vertex, that is its
starting-point.
The first vertex is said to be adjacent to the second.
The diagram shows a graph with 5 vertices and 7 edges.
The edges between A and D and B and C are pairs that make a bidirectional connection,
represented here by a double-headed arrow.
Important Questions:
1. What are data structures?
2. What is primitive Data structure?
3. What is Non – Primitive Data structure?
4. What is stack?
5. What is queue?
6. How are data structure classified?
7. Mention various operation performed ?
8. Mention the types of linked list.
9. Define the following with respect to binary tree
a. Root
b. Sub tree
c. Depth
d. Degree
10. Write an algorithm to insert an element in an away.
11. Write an algorithm to delete an element in an away.
12. Write an algorithm to Insert an element in to queue.
13. Write an algorithm for PUSH and POP operation of stack.
14. Write an algorithm to delete on element from the queue

www.vidyasanskaar.com Page 21 of 22
 Classes and objects

www.vidyasanskaar.com Page 22 of 22