Data Structures and
Algorithms
What is Data Structure?
• Data structure is a way of collecting and
organizing data in such a way that we can perform
operations on these data in an effective and
sometimes efficient way.
Learning about computers does not stop in
learning how to do programs to run in them
By efficient we mean a problem has to be solved
within the given time and space constraints.
The cost of a solution equates to the
amount of resources consumed.
How to solve problems efficiently?:
Analyze the problem to determine the resource constraints a solution must meet.
Determine the operations that must be supported (e.g., record search, insertion,
deletion, etc.)
Quantify the constraints for each operation (e.g., search operations must be
very fast)
Select data structure that best meet these requirements.
Cost and Benefits
Each data structures requires spaces for each data item it stores,
time to perform each operation, and some programming effort to implement it.
Every data structure has costs and benefits.
Rarely one data structure is better than another in all situations
Classification of Data Structures
Basic Data Type or
Primitive Data Structures
• Basic Data Type or Primitive Data Structures represent a set of
individual data and is frequently used to create a program.
Sometimes called atomic data structure as they represent a form
where data can no longer be divided or have no parts. This group
can be further divided into:
1. Simple Type and
2. Pointer Type.
Simple Type
• Simple type is the most basic data type which is usually declared according to
the syntax rule of a programming language.
1. Integer type – represents integers or whole numbers where in the maximum or
minimum value is the unit of data that a computer can process at one time and is
determined by the length of one word.
2. Real number type – represent fixed-point and floating-point numbers
3. Character type – comprised of alphabets, numerals, and symbols as characters. A
character code is expressed as a binary number inside a computer.
4. Logical type – sometimes referred to as Boolean type where the values are used in
performing logical operations such as AND, OR, and NOT.
5. Enumeration type – a data type that enumerates all possible values of variables.
6. Partial type – used to specify an original-value subset by constraining existing data
types, that is identifying upper and lower limits of a variable.
Pointer Type
• Pointer type are addresses that are allocated in a main memory
unit. Pointer types are used to refer to variables, file records, or
functions.
Structure Type or
Simple Data Structure
• Structure Type or Simple Data Structure is a data structure that contains
a basic data type or any of the defined data types as its elements.
• They represent a collection of data elements
1. Array type or array is simply a finite set of elements having the same type referenced
under a common name.
2. String or a collection of character elements.
3. Record type on the other hand is also a set of elements but this time of different data
types referenced under a common name.
Abstract Data Type
• Abstract Data Type is a part of Basic Data Structure but represents those
under Problem- oriented Data Structure. Abstract Data Type or ADT is
almost always synonymous to Data Structures but represents more of a
logical description (abstract) rather than actual implementation. ADT is
basically a mathematical model where a set of data values and its associated
operations are precisely specified independent of any particular
implementation.
Abstract Data Type
(Information Hiding, Abstraction, Encapsulation)
Logical and Physical Forms
1. Logical form: definition of the data item within an ADT (e.g. integers in
mathematical sense: +,-, *, / (operations)
2. Physical form: implementation of the data item (e.g. 16 or 32 bit integers)
Classification of Data Structures
based on Characteristics
Types of data structures
Data structure types are determined by what types of operations are required
or what kinds of algorithms are going to be applied.
• Arrays - An array stores a collection of items at adjoining memory locations. Items
that are the same type get stored together so that the position of each element can be
calculated or retrieved easily. Arrays can be fixed or flexible in length.
• Stacks - A stack stores a collection of items in the linear order that operations are
applied. This order could be last in first out (LIFO) or first in first out (FIFO).
• Queues - A queue stores a collection of items similar to a stack; however, the
operation order can only be first in first out.
Types of data structures
• Linked lists - A linked list stores a collection of items in a linear order. Each
element, or node, in a linked list contains a data item as well as a reference, or link, to
the next item in the list.
• Trees - A tree stores a collection of items in an abstract, hierarchical way. Each node
is linked to other nodes and can have multiple sub-values, also known as children.
• Graphs - A graph stores a collection of items in a non-linear fashion. Graphs are
made up of a finite set of nodes, also known as vertices, and lines that connect them,
also known as edges. These are useful for representing real-life systems such as
computer networks.
Types of data structures
• Tries - A trie, or keyword tree, is a data structure that stores strings
as data items that can be organized in a visual graph.
• Hash tables - A hash table, or a hash map, stores a collection of
items in an associative array that plots keys to values. A hash table
uses a hash function to convert an index into an array of buckets
that contain the desired data item.