Subject : BCS-303 Data Structure & Algorithms

Class : SYBSc (CS) – Semester III

Lecturer : Ms. Madhvi V. Oza
Unit I : Introduction
 Data Structure ---------------------------------------------------------------------------------------------------- 01
 Basic Terminology ---------------------------------------------------------------------------------------------- 02
 Elementary Data Organization -------------------------------------------------------------------------- 04
 Data Structure Operation ---------------------------------------------------------------------------------- 10
 Algorithm Complexity ---------------------------------------------------------------------------------------- 11

 Data Structure :
A data structure is a particular way of organizing data in a computer so that it can be used
efficiently. It is a way of collecting and organizing data in such a way that we can perform
operations on that data in an effective way.
For example, we can store a list of items having the same data-type using the array data
structure.
It represents the knowledge of data to be organized in memory. It should be designed &
implemented in such a way that it reduces the complexity and increases the efficiency.
Data structures are often classified by their characteristics. Some of those characteristics
are:

 Linear or non-linear: This characteristic describes whether the data items are
arranged in chronological sequence, such as with an array, or in an unordered
sequence, such as with a graph.

 Homogeneous or non-homogeneous: This characteristic describes whether all data

items in a given repository are of the same type or of various types.

 Static or dynamic: This characteristic describes how the data structures are
compiled. Static data structures have fixed sizes, structures and memory locations
at compile time. Dynamic data structures have sizes, structures and memory
locations that can shrink or expand depending on the use.

1
  Basic Terminologies :
Explaining or defining the basic terms used in data structures is called basic terminology.
The basic terms are described in brief as below :
1) Data : Data can be defined as value or collection of values, facts or figures. Data is a
raw and unorganized fact that is required to be processed to make it meaningful.
For e.g. Marks of a student can be data.

2) Information : When data is processed, organized, structured or presented in a given

context so as to make it useful, it is called information. In short, Processed data is
Information.
For e.g. Average Marks of the whole class is information.

3) Data Item : A Data Item refers to a single unit of values. A data item that does not
have subordinate data items i.e. that cannot be further sub-divided is called an
elementary item.
For e.g. Roll Number, Age etc.

4) Group Item : A data item that is composed of one or more subordinate data items is
called a group item, i.e. data item that can be further sub-divided is called a group
item.
For e.g. Name – First_Name, Middle_name, Last_name.

5) Entity : An entity is a real-world object that has certain attributes or properties

which may be assigned values.
For e.g. Student, Employee, Chalk, etc.

6) Entity-set : Entities with similar attributes form an entity set.

For e.g. All students in a class.

7) Field : A field is a single unit of information representing an attribute of an entity.

The term fields refers to columns in a table.
For e.g. Roll_no, Name, Class,etc.

8) Record : A record is a collection of field values of a given entity i.e. A single row in a
table is called a record. It is also called a complete set of information of an entity.
For e.g. A student’s Roll_no, Name, Class.

9) File : File is the collection of records of the entities in a given entity set. A collection
of data or information that has a name, called the filename.
2
10) Primary Key : A primary key is a field in a table which uniquely identifies each
row/record in a database table. Primary keys must contain unique values.

For e.g. Roll_No,etc.

3
  Elementary Data Organization :
Organizing each data element at proper memory locations for efficient storage and
retrieval is called Elementary Data Organization. To organize data in an efficient way,
some data structures are used.
The different types of data structures used in a computer system are :

Fig. Types of Data Structure

Data Structures are divided into two types as Primitive and Non-Primitive, as :

1) Primitive Data Structures :

 The data structures for which a language has built-in support are known as Built-
in Data types or Primitive data structures.
 Primitive data are only single values.
 For e.g. Integer, Float values, Boolean, Character, Pointer.
 The size and type of variable values are pre-specified, and it has no additional
methods.

2) Non-Primitive Data Structures :

 The data structures that are derived from primary data types are known as non-
primitive.
 The non-primitive data structures are used to store the group of values. Non-
Primitive Data Structures are usually multiple values with a particular structure.
 For e.g. Array, structure, union, link list, stacks, queue etc.

4
 The size and type of variable values are not pre-specified, and it has additional
methods to perform certain operations.
 Non-Primitive Data Structures are divided into two categories as Linear and Non-
Linear Data Structures, as :

i. Linear Data Structures : Linear data structure arranges the data into a
sequence and follow some sort of order.
In a linear data structure, data elements are arranged in a linear order
where each member element is connected to its previous and next
element.
Such data structures are easy to implement as computer memory is also
sequential. In a linear data structure, memory is not utilized in an efficient
way.
Linear Data Structures are further sub-divided into two types as Static and
Dynamic, as :

a) Static : A static data structure is an organization or collection

of data in memory that is fixed in size. Memory size once allocated
cannot be reallocated later during run-time.
Static data structures are ideal for storing a fixed number of data
items.
For e.g. Arrays.

b) Dynamic : A dynamic data structure refers to an organization or

collection of data in memory that has the flexibility to grow or shrink
in size, enabling a programmer to control exactly how much
memory is utilized.
For e.g. Linked List, Stack, Queue.

ii. Non-Linear Data Structures : A non-linear data structure does not have
a fixed sequence to connect all its elements.
Each element can have multiple paths to connect to other elements. Non-
linear data structures uses memory very efficiently.
Non-linear data structures are not easy to traverse and needs multiple runs
to be traversed completely.
In non-linear data structure, data elements can be hierarchically connected
or are present at various levels.
For e.g. Tree, Graph.
5
Let us describe all types of data structures in brief as below :

1. Array : An array is a collection of items stored at contiguous memory locations.

