Data Abstraction in

Computer Science
Course Instructor: Maheen Zulfiqar
 What is Data Abstraction?
Definition:
Data abstraction is the process of hiding the details of data storage
and operations, showing only the relevant features.
• Key Idea: Focus on what data is and what operations
can be performed, not how they are implemented.
• Analogy: Driving a car—you use the controls (interface)
• without knowing the inner engine mechanics.
 Why is Abstraction Important?
• Simplifies complex systems
• Enhances code modularity and reusability
• Promotes encapsulation and information hiding
• Facilitates easier debugging and maintenance
• Encourages clear system design
 Levels of Data Abstraction

• Physical Level
• How data is stored (bits, bytes, blocks, disks)
• Logical Level
• What data is stored and relationships (schemas, tables)
• View Level
• What part of data the user interacts with (UI, APIs)
 Abstract Data Types (ADTs)

• Definition: An ADT defines a data type purely by its

behaviour (operations), not implementation.
• Examples:
• List: add, remove, search
• Stack: push, pop
• Queue: enqueue, dequeue
• Tree, Graph, Map
• Key Benefit: Separates interface from implementation
 • Linear Data Structures
AGENDA • Arrays
• Linked Lists
• Stacks
• Classification • Queues
• Linear: Data elements are arranged in • Non-Linear Data Structures
sequence (e.g., Array, Stack) • Trees
• Non-Linear: Hierarchical or networked • Graphs
structure (e.g., Tree, Graph) • Hashing and Hash Tables
• Static: Fixed size (e.g., Array)
• Dynamic: Resizable during runtime (e.g.,
Linked List)
Linear Data Structures (Arrays)
1. Arrays
An array is a basic data structure used to store a fixed-size
collection of elements of the same type. These elements are
arranged in contiguous memory locations, allowing each
element to be indexed or accessed directly using an integer
index.
Cont.
Now, let’s understand arrays with examples in different programming languages, considering an
array of integers representing the ages of students in a classroom:

• In Python
ages = [14, 16, 15, 14, 16]
• In C Language
• In C, arrays must be explicitly declared with their size and can store elements of a single data type.

#include
int main() {
int ages[] = {14, 16, 15, 14, 16}; // Declaration and initialization
printf("Third age: %d\n", ages[2]); // Accessing the third element
return 0;
}
Cont.
• Characteristics of Arrays in Data Structures
• Fixed Size: Once an array is declared, its size cannot be changed. You need to know the number
of elements you will store in the array beforehand.

• Homogeneous Elements: All elements in an array must be of the same data type, such as all
integers, all floats, or all characters.

• Indexed by Integers: Each element in an array is assigned a unique integer called an index, which
identifies its position within the array. Indexing usually starts at 0.

• Efficient Access: Because of the way arrays are stored in memory (contiguously), accessing any
element by its index is very efficient. This direct access using the index is often referred to as
"random access."
Cont.
Basic Operations in Arrays
The basic operations in the Arrays are insertion, deletion, searching, display,
traverse, and update. These operations are usually performed to either
modify the data in the array or to report the status of the array.
Following are the basic operations supported by an array.
• Traverse − print all the array elements one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given index or by the value.
• Update − Updates an element at the given index.
• Display − Displays the contents of the array.
Cont.
Time Complexity:
• Insertion:
• O(n) in the worst case (inserting at the beginning) and O(1) in the best case
(inserting at the end). This is because shifting elements to make space for the
new element can take linear time.
• Deletion:
• O(n) in the worst case (deleting from the beginning) and O(1) in the best case
(deleting from the end). Shifting elements to fill the gap created by the deletion
can take linear time.
Cont.
• Searching:
• O(n) in the worst case (searching for an element that is not present or at the end). This is because
every element in the array might need to be checked.
• Accessing:
• O(1) (constant time). You can access any element directly using its index.
• Reading:
• O(1) (constant time). Reading an element by its index is a quick operation.

Space Complexity:

• Overall: O(n). The space required to store an array grows proportionally to the number of
elements.
Linear Data Structures (Linked Lists)
2. Linked Lists
What is Linked List?
A linked list is a linear data structure which can store a collection of "nodes"
connected together via links i.e. pointers. Linked lists nodes are not stored
at a contiguous location, rather they are linked using pointers to the
different memory locations. A node consists of the data value and a
pointer to the address of the next node within the linked list.
• A linked list is a dynamic linear data structure whose memory size can be
allocated or de-allocated at run time based on the operation insertion or
deletion, this helps in using system memory efficiently. Linked lists can be
used to implement various data structures like a stack, queue, graph, hash
maps, etc.
Cont.
• A linked list starts with a head node which points to
the first node. Every node consists of data which holds
the actual data (value) associated with the node and a
next pointer which holds the memory address of the
next node in the linked list. The last node is called the
tail node in the list which points to null indicating the
end of the list.
Cont.
Linked Lists vs Arrays
• In case of arrays, the size is given at the time of creation and so arrays are of fixed
length where as Linked lists are dynamic in size and any number of nodes can be
added in the linked lists dynamically. An array can accommodate similar types of
data types where as linked lists can store various nodes of different data types.

Linked List:
• Data Structure: Non-contiguous Array:
• by
• Memory Allocation: Typically allocated one Data Structure: Contiguous

one to individual elements • Memory Allocation: Typically allocated to the whole

array
• Insertion/Deletion: Efficient • Insertion/Deletion: Inefficient
• Access: Sequential • Access: Random
Cont.
Cont.
Basic Operations in Linked List
The basic operations in the linked lists are insertion, deletion,
searching, display, and deleting an element at a given key.
These operations are performed on Singly Linked Lists as
given below −
• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.
Linked List - Insertion Operation
Cont.
Cont.
Linked List - Delete Operation
Cont.
Linked List - Search Operation

