Data Structures
Introduction to Data Structures
Course Instructor: Mr. Rehan Naveed Abbasi
Course Information
• Course Code CS2113
Course Title Data Structures
Credit Hours 4(3,1)
Prerequisites by CS1033 Object
Course(s) and Topics Oriented
Programming
Tentative marks distribution
Assessment items Weightage
• Quiz 10%
• Assignments 10%
• Project 10%
• Midterm 20%
• Final-exam 50%
Copied and Late submissions will not be considered.
Avoid last minute submissions.
TextBook
• Data Structures and Algorithm Analysis in Java
Mark Allen Weiss, Florida International University,
Pearson, 3rd Edition, 2012.
• Reference Books:
• Algorithms, Robert Sedgewick, Kevin Wayne, Addison-
Wesley Professional, 4th Edition, 2011.
• Data Structures: Abstraction and Design Using Java,
Koffman and Wolfgang, Wiley, 2nd Edition, 2010.
Course Contents (1)
• Introduction to data structures
• Linear and non-linear data structures
• Arrays
• Searching algorithms
• Sorting algorithms
• Singly linked list
• Doubly linked list
• Circular linked list
• Stack
Course Contents (2)
• Queues
• Circular Queue, Priority Queues
• Recursion
• Trees
• Binary Search Trees
• Graphs
• Heaps
• Hashing
Basic Terminology-Elementary
Data Organization
• Data are values or a set of values
• Data item refers to single unit of values
• Data item can be categorized as group item or elementary
item
• Group item:
• Data item that can be subdivided into sub items.
• Ex Name : First Name, Middle initial and Last Name
• Elementary item:
• Data item that can not be divided into sub item.
• Ex : Social Security card number / Bank Pass Book Number is
treated as single item
Data Organization
• Entity:
• Something that has certain attributes or properties
which may be assigned values
• Values may be either numeric or non-numeric
• For Example:
• The employee of an organization
Attributes Name Age Employee Code
Values John 33 13472
Data Organization
• Entity Set
• Entity with similar attributes ( e.g all employees of an
organization) form an entity set
• Each attribute of an entity set has a range of values
[ the set of possible values that could be assigned to
the particular attribute]
• Information: Data with given attribute or processed
data
Data Organization
• Field is a single elementary unit of information
representing an attribute of an entity
• Record is the collection of field values of a given
entity
• File is the collection of records of the entities in a
given entity set
The way that data are organized into the hierarchy of fields, records
and files reflects the relationship between attributes, entity sets and
entities.
Data Organization
• Collection of data are frequently organized into a
hierarchy of fields, records and files
Name Age Roll Number Branch
A 17 109cs0132 CSE
B 18 109ee1234 EE
C 19 109ce0012 CE
D 20 108mm0132 MM
Data Structures
• A data structure is a way to logically organize
data that specifies:
• A set of data elements i.e., a data object
• A set of operations which may legally be applied
to elements of this data object.
• Data Structure
• The logical or mathematical model of a particular
organization of data
Data Structures
• Study of Data Structure includes the following three
steps
• Logical or Mathematical description of the structure
• Implementation of the structure on a computer
• Quantitative analysis of the structure, which includes
determining the amount of memory needed to store the
structure and the time required to process the structure
Data Structures
• Manipulation of real-life data (user data) requires the
following essential tasks:
1) Storage representation of user data: User data
should be stored in such a way that computer can
understand.
2) Retrieval of stored data: Data stored in a computer
should be retrieved in such a way that user can
understand.
3) Transformation of user data: Various operations
which require to be performed on user data so that it
can be transformed from one form to another.
Operations
• Data appearing in Data structure are processed by
means of certain operations
• Particular Data structure one chooses for a given
situation depends largely on the frequency with
which specific operations are performed
Major operation
• Traversing: Accessing each record exactly once so
that certain items in the record may be processed
[ Also known as Visiting the record]
• Searching: Finding the location of the record with a
given key value, or finding the locations of all
records which satisfy one or more conditions
Major operation
• Insertion : Adding a new record to the structure
• Deletion : Removing a record from the structure
• Sorting: Arrange the records in some logical order
(Alphabetically according to Name key or
numerically according to Number key)
• Merging: Combining the records in two different
sorted files into single sorted file
Classification of Data Structure
• Data structure are normally divided into two
broad categories:
• Primitive Data Structure
• Non-Primitive Data Structure
Classification of Data Structure
Non Linear
Data
Structure
Primitive Data Structure
• There are basic structures and directly operated
upon by the machine instructions.
• In general, there are different representation on
different computers.
• Integer, Floating-point number, Character
constants, string constants, pointers etc, fall in
this category.
Non-Primitive Data Structure
• There are more sophisticated data structures.
• These are derived from the primitive data
structures.
• The non-primitive data structures emphasize on
structuring of a group of homogeneous (same
type) or heterogeneous (different type) data
items.
Non-Primitive Data Structure
• Lists, Stack, Queue, Tree, Graph are example of
non-primitive data structures.
• The design of an efficient data structure must
take operations to be performed on the data
structure.
Non-Primitive Data Structure
• The most commonly used operation on data
structure are broadly categorized into following
types:
• Create
• Selection
• Updating
• Searching
• Sorting
• Merging
• Destroy or Delete
Primitive vs Non Primitive Data Structure
• A primitive data structure is generally a basic
structure that is usually built into the language,
such as an integer, a float.
• A non-primitive data structure is built out of
primitive data structures linked together in
meaningful ways, such as a or a linked-list,
binary search tree, AVL Tree, graph etc.
Types of Non Primitive Data
Structures
Linear Data Structure
• Linear data structures organize their data elements
in a linear fashion, where data elements are attached
one after the other.
• Data elements in a linear data structure are traversed
one after the other and only one element can be
directly reached while traversing.
Linear Data Structure
• There are two ways of representing linear structures
in memory.
1. One way is to have linear relationship between the
elements represented by means of sequential memory
location. These are called array.
2. The other way is to have linear relationship between
the elements are represented by means of pointer or
links. These structures are called linked list.
Nonlinear Data Structure
• A data item in a nonlinear data structure could be
attached to several other data elements to reflect a
special relationship among them.
• All the data items cannot be traversed in a single
run.
• Non-linear data structures are usually represented
by Linked lists.
Linear and Nonlinear Data
Structure
Array
Linked list
Queue
Tree
Stack
Graph
Applications of Data Structures
• E-commerce Platform Optimization:
• Challenge: An e-commerce company faces issues with slow page
loading times and inefficient search functionality, leading to a poor user
experience.
• Solution: Implementing efficient data structures (such as caching
algorithms, optimized indexing structures) to improve search speed, and
utilizing appropriate data structures for storing and retrieving product
information.
• Healthcare Data Management:
• Challenge: A healthcare organization needs to manage and analyze
large volumes of patient data efficiently while ensuring privacy and
security.
• Solution: Developing a robust data structure and database system to
organize patient records, ensuring quick retrieval for medical
professionals, and implementing security measures to protect sensitive
information.
Applications of Data Structures
• Social Media Analytics:
• Challenge: A social media company wants to improve its
recommendation system and analyse user engagement patterns.
• Solution: Using graph data structures to model user relationships,
employing algorithms to analyse user behaviour, and implementing
efficient data structures for storing and processing large amounts of
user-generated content.
• Financial Fraud Detection:
• Challenge: A financial institution needs to identify and prevent
fraudulent transactions in real-time.
• Solution: Utilizing data structures like hash tables and trees for
quick access to transaction history, implementing algorithms to
detect patterns indicative of fraud, and ensuring rapid response to
potential threats.
Applications of Data Structures
• Traffic Management System:
• Challenge: A city aims to optimize its traffic flow and reduce
congestion at intersections.
• Solution: Implementing graph-based data structures to model the
road network, and applying algorithms to find the most efficient
routes, manage traffic signals dynamically, and predict congestion
patterns.
Algorithm
• Computer algorithm is defined as:
• “A set of steps to accomplish or complete a task that
is described precisely enough that a computer can
run it’’
Properties of Algorithm
• Finiteness:
• The algorithm must always terminate after a finite number of steps.
• Definiteness:
• Each step must be precisely defined; the actions to be carried out
must be rigorously and unambiguously specified for each case.
• Input:
• An algorithm has zero or more inputs, taken from a specified set of
objects.
• Output:
• An algorithm has one or more outputs, which have a specified
relation to the inputs.
• Effectiveness:
• All operations to be performed must be sufficiently basic that they
can be done exactly and in finite length.
Analysis of algorithm
• Algorithms with similar functionalities may differ in
efficiency.
• Efficiency:
• Time Complexity
• Time required by an algorithm to run to completion
• Space complexity
• The amount of memory required by an algorithm to run to
completion