DATA STRUCTURES - U24CSB272

Unit I: Introduction
Abstract Data Types (ADTs)- List ADT-array-based implementation-linked
list implementation- singly linked lists-circular linked lists-doubly-linked lists-
applications of lists-Polynomial Manipulation- All operations -Insertion-
Deletion-Merge-Traversal.
Data structures are the fundamental building blocks of computer
programming. They define how data is organized, stored, and manipulated
within a program. Understanding data structures is very important for
developing efficient and effective algorithms.
A data structure is not only used for organizing the data. It is also used for
processing, retrieving, and storing data. There are different basic and
advanced types of data structures that are used in almost every program or
software system that has been developed. So we must have good
knowledge about data structures.

Classification of Data Structure

1. Linear Data Structure: Data structure in which data elements are

arranged sequentially or linearly, where each element is attached to its
previous and next adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.
2. Static Data Structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.
Example: array.
3. Dynamic Data Structure: In dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be considered
efficient concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.
4. Non-Linear Data Structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a
non-linear data structure, we can’t traverse all the elements in a single run
only.
Examples: Trees and Graphs.
1. Array:
Array is a linear data structure that stores a collection of elements of
the same data type. Elements are allocated contiguous memory, allowing
for constant-time access. Each element has a unique index number.
2. Matrix/Grid
Matrix is a two-dimensional array of elements, arranged
in rows and columns. It is represented as a rectangular grid, with each
element at the intersection of a row and column.
3. String
String is a sequence of characters, typically used to represent text. It is
considered a data type that allows for the manipulation and processing
of textual data in computer programs.
4. Stack
Stack is a linear data structure that follows the Last In, First Out
(LIFO) principle. Stacks play an important role in managing function calls,
memory, and are widely used in algorithms, web development, and systems
like compilers and browsers.
5. Queue
Queue is a linear data structure that follows the First In, First Out
(FIFO) principle. Queues play an important role in managing tasks or data in
order, scheduling and message handling systems.
6. Linked List
Linked list is a linear data structure that stores data in nodes, which are
connected by pointers. Unlike arrays, nodes of linked lists are not stored in
contiguous memory locations and can only be accessed sequentially,
starting from the head of list.
7. Hash
Hashing is a technique that generates a fixed-size output (hash value) from
an input of variable size using mathematical formulas called hash functions.
Hashing is commonly used in data structures for
efficient searching, insertion and deletion and plays a key role in software
applications like secure data retrieval, password
storage, cryptography, digital signatures, etc.
8. Tree
Tree is a non-linear, hierarchical data structure consisting of nodes
connected by edges, with a top node called the root and nodes having child
nodes. It is widely used in file systems, databases, decision-making
algorithms, etc.
9. Binary Tree
Binary Tree is a non-linear and hierarchical data structure where each
node has at most two children referred to as the left child and the right
child.
10. Binary Search Tree
Binary Search Tree is a type of binary tree in which each
node's left subtree contains only values smaller than the node, and each
node's right subtree contains only values greater than the node. This
property applies recursively, meaning that for every node, its left and right
subtrees must also satisfy the conditions of a valid Binary Search Tree.
11. Heap
Heap is a complete binary tree data structure that satisfies the heap
property. Heaps are usually used to implement priority queues, where
the smallest or largest element is always at the root of the tree.
12. Graph
Graph is a non-linear data structure consisting of a finite set of vertices(or
nodes) and a set of edges(or links)that connect a pair of nodes. Graphs are
widely used to represent relationships between entities.
13. Advanced Data Structures
Advanced Data Structures are complex arrangement of data which are
used to organize, store, and manipulate data efficiently, enabling faster and
more effective processing in complex algorithms. Unlike basic data types
such as arrays and linked lists, these structures include more sophisticated
options like Segment Trees, Trie, Binary Indexed Tree, Suffix Array etc.

DS Algorithm
What is an Algorithm?
An algorithm is a process or a set of rules required to perform calculations or some other
problem-solving operations especially by a computer. The formal definition of an algorithm
is that it contains the finite set of instructions which are being carried in a specific order to
perform the specific task. It is not the complete program or code; it is just a solution (logic)
of a problem, which can be represented either as an informal description using a Flowchart
or Pseudocode.

Characteristics of an Algorithm
The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input value to an
algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the instructions
in an algorithm should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the
algorithm should contain a limited number of instructions, i.e., the instructions should be
countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm
affects the overall process.
o Language independent: An algorithm must be language-independent so that the
instructions in an algorithm can be implemented in any of the languages with the same
output.

