Chapter 28 – Basics of Data Structures
- Authors
- Ms. Samavi Salman
- Dr. Rao Muhammad Adeel Nawab
Quick Recap
- Quick Recap – Functions in Python
In previous Chapter, I presented
- Function
- A Function is defined as a piece of Code (or block of Python Statements) to perform a specific Programming Task
- Python Program
- A Python Program is a collection of one or more Functions
- Main Components of a Function
- The three main components of a Function are
- Function Prototype
- Function Definition
- Function Call
- The three main components of a Function are
- Function Prototype
- A Function Prototype is a function declaration that specifies the data types of its arguments in the parameter list
- Functions can be declared implicitly by their appearance in a call. Arguments to functions undergo the default conversions before the call. The number and type of arguments are not checked
- Function Prototype
- Function Prototype comprises of three parts
- Return Type
- Function Name
- List of Arguments / Parameters
- Function Prototype comprises of three parts
- Four Variations in Function Prototype
- No Return Type, No Arguments / Parameters
- No Return Type, Arguments / Parameters
- Return Type, No Arguments / Parameters
- Return Type, Arguments / Parameters
- Types of Functions
- There are two types of Functions in Python
- Built-in Functions
- User Defined Functions
- There are two types of Functions in Python
- Built-in Function
- A Built-in Function is defined as a Function whose functionality is pre-defined in Python Programming Language
- User Defined Functions
- A User Defined Function is defined as a Function that you can define yourself in Python Programming Language
- Function Definition
- Function Definition is made up of two parts
- Function Header
- Body of Function
- Function Definition is made up of two parts
- Scope of Variable
- The scope of the variable is simply lifetime of a variable. It is block of code under which a variable is applicable or alive
- Types of Scope of Variable
- There Variables can be declared in two ways:
- Local Variable (Inside a function or a block)
- Global Variable (Outside of all functions)
- In the definition of function parameters which are called formal parameters
- There Variables can be declared in two ways:
- Local Variables
- The Variables that are declared inside a function / subroutine are called Local Variables
- Global Variables
- The Variables that are declared outside a function / subroutine are called Global Variables
- Formal Parameters
- Formal parameters, are treated as local variables with-in a function and they take precedence over global variables
- Pass Object by Value and Pass Object by Reference
- An immutable object’s value cannot be changed, even if it is passed a new value
- Passing by value refers to passing a copy of the value
- Passing by reference refers to passing the real reference of the variable in memory
Basics of Data Structure
- Data Structure
- Definition 1
- A Data Structure is defined as a collection of Data Values and relationship among them
- Definition 2
- A Data Structure is defined as a logical or mathematical model to properly organize Data Values
- Definition 3
- A Data Structure is defined as a way of organizing Data Values, so that they can be used efficiently
- Purpose
- The main purpose of a Data Structure is to
- Organize Data Values in such a way that they can be used easily, quickly, and efficiently
- The main purpose of a Data Structure is to
- Importance
- Efficient Data Structures are key to designing efficient Algorithms and
- Efficient Algorithms are key to developing efficient Software’s
- Data Structure help us to manage large amount of Data Values efficiently
- Applications
- Data Structures are used in developing a range of applications including
- Web Apps
- Mobile Apps
- Research Prototypes
- ERP Systems
- Game Development
- And many more
- Data Structures are used in developing a range of applications including
- Suitable to Use
- To develop high-quality Software and manage Data Values properly, we use Data Structures in almost every Software 😊
- Operations on Data Structures
- We mainly perform the following eight Operations to manipulate the Data Values stored in a Data Structure
- Operation 1 – Creation
- Creation of a Data Structure means creating a Data Structure according to its requirements
- Operation 2 – Insertion
- Insertion means adding / inserting Data Values into a Data Structure
- Note
- Data Values can be inserted in a Data Structure at the: (1) beginning, (2) end or (3) desired location
- Operation 3 – Traversal
- Traversal means to visit each Data Value / Element / Item of a Data Structure at least once
- Operation 4 – Searching
- Searching means to find a particular Data Value / Element / Item in all the Data Values / Elements / Items of a Data Structure
- Operation 5 – Sorting
- Sorting means to rearrange the Data Values / Elements / Items of a Data Structure in a particular order i.e., Ascending Order / Descending Order
- Operation 6 – Merging
- Combining the Data Values / Elements / Items of Two or More (same) Data Structures into a Single Data Structure
- Operation 7 – Updation
- Updation means to update / change the existing Data Value(s) in a Data Structure with some new Data Value(s)
- Operation 8 – Deletion
- Deletion means deleting / removing Data Value(s) from a Data Structure
- Note
- Data Values can be deleted from a Data Structure at the: (1) beginning, (2) end or (3) given location
- Operation 1 – Creation
- Types of Data Structures
- The two main Types of Data Structures are
- Linear Data Structures
- Non-linear Data Structures
- Linear Data Structures
- Definition
- Linear Data Structure is defined as a Data Structure in which Data Values arranged sequentially or linearly
- Popular Linear Data Structures
- Some of the popular and widely used Linear Data Structures are as follows
- Arrays
- Lists
- Set
- Tuple
- Dictionary
- Queue
- Stack
- Linked Lists
- Some of the popular and widely used Linear Data Structures are as follows
- Non-linear Data Structures
- Definition
- A Non-linear Data Structure is defined as a Data Structure in which Data Values are not arranged sequentially or linearly
- Popular Non-linear Data Structures
- Some of the popular and widely used Non-linear Data Structures are as follows
- Trees
- Graphs
- Some of the popular and widely used Non-linear Data Structures are as follows
- Lecture Focus
- The focus of this Lecture is on
- Linear Data Structures
Python Collections
- Python Collections
- In Python, there are five Collection Data Types, which are as follows
- Array
- List
- Tuple
- Set
- Dictionary
- Comparison of Main Characteristics of Python Collections
- The Table below shows a Comparison of Main Properties of Python Collections
Collection | Order | Changeable | Duplicate | Nesting |
Array | Ordered | Changeable | Allows Duplicate Members | Allows Nesting |
List | Ordered | Changeable | Allows Duplicate Members | Allows Nesting |
Tuple | Ordered | Unchangeable | Allows Duplicate Members | Allows Nesting |
Set | Unordered and Unindexed | Changeable | No Duplicate Members | Allows Nesting |
Dictionary | Ordered | Changeable | No Duplicate Members | Allows Nesting |
- Selection of a Collection Type to Solve a Real-world Problem
- Question
- How can we select the most suitable Collection Type to Solve a Real-world Problem?
- Answer
- To select the most suitable Collection Type to Solve a Real-world Problem, we need to
- Completely and correctly understand the Properties of each Collection Type
- To select the most suitable Collection Type to Solve a Real-world Problem, we need to
- Important Note
- Selection of appropriate Collection to solve a Real-world Problem will
- Increase efficiency and security
- Selection of appropriate Collection to solve a Real-world Problem will
TODO and Your Turn
Todo Tasks
Your Turn Tasks
Todo Tasks
TODO Task 1
- Task
- Write down at least 2 Linear and 2 Non-linear Data Structures not mentioned in this Lecture?
Your Turn Tasks
Your Turn Task 1
- Task
- Search and write down Linear and Non-linear Data Structures for the following Programming Languages?
- C
- Java
- React JS
- Ruby on Rail
- Search and write down Linear and Non-linear Data Structures for the following Programming Languages?
Chapter Summary
- Chapter Summary
In this Chapter, I presented the following main concepts:
- Data Structure
- Definition 1
- A Data Structure is defined as a collection of Data Values and relationship among them
- Definition 2
- A Data Structure is defined as a logical or mathematical model to properly organize Data Values
- Definition 3
- A Data Structure is defined as a way of organizing Data Values, so that they can be used efficiently
- Definition 1
- Operations on Data Structures
- We mainly perform the following eight Operations to manipulate the Data Values stored in a Data Structure
- Operation 1 – Creation
- Operation 2 – Insertion
- Operation 3 – Traversal
- Operation 4 – Searching
- Operation 5 – Sorting
- Operation 6 – Merging
- Operation 7 – Updation
- Operation 8 – Deletion
- We mainly perform the following eight Operations to manipulate the Data Values stored in a Data Structure
- Types of Data Structures
- The two main Types of Data Structures are
- Linear Data Structures
- Non-linear Data Structures
- The two main Types of Data Structures are
- Linear Data Structures
- Definition
- Linear Data Structure is defined as a Data Structure in which Data Values arranged sequentially or linearly
- Definition
- Non-linear Data Structures
- Definition
- A Non-linear Data Structure is defined as a Data Structure in which Data Values are not arranged sequentially or linearly
- Definition
- Python Collections
- In Python, there are five Collection Data Types, which are as follows
- Array
- List
- Tuple
- Set
- Dictionary
- In Python, there are five Collection Data Types, which are as follows
In Next Chapter
- In Next Chapter
- In Sha Allah, in the next Chapter, I will present a detailed discussion on
- Arrays in Python