Introduction to Data Structures

Data structures form the foundation of efficient software design and

algorithm implementation. They allow us to organize, manage, and store
data in ways that optimize access and modification. This presentation
explores fundamental data structures including arrays, stacks, queues,
linked lists, graphs, trees, hashing, and common algorithms for sorting and
searching.

Understanding these data structures is crucial for computer science students

and software engineers to solve complex problems, improve performance,
and build scalable applications effectively.

Dr. Moutushi Singh

Professor & Head
Department of Computer Science & Engg. & Information Technology
Institute of Engineering & Management,
University of Engineering & Management, Kolkata

preencoded.png
Arrays: The Building Blocks of Data Organization
Definition and Characteristics Usage Examples Definition of Array

An array is a collection of elements identified by index or key, • Storing fixed-size datasets

stored contiguously in memory. It provides fast access to • Implementing other data structures like heaps
elements via indexing, making it ideal for static collections
• Static lookup tables and matrices
where size is known.
Arrays support efficient traversal and enable various algorithms
but have fixed size, limiting dynamic flexibility.

Basic Operations in Arrays

The basic operations in the Arrays are insertion, deletion, searching,

display, traverse, and update. These operations are usually performed to
either modify the data in the array or to report the status of the array.
Following are the basic operations supported by an array.
•Traverse − print all the array elements one by one.
•Insertion − Adds an element at the given index.
•Deletion − Deletes an element at the given index.
•Search − Searches an element using the given index or by the value.
•Update − Updates an element at the given index.
•Display − Displays the contents of the array. preencoded.png
Stacks and Queues: Managing Ordered Data
Stack
A stack is a Last-In-First-Out (LIFO) structure supporting push and pop operations. It is widely
used for function call management, syntax parsing, and backtracking algorithms.

Queue

A queue is a First-In-First-Out (FIFO) data structure with enqueue and dequeue operations. It is
useful for scheduling, buffering, and breadth-first traversal.

Data Structures: Stacks and Queues

preencoded.png
Why & When stack or queue is used instead of
array/lists:
Because they assist you in managing your data in a more specific manner than arrays and lists. It means you won’t have to wonder if
someone placed an element in the midst of your list at random, messing up certain invariants when troubleshooting an issue. Random
access is the nature of arrays and lists. They’re incredibly adaptable, but they’re also easily corruptible. If you wish to keep track of
your data, It’s recommended to use those, previously implemented, collections when storing data as FIFO or LIFO.
•We use stack or queue instead of arrays/lists when we want the elements in a specific order i.e. in the order, we put them (queue) or
in the reverse order (stack).

•Queues and stacks are dynamic while arrays are static. So, when we require dynamic memory, we use queue or stack over arrays.

•Stacks and queues are used over arrays when sequential access is required.

•To efficiently remove any data from the start (queue) or the end (stack) of a data structure.

•When you want to get items out in the same order that you put them in, use a queue (FIFO)

•When you need to bring things out in the opposite order that they were put in, use a stack (LIFO)

preencoded.png
Linked Lists: Dynamic Sequential Access
Singly Linked List Doubly Linked List
Each node contains data and a Nodes hold pointers to both
pointer to the next node. Allows previous and next nodes,
dynamic size with efficient enabling bidirectional traversal
insertions and deletions at head and easier node removal.
or middle.

Circular Linked List

Last node points back to the head, useful for buffering and cyclic
iteration.

A linked list is a linear data structure consisting of a sequence of nodes, where each node contains two parts: data and a pointer to the
next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation; each node is dynamically allocated
its own memory space, allowing for efficient insertions and deletions. The first node is often referred to as the head, and linked lists
can be singly linked (each node points to the next) or doubly linked (each node points to both the next and the previous node). Linked
lists are widely used in various applications, including implementing stacks, queues, and dynamic memory allocation.
Bing Videos Introduction to Linked List preencoded.png
Graphs: Modeling Complex Relationships
A graph is a non-linear data structure. It consists of:
•Vertices (nodes): Represent entities within the graph.
•Edges: Define relationships or connections between vertices.
•Weight (in weighted graphs): Assign numerical values to edges.
•Degree: Refers to the number of edges incident to a vertex.

Vertices (Nodes) Edges