Dataflow of an Algorithm
o Problem: A problem can be a real-world problem or any instance from the real-world
problem for which we need to create a program or the set of instructions. The set of
instructions is known as an algorithm.
o Algorithm: An algorithm will be designed for a problem which is a step by step
procedure.
o Input: After designing an algorithm, the required and the desired inputs are provided to
the algorithm.
o Processing unit: The input will be given to the processing unit, and the processing unit
will produce the desired output.
o Output: The output is the outcome or the result of the program.

Why do we need Algorithms?

We need algorithms because of the following reasons:

o Scalability: It helps us to understand the scalability. When we have a big real-world

problem, we need to scale it down into small-small steps to easily analyze the problem.
o Performance: The real-world is not easily broken down into smaller steps. If the
problem can be easily broken into smaller steps means that the problem is feasible.

Let's understand the algorithm through a real-world example. Suppose we want to

make a lemon juice, so following are the steps required to make a lemon juice:
Step 1: First, we will cut the lemon into half.
Step 2: Squeeze the lemon as much you can and take out its juice in a container.

Step 3: Add two tablespoon sugar in it.

Step 4: Stir the container until the sugar gets dissolved.

Step 5: When sugar gets dissolved, add some water and ice in it.

Step 6: Store the juice in a fridge for 5 to minutes.

Step 7: Now, it's ready to drink.

The above real-world can be directly compared to the definition of the algorithm. We cannot
perform the step 3 before the step 2, we need to follow the specific order to make lemon
juice. An algorithm also says that each and every instruction should be followed in a specific
order to perform a specific task.

Importance of Algorithms
1. Theoretical importance: When any real-world problem is given to us and we break
the problem into small-small modules. To break down the problem, we should know
all the theoretical aspects.
2. Practical importance: As we know that theory cannot be completed without the
practical implementation. So, the importance of algorithm can be considered as both
theoretical and practical.

Types of Algorithms
The following are the types of algorithm:

o Search Algorithm
o Sort Algorithm
Search Algorithm

On each day, we search for something in our day to day life. Similarly, with the case of
computer, huge data is stored in a computer that whenever the user asks for any data then
the computer searches for that data in the memory and provides that data to the user.
There are mainly two techniques available to search the data in an array:

o Linear search
o Binary search

Linear Search

Linear search is a very simple algorithm that starts searching for an element or a value from
the beginning of an array until the required element is not found. It compares the element to
be searched with all the elements in an array, if the match is found, then it returns the index
of the element else it returns -1. This algorithm can be implemented on the unsorted list.
Binary Search

A Binary algorithm is the simplest algorithm that searches the element very quickly. It is
used to search the element from the sorted list. The elements must be stored in sequential
order or the sorted manner to implement the binary algorithm. Binary search cannot be
implemented if the elements are stored in a random manner. It is used to find the middle
element of the list.

Sorting Algorithms
Sorting algorithms are used to rearrange the elements in an array or a given data structure
either in an ascending or descending order. The comparison operator decides the new
order of the elements.

Why do we need a sorting algorithm?

o An efficient sorting algorithm is required for optimizing the efficiency of other algorithms
like binary search algorithm as a binary search algorithm requires an array to be sorted
in a particular order, mainly in ascending order.
o It produces information in a sorted order, which is a human-readable format.
o Searching a particular element in a sorted list is faster than the unsorted list.

ABSTRACT DATA TYPE – ( ADT).

An abstract data type is an abstraction of a data structure that provides only the interface
to which the data structure must adhere. The interface does not give any specific details about
something should be implemented or in what programming language.
An abstract data type is an abstraction of a data structure that provides only the interface to
which the data structure must adhere. The interface does not give any specific details about
something should be implemented or in what programming language.

In other words, we can say that abstract data types are the entities that are definitions of
data and operations but do not have implementation details. In this case, we know the data
that we are storing and the operations that can be performed on the data, but we don't know
about the implementation details. The reason for not having implementation details is that
every programming language has a different implementation strategy for example; a C data
structure is implemented using structures while a C++ data structure is implemented using
objects and classes.

For example, a List is an abstract data type that is implemented using a dynamic array and
linked list. A queue is implemented using linked list-based queue, array-based queue, and
stack-based queue. A Map is implemented using Tree map, hash map, or hash table.

Abstract data type model

Before knowing about the abstract data type model, we should know about abstraction and
encapsulation.

Abstraction: It is a technique of hiding the internal details from the user and only showing
the necessary details to the user.
Encapsulation: It is a technique of combining the data and the member function in a single
unit is known as encapsulation.
Defining ADTs: Examples
1. List ADT

The List ADT need to store the required data in the sequence and should
have the following operations:
 get(): Return an element from the list at any given position.
 insert(): Insert an element at any position in the list.
 remove(): Remove the first occurrence of any element from a non-empty
