Introduction to Data Structures

Unit#1
Data Structure 01CE1301

Department of Information Technology

Unit#1 Introduction to Data Structures Tejas Chauhan

Highlights

● Data Management concepts

● Data types – primitive and non-primitive
● Types of Data Structures
● Linear & non-linear Data Structures
● Abstract Data Types

Unit#1 Introduction to Data Structures Department of Information Technology 2

Data Management Concepts

● A program should give correct results but along with that it should run
efficiently.

● Efficient program executes:

○ Minimum time
○ Minimum memory space

● To write efficient program we need to apply Data management concepts.

Unit#1 Introduction to Data Structures Department of Information Technology 3

Data Management Concepts

● Data Management concept includes,

○ Data collection
○ Organization of data in proper structure
○ Developing and maintaining routines for quality assurance

“A data structure is a particular way of storing and organizing data in a computer so

that it can be used efficiently.”

Unit#1 Introduction to Data Structures Department of Information Technology 4

Data Structure

● When selecting DS, must perform below steps:

1. Analysis of the problem to determine basic operations like insert/delete/search a data in DS
2. Quantify the resource constraints for each operation
3. Select DS that best meets these requirements

● When developing an application:

○ First – data and operations, that are to be performed
○ Second – representation of data
○ Third – implementation of that representation

Unit#1 Introduction to Data Structures Department of Information Technology 5

Data Types

● A data type is a classification of data, which can store a specific type of

information.
○ Primitive data types
○ Non-Primitive data types

● Primitive data types are predefined, supported by C language. e.g. int, char,
float, double
● Non-Primitive data types are not defined by C language, but are created by the
programmer. e.g. Stack, Queue, Linked List, Tree, Graph
● They are created using the basic data types.

Unit#1 Introduction to Data Structures Department of Information Technology 6

Types of Data Structure

1. Arrays
● An array is a data structure consisting of a collection of similar data elements,
each identified by one array index.
● The elements in array are stored in consecutive memory locations.
● Array Syntax: int marks[5];

Elements marks[0] marks[1] marks[2] marks[3] marks[4]

Array 80 60 78 56 87

Index 0 1 2 3 4

Unit#1 Introduction to Data Structures Department of Information Technology 7

Types of Data Structure

1. Arrays
● Limitations of Arrays:
○ Fixed size
○ Data elements are stored in contiguous memory locations which may not be available always!
○ Adding and removing of elements is tough because of shifting the elements from their positions.

Unit#1 Introduction to Data Structures Department of Information Technology 8

Types of Data Structure

2. Linked List
● Consisting of a group of nodes which together represent a sequence.
● Under the simplest form, each node is composed of a data and a reference (in
other words, a link) to the next node in the sequence.
Node

Data Reference

● This structure allows for efficient insertion or removal of elements from any
position in the sequence.

Unit#1 Introduction to Data Structures Department of Information Technology 9

Types of Data Structure

2. Linked List
● A linked list whose nodes contain two fields:
○ an integer value and a link to the next node.

Head/Start D1 D2 D3 NULL

● The last node is linked to a terminator (NULL pointer) used to signify the end of
the list.
● Advantage:
○ Provides quick insert and delete operations
● Disadvantage:
○ Slow search operations and requires more memory space.

Unit#1 Introduction to Data Structures Department of Information Technology 10

Types of Data Structure

3. Stacks
● Stack can be represented as a linear array.
● Every stack has a variable TOP associated with it, to store the address of the
topmost element of the stack.
4

Top 2 D3

1 D2

0 D1

Stack

Unit#1 Introduction to Data Structures Department of Information Technology 11

Types of Data Structure

3. Stacks
● A stack is a last in, first out (LIFO) data structure.
● If TOP = NULL, then it indicates stack is empty
● If TOP = MAX, then it indicates stack is full.
4 4 Top 4 D5

3 3 3 D4

2 Top 2 D3 2 D3

1 1 D2 1 D2

0 0 D1 0 D1

Top Empty Stack Full

Stack With 3 Stack
Data

Unit#1 Introduction to Data Structures Department of Information Technology 12

Types of Data Structure

3. Stacks
● Elements are removed from the stack in the reverse order to the order of their
addition:
○ therefore, the lower elements are those that have been on the stack for longest time.

● Advantage: last-in first-out (LIFO) access.

● Disadvantage: Slow access to other elements.

Unit#1 Introduction to Data Structures Department of Information Technology 13

Types of Data Structure

4. Queue
● Queue is a data structure in which data can be added to one end and retrieved
from the other.
● You can think of it as a line in a grocery store.
● The first one in the line is the first one to be served. Just like a queue.
● A queue is also called a FIFO (First In First Out) to demonstrate the way it
accesses data.

● Advantage: Provides first-in, first-out data access.

● Disadvantage: Slow access to other items.

Unit#1 Introduction to Data Structures Department of Information Technology 14

Types of Data Structure

5. Trees
● A tree is a widely used data structure that simulates a hierarchical tree structure
with a set of linked nodes.
● Every tree has a root element pointed by a root pointer.
● If root = NULL, tree is empty.
● A simple unordered tree:
Root
7

4 9

2 5

Unit#1 Introduction to Data Structures Department of Information Technology 15

Types of Data Structure

5. Trees
● In binary tree every node contains a left pointer, a right pointer and a data
element.
Root
7

4 9

2 5

● Advantage: Provides quick search, insert, delete operations.

● Disadvantage: Complicated deletion algorithm.
● Example: Family Tree

Unit#1 Introduction to Data Structures Department of Information Technology 16

Types of Data Structure

6. Graph
● A graph is a data structure that is meant to implement the graph concepts from
mathematics.
● It is basically a collection of vertices(nodes) and edges that connect these
vertices.

1 2

3 4

Unit#1 Introduction to Data Structures Department of Information Technology 17

Types of Data Structure

6. Graph
● A graph is often viewed as a generalization of the tree structure, where complex
relationship can be represented.

● Advantage: Best models real-world situations.

● Disadvantages: Some algorithms are slow and very complex.

Unit#1 Introduction to Data Structures Department of Information Technology 18

Types of Data Structure

1. Linear Data Structure

● Elements are stored sequentially
● We can traverse either forward or backward
● Examples: Arrays, Stacks, Queues, Linked list

2. Non-linear Data Structure

● Not stored in sequential order
● Branches to more than one node
● Can’t be traversed in a single run
● Examples: Tree, Graphs

Unit#1 Introduction to Data Structures Department of Information Technology 19

Abstract Data Type

● ADT is the way we look at a Data Structure, focusing on what is does and
ignoring how it does its job.
○ In C for eg. FILE
○ Examples: Stack, Queue

● Whenever end user uses Stack, he is concerned about only the type of data and
operations that can be performed on it.
● Fundamentals of how the data is stored, is invisible to users.
● They will have push(), pop(), etc. functions only.

Unit#1 Introduction to Data Structures Department of Information Technology 20

Next Step

● Unit#2:
● Linear Data Structures & their representation
○ Array
○ Stack
○ Queue
○ Linked List

Unit#1 Introduction to Data Structures Department of Information Technology 21

 Thank You.

Unit#1 Introduction to Data Structures 22