1 2
Basic units representing entities such as Connections between vertices representing
people or locations. relationships or pathways.

Weighted Edges Directed vs Undirected

Edges may carry weights such as costs or Edges can have direction indicating one-
4 3
distances. way or mutual connection.

Learn Graphs in 5 minutes

preencoded.png
Trees: Hierarchical Data Structures
Tree Data Structure is a non-linear data structure in which a
collection of elements known as nodes are connected to each other
via edges such that there exists exactly one path between any two
nodes.

Binary Tree 1
A tree where each node has at most two children. Enables fast
searching, insertion, and deletion.
2 Binary Search Tree (BST)
Left child nodes contain smaller values, right child nodes contain
larger, facilitating ordered data retrieval.
Balanced Trees 3
Structure is maintained to keep height minimal, improving operation
efficiency.
4 Other Variants
Includes AVL trees, red-black trees, and B-trees used in databases
and file systems.

Data Structures: Trees preencoded.png

Trees: Hierarchical Data Structures
Basic Terminologies In Tree Data Structure:
Parent Node: The node which is an immediate predecessor of a node is
called the parent node of that node. {B} is the parent node of {D, E}.
Child Node: The node which is the immediate successor of a node is called
the child node of that node. Examples: {D, E} are the child nodes of {B}.
Root Node: The topmost node of a tree or the node which does not have
any parent node is called the root node. {A} is the root node of the tree. A
non-empty tree must contain exactly one root node and exactly one path
from the root to all other nodes of the tree.
Leaf Node or External Node: The nodes which do not have any child
nodes are called leaf nodes. {I, J, K, F, G, H} are the leaf nodes of the tree. Why Tree is considered a non-linear data structure?
Ancestor of a Node: Any predecessor nodes on the path of the root to that The data in a tree are not stored in a sequential manner i.e.,
node are called Ancestors of that node. {A,B} are the ancestor nodes of the they are not stored linearly. Instead, they are arranged on
node {E} multiple levels or we can say it is a hierarchical structure. For
Descendant: A node x is a descendant of another node y if and only if y is this reason, the tree is considered to be a non-linear data
an ancestor of x. structure.
Sibling: Children of the same parent node are called siblings. {D,E} are called
Basic Operations Of Tree Data Structure:
siblings. •Create – create a tree in the data structure.
Level of a node: The count of edges on the path from the root node to that •Insert − Inserts data in a tree.
node. The root node has level 0. •Search − Searches specific data in a tree to check whether
Internal node: A node with at least one child is called Internal Node. it is present or not.
Neighbour of a Node: Parent or child nodes of that node are called •Traversal:
neighbors of that node. • Depth-First-Search Traversal
Sub tree: Any node of the tree along with its descendant. • Breadth-First-Search Traversal
preencoded.png
Hashing: Fast Data Lookup
Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that allows for quick access.

•Hashing involves mapping data to a specific index in a hash table (an array of items) using a hash function. It enables fast
retrieval of information based on its key.
•The great thing about hashing is, we can achieve all three operations (search, insert and delete) in O(1) time on average.
•Hashing is mainly used to implement a set of distinct items (only keys) and dictionaries (key value pairs).

Components of Hashing
There are majorly three components of hashing:
1.Key: A Key can be anything string or integer which is fed as input in the hash function
the technique that determines an index or location for storage of an item in a data
structure.
2.Hash Function: Receives the input key and returns the index of an element in an
array called a hash table. The index is known as the hash index .
3.Hash Table: Hash table is typically an array of lists. It stores values corresponding to
the keys. Hash stores the data in an associative manner in an array where each data
value has its own unique index.

