Chapter 2: Data Structures

Topics we study:
1. Data
2. Stack
3. Queue
4. Linked List
5. Tree
6. Graph
7. Searching and Hashing
 Data

Table of contents:
1. What is Data?
2. Why we need Data Structures and
Algorithms?
3. Common problem with applications
4. Different types of data-General
Understanding
5. Data Types in programming?
6. Data Structures
7. Data Structures characteristics
8. Data Structures basic terminology
9. Algorithm
10. Abstract Data Type
11. Abstract Data Type vs Data Structures
12. Real World Application of DSA
source:[1]
source:[1]
source:[2]
What is data?

Information

Facts

Numbers

1. What is data? Measurement

Observations

Graphs

Quantities

source:[3][4]
Why we need Data Structures and Algorithms?

● Why we need Data Structures and Algorithms?

● Fundamental of computer science that teaches us on how to approach/think and solve
the simple to complex problems systematically.
● Knowing right data structures and algorithm make our program run much faster when
working with abundant of data.
● Two important aspects:
○ Every programming has its own data data structures
○ Different types of algorithm for every programming
● Foundation for almost every softwares for example Search Engine, Gaming Apps, GPS
tracking, AI applications etc.
● Boost your problem solving skills abilities.
● Career wise: helps in crack the job interview and get hired.
● Common problems with the applications:
a. Multiple Request
b. Processor speed
c. Data Search
source:[5][6]
Can you tell different types of data in general?
 2. Different types of Data- General Understanding
1 Structured Data: Information is organized in predefined format as rows and columns.
Follows relational database. Ex: SQLite, MS SQL Server, Postgres, MySQL, Oracle etc. source:[7][8][9]
2 Unstructured Data: Does not have predefined format. Ex: Image, audio, video, text
documents etc.

3 Semi-Structured Data: Does not follow traditional database like SQL but still
has some organization. Ex: Json format, XML, CSV etc.

