Scribd
Upload
2 views4 pages

Lecture-1

The document outlines the course details for Data Structures (E1PY203B) taught by Ashutosh Kumar in the II semester of the 2024-2025 academic year. It covers basic terminology, types of data structures, including linear (arrays, linked lists, stacks, queues) and non-linear structures (trees, graphs), along with their operations, advantages, and applications. Additionally, it provides guidance on selecting appropriate data structures based on specific application requirements.

Uploaded by

chandrakalabhatt9066
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views4 pages

Lecture-1

The document outlines the course details for Data Structures (E1PY203B) taught by Ashutosh Kumar in the II semester of the 2024-2025 academic year. It covers basic terminology, types of data structures, including linear (arrays, linked lists, stacks, queues) and non-linear structures (trees, graphs), along with their operations, advantages, and applications. Additionally, it provides guidance on selecting appropriate data structures based on specific application requirements.

Uploaded by

chandrakalabhatt9066
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Faculty Name: Ashutosh Kumar

Course Code: E1PY203B


Course Name: Data Structures
Semester: II
Academic Year: 2024-2025

Basic Terminology and Types of Data Structures

1. Basic Terminology in Data Structures


a) Data
• Data refers to raw facts, figures or values that are processed to derive useful information.
• Example: Numbers (10, 20, 30), Text ("John", "Apple"), Boolean (True/False).

b) Data Structure
• A data structure is a way of organizing and storing data efficiently so that it can be accessed
and manipulated effectively.
• Examples: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs.

c) Data Type
• Defines the type of value a variable can store.
• Primitive Data Types: Integer, Float, Character, Boolean.
Primitive data structures are the fundamental data types which are supported by a programming
language. Basic data types such as integer, real, character and Boolean are known as Primitive data
Structures. These data types consists of characters that cannot be divided and hence they also called
simple data types.
• Non-Primitive Data Types: Arrays, Structures, Classes, Pointers.
Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of non-primitive data structures is the processing of complex numbers, linked
lists, stacks, trees, and graphs.

d) Abstract Data Type (ADT)


• ADTs define a logical representation of a data structure without specifying its implementation.
• ADT consists of a set of operations that can be performed on the data.
• Examples:
o Stack ADT: Defines push(), pop(), peek() operations.
o Queue ADT: Defines enqueue(), dequeue(), front(), rear() operations.

2. Types of Data Structures


Data structures are classified into two broad categories:
1. Linear Data Structures
2. Non-Linear Data Structures
A) Linear Data Structures
• Elements are stored sequentially.
• Each element has a unique predecessor and successor (except the first and last elements).
• Example: Arrays, Linked Lists, Stacks, Queues.

Types of Data Structure in C

1. Arrays
• A collection of elements stored in contiguous memory locations.
• Used when elements need to be accessed randomly using an index.

Types of Arrays:
o One-Dimensional Array (1D): int arr[5] = {10, 20, 30, 40, 50};
o Two-Dimensional Array (2D): int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
o Multi-Dimensional Array

• Operations:
o Insertion
o Deletion
o Searching
o Sorting
o Traversal

2. Linked List
• A collection of nodes, where each node contains data and a reference to the next node.
• Unlike arrays, linked lists allow dynamic memory allocation.

Types of Linked Lists:


o Singly Linked List – Each node points to the next node.
o Doubly Linked List – Each node points to both the previous and next nodes.
o Circular Linked List – The last node links back to the first node.

Advantages:
o Dynamic size allocation.
o Faster insertion and deletion.
Disadvantages:
o Requires extra memory for pointers.
o Slower access time compared to arrays.

3. Stack (LIFO – Last In, First Out)


• A linear data structure where insertion and deletion happen at one end (top).

Operations:
o push(x): Insert x at the top.
o pop(): Remove the top element.
o peek(): View the top element.

Applications:
o Undo feature in text editors.
o Function call management in recursion.

4. Queue (FIFO – First In, First Out)


• A linear data structure where insertion happens at the rear and deletion at the front.
Types of Queues:
o Simple Queue: Follows FIFO order.
o Circular Queue: The last position connects to the first.
o Dequeue (Double-ended Queue): Allows insertion and deletion at both ends.
o Priority Queue: Elements are dequeued based on priority.

Operations:
o enqueue(x): Insert x at the rear.
o dequeue(): Remove the element from the front.
o front(): View the front element.
o rear(): View the rear element.

B) Non-Linear Data Structures


• Elements are not arranged sequentially.
• Each element can be connected to multiple elements.
• Examples: Trees, Graphs.

1. Trees
• A hierarchical data structure consisting of nodes.
• Each node has a parent and child (except the root node).

Types of Trees:
o Binary Tree: Each node has at most two children.
o Binary Search Tree (BST): Left child < Root < Right child.
o AVL Tree: A self-balancing BST.
o Heap: A complete binary tree used in priority-based applications.

Applications:
o File system hierarchy.
o Organization structures.
o Database indexing.

2. Graphs
• A non-linear data structure consisting of a set of nodes (vertices) and edges (connections).

Types of Graphs:
o Directed Graph (Digraph): Edges have direction.
o Undirected Graph: Edges have no direction.
o Weighted Graph: Edges have weights (used in shortest path algorithms).

Graph Representation:
o Adjacency Matrix: An adjacency matrix is a way to represent a graph in a square
matrix form. It is used to show which vertices (or nodes) of a graph are adjacent to
which other vertices.
o Adjacency List: An adjacency list is another way to represent a graph, and it is
particularly efficient for sparse graphs (graphs with relatively few edges compared
to the number of vertices). Instead of using a matrix, an adjacency list uses a
collection of lists or arrays to store the neighbours of each vertex.
Applications:
o Social networks (Facebook, LinkedIn).
o Google Maps (shortest path algorithms).
o Computer networks.

How to Choose the Right Data Structure?


Choosing the right data structure depends on the application requirements:
Scenario Recommended Data Structure
Fast lookup with fixed size Array
Frequent insertions/deletions Linked List
LIFO behaviour (Undo, Backtracking) Stack
FIFO behaviour (Task scheduling, Printing) Queue
Fast searching Binary Search Tree (BST)
Hierarchical data representation Trees
Social networks, Pathfinding Graphs

Textbook: Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein “Data


Structures”.

You might also like