preencoded.png
Hashing: Fast Data Lookup
How does Hashing work?
Suppose we have a set of strings {“ab”, “cd”, “efg”} and we would
like to store it in a table. What is Collision in Hashing?
•Step 1: We know that hash functions (which is some mathematical When two or more keys have the same hash value,
formula) are used to calculate the hash value which acts as the index a collision happens. If we consider the above example, the hash
of the data structure where the value will be stored. function we used is the sum of the letters, but if we examined the
•Step 2: So, let’s assign hash function closely then the problem can be easily visualized
•“a” = 1, that for different strings same hash value is being generated by
•“b”=2, .. etc, to all alphabetical characters. the hash function.
•Step 3: Therefore, the numerical value by summation of all For example: {“ab”, “ba”} both have the same hash value, and
characters of the string: string {“cd”,”be”} also generate the same hash value, etc. This is
•“ab” = 1 + 2 = 3, known as collision and it creates problem in searching, insertion,
•“cd” = 3 + 4 = 7 , deletion, and updating of value.
•“efg” = 5 + 6 + 7 = 18
•Step 4: Now, assume that we have a table of size 7 to store these
strings. The hash function that is used here is the sum of the
characters in key mod Table size . We can compute the location of
the string in the array by taking the sum(string) mod 7 .
•Step 5: So we will then store
•“ab” in 3 mod 7 = 3,
•“cd” in 7 mod 7 = 0, and
•“efg” in 18 mod 7 = 4.

To handle this collision, we use Collision Resolution Techniques. preencoded.png

Sorting Algorithms: Arranging Data Efficiently
A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10,
20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order.
•There exist different sorting algorithms for different types of inputs, for example a binary array, a character array, an array with a large range of values or
an array with many duplicates or a small vs. large array.
•The algorithms may also differ according to output requirements. For example, stable sorting (or maintains original order of equal elements) or not
stable.
•Sorting is provided in library implementation of most of the programming languages. These sorting functions typically are general purpose functions
with flexibility of providing the expected sorting order (increasing or decreasing or by a specific key in case of objects).

Common Algorithms
• Bubble Sort
• Merge Sort
• Quick Sort
• Heap Sort

Performance Considerations
Time complexity varies; merge and quick sorts are efficient for large data sets.
Stability and space complexity also matter.

Use Cases
Sorting is fundamental for searching, data organization, and algorithm optimization.

preencoded.png
Searching Algorithms:
Searching algorithms are essential tools in computer science used to locate specific items within a collection of data. In this tutorial, we are mainly going to
focus upon searching in an array. When we search an item in an array, there are two most common algorithms used based on the type of input array.
Linear Search : It is used for an unsorted array. It mainly does one by one comparison of the item to be search with array elements. It takes linear or O(n) Time.
Binary Search : It is used for a sorted array. It mainly compares the array's middle element first and if the middle element is same as input, then it returns. Otherwise it
searches in either left half or right half based on comparison result (Whether the mid element is smaller or greater). This algorithm is faster than linear search and
takes O(Log n) time.

Linear Search vs. Binary Search

Feature Linear Search Binary Search
Approach Check each element one by one. Repeatedly divide the search interval in half.

Data Requirement Works on any list (unsorted or sorted). Works only on a sorted list.
Time Complexity O(n) O(log n)
Space Complexity O(1) O(1)
Speed Slower for large datasets. Much faster for large datasets.
Large, sorted datasets (like phonebooks,
Example Use Small or unsorted data sets.
databases).

preencoded.png
Searching Algorithms:
Example
Example List: List: [3, 7, 9, 13, 18, 21, 27, 31]
Search for: 18

1. Linear Search 2. Binary Search

Steps: Steps:
•Compare 3 → not 18 •Middle element: 13 → (index 4)
•Compare 7 → not 18 • 18 > 13 → search in right half [18, 21, 27, 31]
•Compare 9 → not 18 •Middle element in right half: 21
•Compare 13 → not 18 • 18 < 21 → search in left half [18]
•Compare 18 → found! •Middle element now: 18 → found!
Found 18 at position 5. Found 18 at position 5.
Observation: Had to check element by element. Observation: Only 3 checks instead of 5.

preencoded.png
Searching Algorithms: Locating Data Quickly

1 Linear Search 2 Binary Search

Simple, sequential search Efficient O(log n) search on
with O(n) complexity, suitable sorted data by repeatedly
for unsorted or small dividing the search interval in
datasets. half.

3 Graph Search
Includes depth-first and breadth-first search for traversing graph
structures and finding paths.

preencoded.png
Key Takeaways and Best Practices
Choose Data Structures Wisely
Match the structure to your application's needs to optimize performance and memory
use.

Understand Algorithm Complexity

Evaluate time and space complexities to ensure scalable solutions.

Practice Implementation
Hands-on coding deepens understanding and improves problem-solving skills.

Stay Updated
New structures and algorithms continue to evolve; keep learning to enhance efficiency.

preencoded.png