Array is a container which can hold a fix number of items and these items should be
of the same type.
The basic terms used in array are :
 Element : Every item stored in an array is termed as an element.
 Index : Each memory location of an element in an array is denoted by a
numerical index which is used for identifying the element.
An array can be declared as :

Graphical representation :

2. Linked List : A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations. The elements in a linked list are linked using
pointers.
Linked list can be visualized as a chain of nodes, where every node points to the
next node
Each node is divided into two parts :
First part contains the data element i.e. Information/Data field and second part
contains the address of next node i.e. Next Pointer Field. The node that contains
the Null Pointer indicates the end of list, as :

6
 The entry point into a linked list is called the HEAD node or START node of the list.
It is the reference (pointer) to the first node.

3. Stack : Stack is an ordered list of similar data type. It is a linear list in which Insertion
and Deletion takes place only at one end, called TOP.
Stack is also called as LIFO [Last In First Out] or FILO [First In Last Out] data
structure.
For e.g. Stack of Dishes, Books, Cards, etc.
It is a simple data structure that allows adding and removing elements in a particular
order. Every time an element is added, it goes on the top of the stack and the only
element that can be removed is the element that is at the top of the stack, just like
a pile of objects.

Two pre-defined functions are used to insert and remove items from the stack, as:
push() is used to insert a new element in the stack, pop() is used to delete an
existing element from the list.
The simplest application of a stack is to reverse a word. You push a given word to
stack - letter by letter - and then pop letters from the stack.

4. QUEUE : A queue is a linear collection of objects that are inserted and removed
according to the First In First Out (FIFO) principle.
7
 Queue is a linear data structure where the first element is inserted from one end
called REAR and deleted from the other end called FRONT.
According to its FIFO structure, element inserted first will also be removed first.
The pre-defined functions to add an element into queue is called enqueue() and to
remove an element from queue is called dequeue().

Front pointer is used to get the first data item from a queue. Rear pointer is used
to get the last item from a queue.

5. Tree : A tree is a nonlinear hierarchical data structure that consists of nodes

connected by edges. Tree is a collection of elements called Nodes, where each node
can have single or multiple number of children.
The topmost node in a tree is called the root node. It does not have a parent. It
represents the parent & child nodes connected by edges.

The above figure represents structure of a tree. This tree has 2 subtrees, as :
A is a parent of B and C.
B is called a child of A and also parent of D, E, F.

8
6. GRAPH : A Graph is a non-linear data structure consisting of nodes and edges. A
graph G can be defined as an ordered set G(V, E) where, G = Graph, V = set of
Vertices[Nodes] & E = set of Edges[To connect nodes].

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Graphs are used to solve many real-life problems. Graphs are used to represent
networks, as telephone network or circuit network. Graphs are also used in social
networks like linkedIn, Facebook, etc.

9
  Data Structure Operations :
The data in the data structures are processed by certain operations. The basic operations
that are performed on data structures are as follows:

1. Traversing : Traversing is a process where each & every element of a particular

data structure is accessed atleast once for processing.
Accessing means visiting every element at least once, just to display them to the
user or perform an operation on all the elements.
For e.g. Printing all the array elements one by one.
Traversal is the most basic of the operations that can be performed on any data
structures.

2. Searching : Searching in data structure refers to the process of finding location

LOC of an element in a list. Searching is an operation or a technique that helps finds
the place of a given element or value in the list. Any search is said to be successful
or unsuccessful depending upon whether the element that is being searched is
found or not. Searching can be Linear or binary.

3. Inserting : Inserting is the process to insert one or more data elements into a data
structure. Based on the requirement, new element can be added at the beginning,
end or any given index.

4. Deleting : Deleting refers to removing an existing element from a data structure

and re-organizing all the elements accordingly.

5. Sorting : Sorting refers to the operation or technique of arranging and rearranging

sets of data in some specific order. Sorting is performed according to some key
value of each record. Sorting is one of the most important operations performed by
computers.

6. Merging : The process of combining elements of two data structures is

called merging. Merging operation is used to combine the data items of two sorted
files into a single file in sorted order.

10
  Algorithm Complexity :
Complexity of an algorithm is a measure of the amount of time and/or space required by
an algorithm for an input of a given size (n).
Algorithm complexity is a rough approximation of the number of steps, which will be
executed depending on the size of the input data. Complexity gives the order of steps
count, not their exact count.
Suppose X is an algorithm and n is the size of input data, the time and space used by the
algorithm X are the two main factors, which decide the efficiency of X.
 Time Factor − Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.
 Space Factor − Space is measured by counting the maximum memory space
required by the algorithm.
The complexity of an algorithm f(n) gives the running time and/or the storage space
required by the algorithm in terms of n as the size of input data.
1. Time Complexity : Time complexity of an algorithm represents the amount of time
required by the algorithm to run to completion. Time requirements can be defined as
a numerical function T(n), where T(n) can be measured as the number of steps,
provided each step consumes constant time.
For example, addition of two n-bit integers takes n steps. Consequently, the
total computational time is T(n) = c ∗ n, where c is the time taken for the addition of
two bits. Here, we observe that T(n) grows linearly as the input size increases.
2. Space Complexity : Space complexity of an algorithm represents the amount of
memory space required by the algorithm in its life cycle. The space required by an
algorithm is equal to the sum of the following two components −
 A fixed part that is a space required to store certain data and variables, that are
independent of the size of the problem. For example, simple variables and
constants used, program size, etc.
 A variable part is a space required by variables, whose size depends on the size of
the problem. For example, dynamic memory allocation, recursion stack space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed
part and S(I) is the variable part of the algorithm, which depends on instance
characteristic I. Following is a simple example that tries to explain the concept −
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

11
Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now,
space depends on data types of given variables and constant types and it will be
multiplied accordingly.

12