list.
 removeAt(): Remove the element at a specified location from a non-
empty list.
 replace(): Replace an element at any position with another element.
 size(): Return the number of elements in the list.
 isEmpty(): Return true if the list is empty; otherwise, return false.
 isFull(): Return true if the list is full; otherwise, return false.
2. Stack ADT
In Stack ADT, the order of insertion and deletion should be according to the
FILO or LIFO Principle. Elements are inserted and removed from the same
end, called the top of the stack. It should also support the following
operations:
 push(): Insert an element at one end of the stack called the top.
 pop(): Remove and return the element at the top of the stack, if it is not
empty.
 peek(): Return the element at the top of the stack without removing it, if
the stack is not empty.
 size(): Return the number of elements in the stack.
 isEmpty(): Return true if the stack is empty; otherwise, return false.
 isFull(): Return true if the stack is full; otherwise, return false.
3. Queue ADT

View of Queue

The Queue ADT follows a design similar to the Stack ADT, but the order of
insertion and deletion changes to FIFO. Elements are inserted at one end
(called the rear) and removed from the other end (called the front). It should
support the following operations:
 enqueue(): Insert an element at the end of the queue.
 dequeue(): Remove and return the first element of the queue, if the
queue is not empty.
 peek(): Return the element of the queue without removing it, if the queue
is not empty.
 size(): Return the number of elements in the queue.
 isEmpty(): Return true if the queue is empty; otherwise, return false.

Features of ADT:
Abstract data types (ADTs) are a way of encapsulating data and
operations on that data into a single unit. Some of the key features of
ADTs include:

 Abstraction: The user does not need to know the implementation of the
data structure only essentials are provided.
 Better Conceptualization: ADT gives us a better conceptualization of the
real world.
 Robust: The program is robust and has the ability to catch errors.
 Encapsulation: ADTs hide the internal details of the data and provide a
public interface for users to interact with the data. This allows for easier
maintenance and modification of the data structure.
 Data Abstraction: ADTs provide a level of abstraction from the
implementation details of the data. Users only need to know the
operations that can be performed on the data, not how those operations
are implemented.
 Data Structure Independence: ADTs can be implemented using different
data structures, such as arrays or linked lists, without affecting the
functionality of the ADT.
 Information Hiding: ADTs can protect the integrity of the data by
allowing access only to authorized users and operations. This helps
prevent errors and misuse of the data.
 Modularity: ADTs can be combined with other ADTs to form larger, more
complex data structures. This allows for greater flexibility and modularity
in programming.

Advantages:
 Encapsulation: ADTs provide a way to encapsulate data and operations
into a single unit, making it easier to manage and modify the data
structure.
 Abstraction: ADTs allow users to work with data structures without
having to know the implementation details, which can simplify
programming and reduce errors.
 Data Structure Independence: ADTs can be implemented using different
data structures, which can make it easier to adapt to changing needs and
requirements.
 Information Hiding: ADTs can protect the integrity of data by controlling
access and preventing unauthorized modifications.
 Modularity: ADTs can be combined with other ADTs to form more
complex data structures, which can increase flexibility and modularity in
programming.

Disadvantages:
 Overhead: Implementing ADTs can add overhead in terms of memory
and processing, which can affect performance.
 Complexity: ADTs can be complex to implement, especially for large and
complex data structures.
 Learning Curve: Using ADTs requires knowledge of their implementation
and usage, which can take time and effort to learn.
 Limited Flexibility: Some ADTs may be limited in their functionality or
may not be suitable for all types of data structures.
 Cost: Implementing ADTs may require additional resources and
investment, which can increase the cost of development.

List (abstract data type)

In computer science, a list or sequence is a collection of items that are finite in number
and in a particular order. An instance of a list is a computer representation of
the mathematical concept of a tuple or finite sequence.

A list may contain the same value more than once, and each occurrence is considered
a distinct item.

A singly-linked list structure, implementing a list with three integer elements.

The term list is also used for several concrete data structures that can be used to
implement abstract lists, especially linked lists and arrays. In some contexts, such as
in Lisp programming, the term list may refer specifically to a linked list rather than an
array. In class-based programming, lists are usually provided as instances of
subclasses of a generic "list" class, and traversed via separate iterators.

Many programming languages provide support for list data types, and have special
syntax and semantics for lists and list operations. A list can often be constructed by
writing the items in sequence, separated by commas, semicolons, and/or spaces, within
a pair of delimiters such as parentheses '()', brackets '[]', braces '{}', or angle
brackets '<>'. Some languages may allow list types to be indexed or sliced like array
types, in which case the data type is more accurately described as an array.