MODULE – I
Syllabus:
• Introduction to Data Structures - Definition, Types, Applications - Abstract Data
Types (ADTs) and their significance. Arrays: Definition, Representation,
Operations (Insertion, Deletion, Traversal) - Searching Techniques: Linear Search,
Binary Search.
INTRODUCTION:
• A data structure is a particular way of storing and organizing data in a computer so that it can be
used efficiently.
• Some common examples of data structures are arrays, linked lists, queues, stacks, binary trees,
and hash tables
• Today computer programmers do not write programs just to solve a problem but to write an
efficient program.
• When selecting a data structure to solve a problem, the following steps must be performed.
1. Analysis of the problem to determine the basic operations that must be supported.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.
• The term data means a value or set of values. It specifies either the value of a variable or a constant
(e.g., marks of students, name of an employee, address of a customer, value of pi, etc.).
• A record is a collection of data items. For example, the name, address, course, and marks obtained
are individual data items. But all these data items can be grouped together to form a record.
• A file is a collection of related records. For example, if there are 60 students in a class, then there
are 60 records of the students. All these related records are stored in a file.
CLASSIFICATION OF DATA STRUCTURES:
• Data structures are generally categorized into two classes: primitive and non-primitive data
structures.
Primitive and Non-primitive Data Structures:
• Primitive data structures are the fundamental
data types which are supported by a
programming language. Some basic data types
are integer, real, character, and boolean. The
terms ‘data type, basic data type’, and ‘primitive
data type’ are often used interchangeably.
1
• Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of such data structures include linked lists, stacks, trees, and graphs.
• Non-primitive data structures can further be classified into two categories: linear and non-linear
data structures.
Linear and Non-linear Structures:
• If the elements of a data structure are stored in a linear or sequential order, then it is a linear data
structure.
o Examples include arrays, linked lists, stacks, and queues.
o Linear data structures can be represented in memory in two different ways. One way is to
have to a linear relationship between elements by means of sequential memory locations.
The other way is to have a linear relationship between elements by means of links.
• If the elements of a data structure are not stored in a sequential order, then it is a non-linear data
structure.
o The relationship of adjacency is not maintained between elements of a non-linear data
structure. Examples include trees and graphs.
Arrays:
• An array is a collection of similar data elements. These data elements have the same data type.
The elements of the array are stored in consecutive memory locations and are referenced by an
index (also known as the subscript).
• In C, arrays are declared using the following syntax: datatype name[size];
Ex: int marks[10];
limitations:
o Arrays are of fixed size.
o Data elements are stored in contiguous memory locations which may not be always available.
o Insertion and deletion of elements can be problematic because of shifting of elements from their
positions.
2
Linked Lists:
• linked list is a dynamic data structure in which elements (called nodes) form a sequential list.
• In a linked list, each node is allocated space as it is added to the list. Every node in the list points
to the next node in the list.
• Every node contains the following
The value of the node or any other data that corresponds to that node
A pointer or link to the next node in the list
• The first node in the list is pointed by Head/Start/First. The last node in the list contains a NULL
pointer to indicate that it is the end or tail of the list.
Advantage: Easier to insert or delete data elements
Disadvantage: Slow search operation and requires more memory space
Stacks:
• A stack is a linear data structure in which insertion and deletion of elements are done at only one
end, which is known as the top of the stack.
• Stack is called a last-in, first-out (LIFO)
structure because the last element which is
added to the stack is the first element which
is deleted from the stack.
• Stacks can be implemented using arrays or
linked lists.
• Every stack has a variable top associated
with it. Top is used to store the address of
the topmost element of the stack.
• It is this position from where the element will be added or deleted. There is another variable MAX,
which is used to store the maximum number of elements that the stack can store.
• If top = NULL, then it indicates that the stack is empty and if top = MAX–1, then the stack is full.
• A stack supports three basic operations: push, pop, and peep. The push operation adds an element
to the top of the stack. The pop operation removes the element from the top of the stack. And the
peep operation returns the value of the topmost element of the stack (without deleting it).
3
Queues:
• A Queue is a linear data structure in which insertion can be done at rear end and deletion of
elements can be dome at front end.
• A queue is a first-in, first-out (FIFO) data
structure in which the element that is
inserted first is the first one to be taken out.
• Like stacks, queues can be implemented by using either arrays or linked lists.
Insert element into the Queue:
Delete element from Queue:
• A queue is full when rear = MAX – 1, An underflow condition occurs when we try to delete an
element from a queue that is already empty. If front = NULL and rear = NULL, then there is no
element in the queue.
Trees:
• A tree is a non-linear data structure which consists of a collection of nodes arranged in a
hierarchical order.
• One of the nodes is designated as the root node, and the remaining nodes can be partitioned into
disjoint sets such that each set is a sub-tree of the root
• The simplest form of a tree is a binary tree. A binary tree
consists of a root node and left and right sub-trees, where both
sub-trees are also binary trees.
• Each node contains a data element, a left pointer which points
to the left sub-tree, and a right pointer which points to the right
sub-tree.
• The root element is the topmost node which is pointed by a
‘root’ pointer. If root = NULL then the tree is empty.
4
• Here R is the root node and T1 and T2 are the left and right subtrees of R. If T1 is non-empty,
then T1 is said to be the left successor of R. Likewise, if T2 is non-empty, then it is called the
right successor of R.
Advantage: Provides quick search, insert, and delete operations
Disadvantage: Complicated deletion algorithm
Graphs:
• A graph is a non-linear data structure which is a collection of vertices (also called nodes) and
edges that connect these vertices.
• A node in the graph may represent a city and the edges connecting
the nodes can represent roads.
• A graph can also be used to represent a computer network where
the nodes are workstations and the edges are the network
connections.
• Graphs do not have any root node. Rather, every node in the graph can be connected with every
another node in the graph.
Advantage: Best models real-world situations
Disadvantage: Some algorithms are slow and very complex
OPERATIONS ON DATA STRUCTURES:
• This section discusses the different operations that can be performed on the various data structures
previously mentioned.
• Traversing It means to access each data item exactly once so that it can be processed. For example,
to print the names of all the students in a class.
• Searching It is used to find the location of one or more data items that satisfy the given constraint.
Such a data item may or may not be present in the given collection of data items. For example, to
find the names of all the students who secured 100 marks in mathematics.
• Inserting It is used to add new data items to the given list of data items. For example, to add the
details of a new student who has recently joined the course.
• Deleting It means to remove (delete) a particular data item from the given collection of data items.
For example, to delete the name of a student who has left the course.
• Sorting Data items can be arranged in some order like ascending order or descending order
depending on the type of application. For example, arranging the names of students in a class in
an alphabetical order, or calculating the top three winners by arranging the participants’ scores in
descending order and then extracting the top three.
• Merging Lists of two sorted data items can be combined to form a single list of sorted data items.
5
ABSTRACT DATA TYPE:
• An abstract data type (ADT) is a data structure, focusing on what it does and ignoring how it does
its job. (or) Abstract Data type (ADT) is a
type (or class) for objects whose behavior is
defined by a set of value and a set of
operations.
• Ex: stacks ADT and queues ADT. the user
is concerned only with the type of data and
the operations that can be performed on it.
• We can implement both these ADTs using
an array or a linked list.
Advantage of using ADTs
• Modification of a program is simple, For example, if you want to add a new field to a student’s
record to keep track of more information about each student, then it will be better to replace an
array with a linked structure to improve the program’s efficiency.
• In such a scenario, rewriting every procedure that uses the changed structure is not desirable.
Therefore, a better alternative is to separate the use of a data structure from the details of its
implementation.
Common Abstract Data Types in Python
Several common ADTs are frequently used in Python:
1. List (Array): An ordered collection of elements.
2. Stack: A collection of elements with Last In, First Out (LIFO) access.
3. Queue: A collection of elements with First In, First Out (FIFO) access.
4. Set: A collection of distinct elements.
5. Dictionary (Map): A collection of key-value pairs.
Time and Space Complexity
Understanding the time and space complexity of operations on ADTs is crucial for writing efficient
programs. Complexity analysis helps predict the behavior of an algorithm as the size of the input
data grows.
List (Array)
A list is a collection of elements where each element can be accessed by its index. Lists are one of
the most versatile data structures in Python and support a wide range of operations.
• Access (indexing): O(1)
• Search: O(n)
• Insertion: O(n) (O(1) for append)
• Deletion: O(n)
• Space Complexity: O(n)
In a list, accessing an element by index is very efficient (O(1)) because the list is essentially an
array in memory. However, searching, inserting, and deleting elements can be time-consuming,
especially if the list is large, as these operations may require shifting elements.
6
# Creating a list
my_list = [1, 2, 3, 4, 5]
# Accessing elements
print(my_list[2]) # Output: 3
# Inserting elements
my_list.append(6) # [1, 2, 3, 4, 5, 6]
# Deleting elements
my_list.remove(3) # [1, 2, 4, 5, 6]
Stack
A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. The most
recently added element is the first one to be removed.
• Push (insertion): O(1)
• Pop (deletion): O(1)
• Peek (access top element): O(1)
• Search: O(n)
• Space Complexity: O(n)
A stack is a specialized list where elements are added and removed from only one end, called the
top. The push, pop, and peek operations are all O(1) because they involve only the top element.
However, searching through a stack requires linear time, O(n).
Example:
# Implementing stack using list
stack = []
# Push operation
[Link](1)
[Link](2)
# Pop operation
print([Link]()) # Output: 2
# Peek operation
print(stack[-1]) # Output: 1
Queue
A queue operates similarly to a stack but with FIFO access. Enqueuing and dequeuing elements are
O(1) operations because they occur at the ends of the queue. Searching through a queue, however,
is a linear operation, O(n).
Example:
from collections import deque
# Creating a queue
queue = deque()
# Enqueue operation
[Link](1)
[Link](2)
# Dequeue operation
7
print([Link]()) # Output: 1
# Peek operation
print(queue[0]) # Output: 2
Set
A set is a collection of distinct elements, meaning it cannot have duplicate elements. Sets are highly
efficient for membership testing.
• Insertion: O(1)
• Deletion: O(1)
• Search: O(1)
• Space Complexity: O(n)
Sets are collections of unique elements. The primary operations on a set (insertion, deletion, and
search) have an average time complexity of O(1) due to the underlying hash table implementation.
This makes sets very efficient for membership testing and eliminating duplicates.
Example:
# Creating a set
my_set = {1, 2, 3, 4, 5}
# Adding elements
my_set.add(6)
# Removing elements
my_set.remove(3)
# Checking existence
print(4 in my_set) # Output: True
Dictionary (Map)
A dictionary, or map, is a collection of key-value pairs, where each key is unique and is used to
store and retrieve values.
• Insertion: O(1)
• Deletion: O(1)
• Search: O(1)
• Space Complexity: O(n)
Dictionaries, or maps, store key-value pairs and also use hash tables for their implementation. The
average time complexity for insertion, deletion, and search operations is O(1), making dictionaries
highly efficient for associative arrays or mappings.
Example:
# Creating a dictionary
my_dict = {'a': 1, 'b': 2, 'c': 3}
# Accessing elements
print(my_dict['b']) # Output: 2
# Adding elements
my_dict['d'] = 4
# Deleting elements
del my_dict['a']
8
Arrays:
Definition:
An array is a powerful data structure that allows users to store and manipulate a collection of
elements, all of the same data type in a single variable. Simply, it is a collection of elements of
the same data type stored at contagious memory locations that can be randomly accessed with
their index number. It’s one of the most popular and simple data structures and is often used to
implement other data structures like stacks and queues.
There are two types of array in Data Structures, which are:
1. Single-dimensional array: It is a collection of elements of the same data type that are
stored in a contiguous block of memory.
2. Multi-dimensional array: It is an array that contains one or more arrays as its elements.
We will see this in the next section Types of Arrays in Data Structures.
Representation of Arrays in Data Structures:
The representation of an array can be defined by its declaration. A declaration means
allocating memory for an array of a given size.
import array
# Example:
arr = [Link]('i', [1, 2, 5, 6])
9
Operations(Insertion,Deletion,Travesal)
[Link]
We can insert one or multiple elements in an array as per the requirement at the
required positions or indexes.
def main():
chairs = [1, 2, 3, 4, 5]
balls = [5, 2, 8, 5, 7, -1]
# array size
n=5
# index of element to be added
pos = 2
# element to be added
item = 4
# incrementing the size of the array by 1
n=n+1
# adjusting the value of loop counter to the last index
j=n-2
# traversing balls[] from last
while j >= pos:
# copying the element to the incremented block
balls[j + 1] = balls[j]
j=j-1
# copying the element to the vacated position
balls[pos] = item
print("The chairs and the corresponding number of balls after adding a ball:")
10
for i in range(n):
print(" ", i + 1, "\t", balls[i])
if __name__ == "__main__":
main()
Output
1 5
2 2
3 4
4 8
5 5
6 7
[Link]
It is used to delete an element from a particular index in an array.
balls = [5, 2, 8, 5, 7]
# array size
n=5
# index of element to be deleted
pos = 2
# adjusting the value of loop counter to pos
j = pos
while j < n:
balls[j - 1] = balls[j]
j=j+1
# decrementing the size of the array by 1
n=n-1
print("\nThe chairs and the corresponding number of balls after removing a ball")
for i in range(n):
print(" " + str(i + 1) + "\t " + str(balls[i]))
Output
The chairs and the corresponding number of balls after removing a ball
1 5
2 8
3 5
4 7
11
[Link]
This operation is used to traverse or move through the elements of the array.
fruits = ["Apple", "Mango", "Banana", "Orange", "Grapes"]
for fruit in fruits:
print(fruit)
Output
Apple
Mango
Banana
Orange
Grapes
SEARCHING:
• Searching means to find whether a particular value is present in an array or not.
• If the value is present in the array, then searching is said to be successful and the searching process
gives the location of that value in the array.
• However, if the value is not present in the array, the searching process displays an appropriate
message and in this case searching is said to be unsuccessful.
Searching techniques are linear search, binary search and Fibonacci Search
LINEAR SEARCH:
• Linear search is a technique which traverse the array sequentially to locate given item or search
element.
• In Linear search, we access each element of an array one by one sequentially and see weather it
is desired element or not. We traverse the entire list and match each element of the list with the
item whose location is to be found. If the match found then location of the item is returned
otherwise the algorithm return NULL.
• A search is successful then it will return the location of desired element
• If A search will unsuccessful if all the elements are accessed and desired element not found.
• Linear search is mostly used to search an unordered list in which the items are not sorted.
Linear search is implemented using following steps...
12
Step 1 - Read the search element from the user.
Step 2 - Compare the search element with the first element in the list.
Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function
Step 4 - If both are not matched, then compare search element with the next element in the list.
Step 5 - Repeat steps 3 and 4 until search element is compared with last element in the list.
Step 6 - If last element in the list also doesn't match, then display "Element is not found!!!" and
terminate the function.
Example:
Consider the following list of elements and the element to be searched...
13
BINARY SEARCH:
• Binary search is the search technique which works efficiently on the sorted lists. Hence, in order
to search an element into some list by using binary search technique, we must ensure that the list
is sorted.
• Binary search follows divide and conquer approach in which, the list is divided into two halves
and the item is compared with the middle element of the list. If the match is found then, the
location of middle element is returned otherwise, we search into either of the halves depending
upon the result produced through the match.
Algorithm:
Step 1 - Read the search element from the user.
Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
14
Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
Step 5 - If both are not matched, then check whether the search element is smaller or larger than
the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left
sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right
sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist
contains only one element.
Step 9 - If that element also doesn't match with the search element, then display "Element is not
found in the list!!!" and terminate the function.
Example:
15
Example 2:
16
17