• Searching for an element in the list using a key

element. This operation is done in the same way as
array search; comparing every element in the list with
the key element given.
1 START
2 If the list is not empty, iteratively check
if the list contains the key
3 If the key element is not present in the list,
unsuccessful search
4 END
Types of Linked Lists:
1. Singly Linked Lists
Singly linked lists contain two "buckets" in one node;
one bucket holds the data and the other bucket holds
the address of the next node of the list. Traversals can
be done in one direction only as there is only a single
link between two nodes of the same list.
Cont.
2. Doubly Linked Lists
Doubly Linked Lists contain three "buckets" in one node;
one bucket holds the data and the other buckets hold
the addresses of the previous and next nodes in the
list. The list is traversed twice as the nodes in the list
are connected to each other from both sides.
Each node points to both the next and previous node, allowing
for traversal in both directions.
Cont.
3. Circular Linked Lists
Circular linked lists can exist in both singly linked list
and doubly linked list.
Since the last node and the first node of the circular
linked list are connected, the traversal in this linked list
will go on forever until it is broken.
The last node points back to the first node, creating a circular
loop.
Time and Space Complexity of Linked
Lists

Time and Space Complexity of Linked Lists

3. Stack
• A stack is a simple data structure where you can only add or remove
items from one end, known as the “top”. Both insertion and deletion
of elements occur at this top end. A stack operates on the Last-In,
First-Out (LIFO) principle, meaning that the most recently added
element is the first one to be removed.
• The stack data structure is a linear data structure that accompanies a
principle known as LIFO (Last In First Out) or FILO (First In Last Out).
Real-life examples of a stack are a deck of cards, piles of books, piles
of money, and many more.
Properties of Stack
1. LIFO Principle: A stack works by the Last-In, First-Out rule. The last
item added is the first one removed.
2. Single Access Point: You can only add or remove items from the top
of the stack.
3. Order Preservation: The order in which you add items is preserved,
with the last item added being the first to leave.
4. Size Flexibility: A stack can either have a fixed size or grow as
needed.
5. Sequential Access: You can only access items in the order they
were added, starting from the top
Basic Operations on Stack in Data Structures

Push Operation

Push operation involves inserting new elements

in the stack. Since you have only one end to
insert a unique element on top of the stack, it
inserts the new element at the top of the stack.

Pop Operation

Pop operation refers to removing the element

from the stack again since you have only one
end to do all top of the stack. So, removing an
element from the top of the stack is termed
pop operation.
Pseudo Code
Push Operation Pop Operation

Step 1: First, check whether or not the stack is empty

Push operation includes various steps, which are as follows :
Step 2: If the stack is empty, then exit
Step 1: First, check whether or not the stack is full
Step 3: If not, access the topmost data element

Step 2: If the stack is complete, then exit Step 4: Decrement the top by one

Step 3: If not, increment the top by one Step 5: Success

Step 4: Insert a new element where the top is pointing

Step 5: Success
Using Stacks in Computers
• Infix, Postfix, and Prefix Notations In • Postfix Notation: The operator is placed after
mathematics and computer science, the operands. This notation does not require
expressions can be written in different parentheses to denote the order of operations.
notations. Examples: A + B = AB+ and (A + B) x C = (AB+) x
• The three main notations are infix, postfix, C = AB + Cx · In AB+, you first encounter the
and prefix notations. operands A and B, followed by the operator +,
indicating that A and B are to be added. In AB
• Infix Notation: The operator is placed between + Cx, you first add A and B, then multiply the
the operands. This is the standard notation result to C.
used in most arithmetic and algebraic • Prefix Notation : The operator is placed before
expressions. Example: A + B or (A+ B) x C · In A the operands. Like postfix notation, prefix
+ B, the operator + is between the operands A notation also does not require parentheses to
and B. Parentheses may be used to clarify the indicate the order of operations. Example:
order of operations. +AB or +A x BC · In this, the operator + comes
before the operands A and B, indicating that A
and B are to be added. In +A x BC, you first
multiply B and C, then add A to the result
Converting an Infix Expression to Postfix
• Converting an infix expression (like 3 + 4 * 5) to postfix notation (like 3 4 5 *+) can
make calculations easier for computers. We use a stack to help with this
conversion. Here's a simple explanation:
1. Start with an empty stack and an empty output list. 2. Read the infix expression
from left to right.
2. If you find an operand, add it directly to the output list.
3. If you find an operator (like +, -, *), push it onto the stack. But, if there is
already an operator on the stack with higher or equal priority, pop it from the
stack to the output list before pushing the new operator.
4. If you find a left parenthesis (, push it onto the stack.
5. If you find a right parenthesis), pop operators from the stack to the output list
until you find a left parenthesis. Remove the left parenthesis from the stack but
do not add it to the output list.
6. When you have processed the entire infix expression, pop any remaining
operators from the stack to the output list.
 Solution
1. Start with an empty stack.
Examples 2. Read the expression from left to right. 3.
When you find a number, push it onto the
Convert the infix stack.
expression 3 + 4 * 5 to 3. Push 3 onto the stack: [3]
postfix notation 4. Push 4 onto the stack: [3, 4]
5. Push 5 onto the stack: [3, 4, 5]
Result: The postfix
6. When you find an operator, pop the required
expression is 3 4 5 * +. number of items from the stack, perform the
operation, and push the result back onto the
Example: Now Evaluate stack.
the postfix expression 3 7. Pop 5 and 4, multiply them: 4 * 5 = 20
4 5 *+ using a stack. 8. Push the result 20 back onto the stack: [3, 20]
9. Pop 20 and 3, add them: 3 + 20 = 23
10. Push the result 23 back onto the stack: [23]
11. The final result on the stack is the answer to
the expression.