BSIT Survival Kit

Module 2: Costs, Benefits, and Choosing Data Structures

No single data structure is best for every situation. Each structure has trade-offs involving:

memory usage
speed of insertion
speed of deletion
speed of searching
programming complexity

For example, arrays are simple and fast when directly accessing an element by index, but inserting into the middle of an array may require shifting many elements. Linked lists can grow dynamically, but accessing a specific position is slower because the list must be followed node by node.

Data Structure, Data Type, and ADT Compared

Term	Main Idea	Example
Data type	Defines the kind of value a variable may hold.	`int`, `double`, `char`, `boolean`
Data structure	Organizes data so operations can be performed efficiently.	array, linked list, stack
ADT	Describes behavior and operations without exposing implementation details.	stack ADT, queue ADT, list ADT

Primitive Data Structures

Primitive or basic data structures represent simple individual values. Examples include:

integer
real number
character
Boolean

These are sometimes called atomic because they store values that are usually treated as single units.

Simple Types

Type	Description
Integer	Stores whole numbers.
Real number	Stores decimal or floating-point values.
Character	Stores letters, digits, or symbols as individual characters.
Logical / Boolean	Stores truth values such as `true` or `false`.
Enumeration	Defines a limited set of named values.
Subrange / partial type	Restricts possible values to a smaller range.

Pointer Type

A pointer stores a memory address. It can refer to another variable, object, record, or function. Pointers are especially important in structures such as linked lists, where one node must refer to another.

Structured Types

Structured types group multiple values under one name.

Type	Description
Array	Stores multiple elements of the same type under one name.
String	Stores a sequence of characters.
Record / structure	Stores related fields that may have different types.

Abstraction and Encapsulation

Abstraction hides unnecessary details and focuses on what something does.

Encapsulation groups data with the operations that work on it and protects internal details from direct outside access.

An ADT works like a black box: the user knows the allowed operations and expected results, but does not need to know the internal implementation.

Logical and Physical Forms

Every data structure can be viewed in two ways:

Form	Description
Logical form	The concept or behavior of the structure, such as a stack where the last item added is removed first.
Physical form	The actual memory implementation, such as an array-based stack or linked-list-based stack.

Characteristics of Data Structures

Characteristic	Description	Example
Linear	Items are arranged in sequence.	array
Nonlinear	Items are connected in branching or network-like relationships.	tree, graph
Homogeneous	All elements have the same type.	array of integers
Non-homogeneous	Elements may have different types.	record / object
Static	Size is fixed before or during compilation.	fixed-size array
Dynamic	Size can grow or shrink while the program runs.	linked list

Common Data Structures

Structure	Main Use
Array	Store same-type elements using indexes.
Stack	Process items in Last-In, First-Out order.
Queue	Process items in First-In, First-Out order.
Linked list	Store items as connected nodes.
Tree	Represent hierarchical relationships.
Graph	Represent networks of connected objects.
Trie	Store and search strings by prefix.
Hash table	Store key-value pairs for fast lookup.