Welcome to
ITEC 2620
Introduction to
Data Structures
Khairul Bashar
School of Information Technology
York University, Toronto.
It is a format for arranging, processing,
accessing and storing a collection of data in a
storage device.
What is a Data There are both simple and complex data
Structure? structures.
Using a proper data Efficiency
structure for your data can Reusability
increase the performance Processing speed
of your program by
ArrayList
LinkedList
Popular Stack
Data Queue
Structures Tree
Graph
And many more
• Analyze your problem to determine the basic
operations that must be supported.
Selecting a Examples of basic operations include
Data inserting a data item into the data structure,
deleting a data item from the data structure,
Structure to and finding a specified data item.
solve a • Quantify the resource constraints for each
operation.
problem • Select the data structure that best meets
these requirements.
• Storage Space
• Execution Time
• Programming effort
Costs and You need to analyze the problem’s
Benefits characteristics to find a balance between the
costs and benefits for different data
structures.
Example: Bank Database System
Data Types
• Primitive Data Types
• Int, float, Boolean
• Non-Primitive Data Types
• These are also called reference types
because they refer to an object of a
class. Aggregated type, composite
type
• These can be used to call methods,
starts with an uppercase letter.
Is String a primitive or non-primitive
data type?
Abstract data type (ADT) and Data
Structure
• Data type as a software component
• It’s a formal description of the behavior of a data type. Mostly, what kind of operation we
would like the data type to have.
• An ADT does not specify how the data type is implemented.
• A data structure is a concrete representation/organization/implementation of an ADT
• An ADT and its implementation together make up a class.
• For many cases the type can be decided runtime. (e.g. List)
ADT for a List
• Add items to the list
• Remove items from the list
• Access items in the list
• Determine the size of the list
Array vs ArrayList
Classification
Classification
Linear Data Structures Non-Linear Data Structures
Elements arranged in a linear fashion Elements arranged in a non-linear fashion
Each element is connected to one other element Each element is connected to n-other elements
only
Static vs dynamic
• Static Data Structures
• Size is declared and fixed at compile time
• Can not store data over the fixed size
• Easy to handle
• Can occupy more storage then required
• Dynamic Data Structures
• Size is not fixed at compile time
• Size can be decided on runtime
• Does occupy storage as required
• Releases memory when no longer needed
Array
• Advantages
• Random access
• Easy sorting and iteration
• Replacement of multiple variables
• Disadvantages
• Size is fixed
• Difficult to insert and delete
• If capacity is more and occupancy less, most of the array gets wasted
• Needs contiguous memory to get allocated
Dynamic Array: ArrayList
ArrayList: Costs and Benefits
• Dynamic Resizing
• Ordered
• Index Based
• Object based only
• Not synchronized / not thread safe
• Quicker random access
• Insertion and Deletion can take longer time
• Searching an element can take longer time
That’s all for Today!
Thank you