4 ● Nominal Data
-Labels or Names
-No order or ranking
-Cannot logically sorted
Qualitative Data: Describes the qualities, -Ex: Gender(Male/Female), Blood Group(A,AB,+ve,O-ve

labels or categories. ● Ordinal Data

-Ordered Categories
-Example: Education Level(SEE,Bachelor, Master, Phd)

5 ● Discrete
Quantitative Data: Describes quantities or -Countable data
-No decimals
numbers. Uses mathematical operation like -Example: Number of students in the class,

addition, mean, variance etc.

● Continuous
-values in a range
-Decimals allowed
-Example: Height, Time, Temperature, Age, Weight
What are Data Types in Programming?

● A data type is an attribute associated with piece of data that tells computer how to
interpret it and what operations can be performed on it.
● A method of interpreting a bit pattern is also known as Data Type.
● It uses variable to store the particular value. For example:
int number=100
● Why we need Data Types?
○ For memory allocation
○ Valid operations
○ Error Prevention
○ Readability and Maintainability
● Two data types:
○ Builtin Data Types
○ Derived Data Types
source:[10][14][15]
What is Data Structures?
Data Structures

● It defines how data is stored, organized and

retrieved, how operations are implemented, how
memory is managed in a programming language.
● It is systematic way to organize data where we can
use it efficiently.
● It is not restrict with only one programming
language.
● It is a physical Implementation in memory.
● In computer science:
○ Primitive Data Structure
○ Abstract Data Structures
● Usually two types:
○ Linear
○ Non- Linear
● Example: Array, String, Linked List, Stack, Queue
Data structures etc. source:[13][11][16]
Data Structures Characteristics

● Correctness:
○ Implementation of interface correctly.
Algorithm always produces the expected
output or follows the ground truth for the
range of valid inputs, and eventually, it
terminates.
● Time complexity:
○ Execution time of operations of data structure
must be small as possible.
● Space Complexity:
○ Usage of memory of a data structure operation
should be as little as possible.

source:[18]
Data Structures(continued..)

source:[17]
Data Structures Basic Terminologies
● Data: A collection of values or observations or fact.
● Data Item: A single unit of values.
● Group Items: Data items that are divided into sub of items(e.g: a "Name" divided into
First, Middle, and Last).
● Elementary Items: Data items that cannot be divided(Data items that cannot be
divided (e.g: a "Social Security Number" or "Age").
● Entity: An object that exists and is distinguishable(e.g: an employee).
● Attribute: The specific properties or characterisctics of an entity(e.g: salary, job title).
● Entity set: A group of similar entities(e.g: all employees in a company).
● Field: The smallest logical unit of data or Single elementary unit of information.
● Record: A logical collection of related fields that describes one entity or Collection of
fields.
● File: A Collection of related records(e.g a Payroll file).

source:[19]
What is Algorithm?
Algorithm?

● Step by step instruction that

defines to execute in a certain
order to get the desired output.
● It is independent to the
programming languages.
● Example: Searching, Sorting,
Pattern matching etc.

source:[20][21]
Abstract Data Types(ADT)
● Special kind of data type that is a conceptual
mathematical model that defines behaviors and set of
operations for a data structure. Consist two part:
○ Value definition: Collection of values
○ Operator definition: Set of Operation on those
values
● It is a tool that specify the logical properties of data type.
● It defines:
○ Data: What values it stores
○ Operation: what you can do with it.
○ Behavior/Rules: How operators should work
● Not concerned with space and time complexity.
● Hide internal implementation details and how data is
structured
○ Example: Push(), Pop(), Insert(), Delete(), Search()
● Example List as ADT, Stack as ADT, Queue as ADT, Tree
as ADT, Graph ADT
● Purpose: Provides an abstract model to define the data
structure in a conceptual way.

source:[22][23]
Abstract Data Types(ADT)(Continued..)

● Value Definition:

Abstract typedef <<int>> Number;

Condition Number => 0;

● Operator definition:

Abstract score(x,y)

Number x, y;

Postcondition number == (x[0] + y[0]>0)

● ADT as Sequence as Value definition

● ADT as Varying-length Character Strings

source:[8]
Abstract Data Type(The idea/blueprint) Vs Data Structures(The implementation/Physical
object)

● Analogy:
○ Mobile Phone Idea: It is an Abstract Data Type= Camera, Processor, Operating System etc.
○ Samsung/ Apple Phone: Data Structure=> actual implementation of Camera, Processor,
Operating System etc.

source:[24]
Abstract Data Type(The idea/blueprint) Vs Data Structures(The implementation/Physical
object)(continued..)

Abstract Data Type Data Structures

1 Concept/ Specification Actual Implementation

2 What Operations How operations are done

3 Example: Stack ADT Example: Stack using

array/linked list

4 It is High level concept Low level

5 No programming language dependent It is dependent on

programming language

6 It determines the behaviors what data and what It determines the memory
operation. use and performance on
that data for that operation.

source:[24]
Real world application of DSA

1. Applications of Arrays:
a. Your viewing screen is a multidimensional array of pixels.
b. Online book ticketing systems.
c. Contacts on a mobile phone.
d. A simple question paper is an array of numbered questions assigned with some marks.
2. Application of Linked Lists:
a. Image viewer software uses a linked list to view previous and next images.
b. Music player system.
c. Social Media feeds.
3. Application of Stack (LIFO Order):
a. Undo/Redo operation in word processors.
b. History of visited websites
c. Call Logs, E-mails, Google Photos, Downloads, Notifications - (Note:latest appears first).
Real world application of DSA(continued..)

4. Applications of Queue(FIFO Order):

a. Operating System that uses queue for job scheduling
b. Data Packets in Network Communication.
c. Sending email
d. Server response toward client request.
5. Application of Graphs:
e. Google’s Knowledge Graph, Facebook’s Graph API.
f. Dijkstra Algorithm
g. GPS navigation
h. Google Map.
6. Application of Tree:
i. XML Parser.
j. Domain Name Server.
k. File Explorer
References
● [1][Link]
● [2][Link]
data
● [3][Link]
● [4][Link]
● [5][Link]
-ai-e0ea291250c4
● [6][Link]
● [7][Link]
● [8]Data Structure and Algorithms with C and C++, Yedidyah Langsam, Moshe, Aaron
● [9][Link]
● [10][Link]
● [11][Link]
● [12][Link]
● [13][Link]
References
● [14][Link]
● [15][Link]
● [16][Link]
● [17][Link]
● [18][Link]
● [19][Link]
● [20][Link]
● [21][Link]
● [22][Link]
● [23][Link]
● [24][Link]
[Link]