UNIT 1
INTRODUCTION TO DS : SEARCHING AND SORTING
TOPIC 1 : BASIC CONCEPTS : INTRODUCTION TO DS
TOPIC 2 : CLASSIFICATION OF DS : LINEAR , NON-LINEAR
TOPIC 3 : OPERATIONS ON DATA STRUCTURES
TOPIC 4 : SEARCHING TECHNIQUES : LINEAR SEARCH
TOPIC 5 : BINARY SEARCH
TOPIC 6 : FIBONACCI SEARCH
TOPIC 7 : SORTING TECHNIQUES : QUICK SORT
TOPIC 8 : MERGE SORT
TOPIC 9 : HEAP SORT
TOPIC 1: BASIC CONCEPTS : INTRODUCTION TO DATA STRUCTURES
Data Structure is a branch of Computer Science. Data Structure is a particular way of storing and
organizing data in the memory of the computer so that these data can easily be retrieved and efficiently utilized in
the future when required. There are different basic and advanced types of data structures that are used in almost
every program or software system that has been developed. The data stored can be changed using various operations
like insertion, deletion, searching, sorting, etc.
DEFINITION : Data structures provide an easy way of organising, retrieving, managing, and storing data in a
computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks.
Data presentation must be easy to understand to the developer and user, to implement efficiently.
USES OF DATA STRUCTURES :
● Data structure modification is easy.
● It requires less time.
● Save storage memory space.
● Data representation is easy.
● Easy access to the large databases.
TOPIC 2 : CLASSIFICATION OF DATA STRUCTURES
We can classify Data Structures into two main categories. They are :
1. Primitive Data Structure
2. Non-Primitive Data Structure
Primitive Data Structures: The primitive data structures in C are also known as primitive data types. These are the
basic data structures that are already defined in the C language. These data types are also called Simple data types,
as they contain characters that can't be divided further. These data structures can be manipulated or operated directly
by machine-level instructions. Basic data types like Integer, Float, Character, and Boolean come under the Primitive
Data Structures.
Non-Primitive Data Structures: The non-primitive data structures in C are also known as the derived data
structures as they are derived from primitive data types. A large number of values can be stored using the
non-primitive data structures. These data structures can't be manipulated or operated directly by machine-level
instructions. The focus of these data structures is on forming a set of data elements either homogeneous (same data
type) or heterogeneous (different data types). The data stored can be changed using various operations like insertion,
deletion, searching, sorting, etc. They include data structures like arrays, trees and stacks.
The non-primitive data structures in C can further be divided into two categories. They are Linear and Non - Linear.
1. Linear Data Structures
2. Non-Linear Data Structures
,1. LINEAR DATA STRUCTURES: A data structure that preserves a linear connection among its data elements
is known as a Linear Data Structure. The arrangement of the data is done linearly, where each element consists of
the successors and predecessors except the first and the last data element. Based on memory allocation, the Linear
Data Structures are further classified into two types:
1. Static Data Structures: The data structures having a fixed size are known as Static Data Structures. The
memory for these data structures is allocated at the compiler time, and their size cannot be changed by the
user after being compiled; however, the data stored in them can be changed. Example : Array.
2. Dynamic Data Structures: The data structures having a dynamic size are known as Dynamic Data
Structures. The memory of these data structures is allocated at the run time, and their size varies during the
run time of the code. Example : Linked Lists, Stacks, and Queues.
TYPES OF LINEAR DATA STRUCTURES :
1. Arrays : An Array is a data structure used to collect multiple data elements of the same data type into one
variable. An Array is a list of elements where each element has a unique place in the list. The data elements of the
array share the same variable name; however, each carries a different index number called a subscript. We can
access any data element from the list with the help of its location in the list. Instead of storing multiple values of the
same data types in separate variable names, we could store all of them together into one variable. Thus, the key
feature of the arrays is that the data is stored in contiguous memory locations, making it possible for the users to
traverse through the data elements of the array using their indexes.
Arrays can be classified into different types:
1. One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
2. Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
3. Multidimensional Array: We can define Multidimensional Array as an Array of Arrays.
Multidimensional Arrays are not bounded to two indices or two dimensions as they can include as many
indices are per the need.
2. Linked Lists: A Linked List is used to store a collection of data elements dynamically. Data elements in this
data structure are represented by the Nodes, connected using links or pointers. Each node contains two fields, the
, information field consists of the actual data, and the pointer field consists of the address of the subsequent nodes in
the list. The pointer of the last node of the linked list consists of a null pointer, as it points to nothing.
Linked Lists can be classified into :
1. Singly Linked List: A Singly Linked List is the most common type of Linked List. Each node has data
and a pointer field containing an address to the next node.
2. Doubly Linked List: A Doubly Linked List consists of an information field and two pointer fields. The
information field contains the data. The first pointer field contains an address of the previous node, whereas
another pointer field contains a reference to the next node. Thus, we can go in both directions (backward as
well as forward).
3. Circular Linked List: The Circular Linked List is similar to the Singly Linked List. The only key
difference is that the last node contains the address of the first node, forming a circular loop in the Circular
Linked List.
3. Stack: A Stack is a Linear Data Structure that follows the LIFO (Last In, First Out) principle that allows
operations like insertion and deletion from one end of the Stack, i.e., Top. Stacks can be implemented with the help
of contiguous memory, an Array, and non-contiguous memory, a Linked List. Real-life examples of Stacks are piles
of books etc.,.
DIAGRAM :
Stack Operations:
● push(): When this operation is performed, an element is inserted into the stack.
● pop(): An element is removed from the top of the stack and is returned.
● top(): This will return the last inserted element that is at the top without removing it.
● size(): This will return the size of the stack i.e. the total number of elements present in the stack.
● isEmpty(): This operation indicates whether the stack is empty or not.
4. Queue: The Queue data structure follows FIFO (First In, First Out) principle. The insertion of an element in a
Queue is done at one end, and the removal is done at another or opposite end. The difference between stacks and
queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the
least recently added. Implementation of Queues can be done using Arrays, Linked Lists, or Stacks.
A good example of the queue is any queue of consumers for a resource where the consumer that came first is served
first.
Operations of the Queue :
1. Enqueue: The insertion or Addition of some data elements to the Queue is called Enqueue. The element
insertion is always done with the help of the rear/back pointer.
2. Dequeue: Deleting or removing data elements from the Queue is termed Dequeue. The deletion of the
element is always done with the help of the front pointer.
3. isFull(): Validates if the queue is full.
INTRODUCTION TO DS : SEARCHING AND SORTING
TOPIC 1 : BASIC CONCEPTS : INTRODUCTION TO DS
TOPIC 2 : CLASSIFICATION OF DS : LINEAR , NON-LINEAR
TOPIC 3 : OPERATIONS ON DATA STRUCTURES
TOPIC 4 : SEARCHING TECHNIQUES : LINEAR SEARCH
TOPIC 5 : BINARY SEARCH
TOPIC 6 : FIBONACCI SEARCH
TOPIC 7 : SORTING TECHNIQUES : QUICK SORT
TOPIC 8 : MERGE SORT
TOPIC 9 : HEAP SORT
TOPIC 1: BASIC CONCEPTS : INTRODUCTION TO DATA STRUCTURES
Data Structure is a branch of Computer Science. Data Structure is a particular way of storing and
organizing data in the memory of the computer so that these data can easily be retrieved and efficiently utilized in
the future when required. There are different basic and advanced types of data structures that are used in almost
every program or software system that has been developed. The data stored can be changed using various operations
like insertion, deletion, searching, sorting, etc.
DEFINITION : Data structures provide an easy way of organising, retrieving, managing, and storing data in a
computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks.
Data presentation must be easy to understand to the developer and user, to implement efficiently.
USES OF DATA STRUCTURES :
● Data structure modification is easy.
● It requires less time.
● Save storage memory space.
● Data representation is easy.
● Easy access to the large databases.
TOPIC 2 : CLASSIFICATION OF DATA STRUCTURES
We can classify Data Structures into two main categories. They are :
1. Primitive Data Structure
2. Non-Primitive Data Structure
Primitive Data Structures: The primitive data structures in C are also known as primitive data types. These are the
basic data structures that are already defined in the C language. These data types are also called Simple data types,
as they contain characters that can't be divided further. These data structures can be manipulated or operated directly
by machine-level instructions. Basic data types like Integer, Float, Character, and Boolean come under the Primitive
Data Structures.
Non-Primitive Data Structures: The non-primitive data structures in C are also known as the derived data
structures as they are derived from primitive data types. A large number of values can be stored using the
non-primitive data structures. These data structures can't be manipulated or operated directly by machine-level
instructions. The focus of these data structures is on forming a set of data elements either homogeneous (same data
type) or heterogeneous (different data types). The data stored can be changed using various operations like insertion,
deletion, searching, sorting, etc. They include data structures like arrays, trees and stacks.
The non-primitive data structures in C can further be divided into two categories. They are Linear and Non - Linear.
1. Linear Data Structures
2. Non-Linear Data Structures
,1. LINEAR DATA STRUCTURES: A data structure that preserves a linear connection among its data elements
is known as a Linear Data Structure. The arrangement of the data is done linearly, where each element consists of
the successors and predecessors except the first and the last data element. Based on memory allocation, the Linear
Data Structures are further classified into two types:
1. Static Data Structures: The data structures having a fixed size are known as Static Data Structures. The
memory for these data structures is allocated at the compiler time, and their size cannot be changed by the
user after being compiled; however, the data stored in them can be changed. Example : Array.
2. Dynamic Data Structures: The data structures having a dynamic size are known as Dynamic Data
Structures. The memory of these data structures is allocated at the run time, and their size varies during the
run time of the code. Example : Linked Lists, Stacks, and Queues.
TYPES OF LINEAR DATA STRUCTURES :
1. Arrays : An Array is a data structure used to collect multiple data elements of the same data type into one
variable. An Array is a list of elements where each element has a unique place in the list. The data elements of the
array share the same variable name; however, each carries a different index number called a subscript. We can
access any data element from the list with the help of its location in the list. Instead of storing multiple values of the
same data types in separate variable names, we could store all of them together into one variable. Thus, the key
feature of the arrays is that the data is stored in contiguous memory locations, making it possible for the users to
traverse through the data elements of the array using their indexes.
Arrays can be classified into different types:
1. One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
2. Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
3. Multidimensional Array: We can define Multidimensional Array as an Array of Arrays.
Multidimensional Arrays are not bounded to two indices or two dimensions as they can include as many
indices are per the need.
2. Linked Lists: A Linked List is used to store a collection of data elements dynamically. Data elements in this
data structure are represented by the Nodes, connected using links or pointers. Each node contains two fields, the
, information field consists of the actual data, and the pointer field consists of the address of the subsequent nodes in
the list. The pointer of the last node of the linked list consists of a null pointer, as it points to nothing.
Linked Lists can be classified into :
1. Singly Linked List: A Singly Linked List is the most common type of Linked List. Each node has data
and a pointer field containing an address to the next node.
2. Doubly Linked List: A Doubly Linked List consists of an information field and two pointer fields. The
information field contains the data. The first pointer field contains an address of the previous node, whereas
another pointer field contains a reference to the next node. Thus, we can go in both directions (backward as
well as forward).
3. Circular Linked List: The Circular Linked List is similar to the Singly Linked List. The only key
difference is that the last node contains the address of the first node, forming a circular loop in the Circular
Linked List.
3. Stack: A Stack is a Linear Data Structure that follows the LIFO (Last In, First Out) principle that allows
operations like insertion and deletion from one end of the Stack, i.e., Top. Stacks can be implemented with the help
of contiguous memory, an Array, and non-contiguous memory, a Linked List. Real-life examples of Stacks are piles
of books etc.,.
DIAGRAM :
Stack Operations:
● push(): When this operation is performed, an element is inserted into the stack.
● pop(): An element is removed from the top of the stack and is returned.
● top(): This will return the last inserted element that is at the top without removing it.
● size(): This will return the size of the stack i.e. the total number of elements present in the stack.
● isEmpty(): This operation indicates whether the stack is empty or not.
4. Queue: The Queue data structure follows FIFO (First In, First Out) principle. The insertion of an element in a
Queue is done at one end, and the removal is done at another or opposite end. The difference between stacks and
queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the
least recently added. Implementation of Queues can be done using Arrays, Linked Lists, or Stacks.
A good example of the queue is any queue of consumers for a resource where the consumer that came first is served
first.
Operations of the Queue :
1. Enqueue: The insertion or Addition of some data elements to the Queue is called Enqueue. The element
insertion is always done with the help of the rear/back pointer.
2. Dequeue: Deleting or removing data elements from the Queue is termed Dequeue. The deletion of the
element is always done with the help of the front pointer.
3. isFull(): Validates if the queue is full.
