📘 Chapter 4: Computational Structures

1. Primitive Computational Structure

Definition:
Primitive computational structures are the basic building blocks used to design more complex
data structures. They help organize and store data in a way that computers can easily process.

Types:

1. List
2. Stack
3. Queue
4. Tree
5. Graph

Lists in Python

1. Definition of List

A list in Python is a collection of ordered and changeable elements. It can store multiple items
(numbers, strings, objects, or even other lists) in a single variable. Lists are written inside square
brackets [ ] and separated by commas.

👉 In simple words: A list is like a basket where you can keep many different things (fruits,
books, toys), and you can add/remove/change them anytime.

📌 Syntax:

list_name = [item1, item2, item3, ...]

📌 Example:

fruits = ["apple", "banana", "mango"]

print(fruits)

📌 Output:

['apple', 'banana', 'mango']

2. List Creation

We can create lists in different ways:

1. Empty List

my_list = []

2. List with Elements

numbers = [10, 20, 30, 40]

3. List with Different Data Types

mixed = [10, "apple", 3.5, True]

4. Using list() Constructor

chars = list(("a", "b", "c"))

3. Properties of Lists

Lists have some important properties:

1. Dynamic: Size of the list can grow or shrink when we add or remove items.

items = [1, 2]
[Link](3) # list grows
print(items) # [1, 2, 3]

2. Size: The length of a list can be found using len().

print(len(items)) # 3

3. Index: Elements are accessed by their index (position). Indexing starts at 0.

print(items[0]) # 1

4. Base Address: In memory, a list has a base address, and indexes are offsets from it
(conceptual).
5. Ordered: List maintains the order of insertion.

letters = ["a", "b", "c"]

print(letters) # ['a', 'b', 'c']

6. Access: We can directly access or modify any element by its index.

 items[1] = 5
print(items) # [1, 5, 3]

7. Collision (Not in Python directly): In memory concepts, if two lists share same
reference, changes in one affect the other.

a = [1, 2]
b = a # b points to same list
b[0] = 99
print(a) # [99, 2]

4. List Operations

(i) Insertion

Adding new elements into the list.

📌 Syntax:

[Link](item) # add at end

[Link](index, item) # insert at given index

📌 Example:

fruits = ["apple", "banana"]

[Link]("mango")
[Link](1, "grapes")
print(fruits)

📌 Output:

['apple', 'grapes', 'banana', 'mango']

(ii) Deletion (Remove by Value)

Removes the given element.

📌 Syntax:

[Link](item)

📌 Example:

fruits = ["apple", "banana", "mango"]

[Link]("banana")
print(fruits)
📌 Output:

['apple', 'mango']

(iii) Deletion (Remove by Index)

Removes element at a particular position.

📌 Syntax:

[Link](index)

📌 Example:

fruits = ["apple", "banana", "mango"]

[Link](1) # removes "banana"
print(fruits)

📌 Output:

['apple', 'mango']

(iv) Searching

Finds whether an element exists in the list.

📌 Syntax:

if item in list:
print("Found")

📌 Example:

numbers = [10, 20, 30, 40]

if 20 in numbers:
print("Yes, 20 is in the list")

📌 Output:

Yes, 20 is in the list

5. Applications of Lists

1. Data Storage and Manipulation

 o Storing student names, marks, employee records.
o Example:
o marks = [85, 90, 78, 92]
o print("Average:", sum(marks)/len(marks))
2. Stack and Queue Implementation
o Using list as stack (push/pop) or queue (append/pop(0)).
3. Matrix Representation
o Lists inside lists represent tables or matrices.
4. Real-Life Applications
o Shopping cart in an online store.
o To-do list apps.

6. Complete Example Program

# Example: Student Marks Management
marks = []

# Insertion
[Link](85)
[Link](90)
[Link](78)
[Link](1, 88)

print("Marks List:", marks)

# Deletion
[Link](78)
print("After removing 78:", marks)

[Link](0)
print("After removing index 0:", marks)

# Searching
if 90 in marks:
print("90 is found in marks")

# Properties
print("Total Students:", len(marks))
print("Marks are Ordered:", marks)

📌 Output:

Marks List: [85, 88, 90, 78]

After removing 78: [85, 88, 90]
After removing index 0: [88, 90]
90 is found in marks
Total Students: 2
Marks are Ordered: [88, 90]
Stack in Python (Detailed Answer)

1. Definition of Stack
A Stack is a linear data structure that follows the principle of LIFO (Last In, First Out).
This means the last element inserted (pushed) will be the first one removed (popped).
It is just like a stack of plates in a cafeteria – the plate placed at the top is the first one to be taken
out.

2. Importance of Stack
 It helps manage data in an organized way.
 Used where reverse order processing is required.
 Plays a vital role in program execution, memory management, and application
control.
 It is widely used in everyday applications like text editors, browsers, and calculators.

3. Interesting Information about Stack

 The CPU itself uses a stack to handle function calls (called the call stack).
 Many real-life systems like undo buttons, navigation systems, compiler parsing, and
recursion are completely dependent on stack.
 It is the backbone for many algorithms in computer science.

4. Stack Operations
(a) Push Operation

Definition:
Push means adding an element at the top of the stack.

Syntax in Python:

[Link](item)

Code Example:

stack = []
[Link](10) # Push 10
[Link](20) # Push 20
[Link](30) # Push 30
print("Stack after push:", stack)

Output:

Stack after push: [10, 20, 30]

Real-Life Example of Push:

Placing dishes on top of each other in a dish rack – the new dish always goes on the top.

(b) Pop Operation

Definition:
Pop means removing the topmost element from the stack.

Syntax in Python:

[Link]()

Code Example:

stack = [10, 20, 30]

[Link]() # Removes 30
print("Stack after pop:", stack)

Output:

Stack after pop: [10, 20]

Real-Life Example of Pop:

Taking the top book out from a pile of books – you can only remove the topmost book first.

5. Applications of Stack (Explained in Detail)

(a) Undo and Redo in Editors

 In Notepad, MS Word, or Photoshop, when you press Undo (Ctrl+Z), the last change
is popped from the stack.
 If you press Redo (Ctrl+Y), the change is pushed back onto the stack.
 This feature is 100% stack-based.
(b) Browser History (Back and Forward Button)

 Every website you visit is pushed into a stack.

 When you press the Back button, the last site is popped.
 If you press Forward, the site is pushed back.
 This ensures smooth navigation through visited pages.

(c) Call Stack (Function Calls in Programming)

 When a function is called in Python (or any language), it is pushed onto the stack.
 When the function finishes execution, it is popped.
 This is how recursion is handled internally.
 Example: Calculating factorial using recursion uses stack frames.

(d) Expression Evaluation (Mathematics / Calculators)

 Stack is used to evaluate postfix, prefix, and infix expressions.

 Example: Converting 2 + 3 * 4 into postfix and solving it uses stack.
 Modern calculators and compilers depend on stack for solving complex equations.

6. Python Program for Stack (Push & Pop)

# Full Python Program for Stack

stack = []

def push(item):
[Link](item)
print(f"{item} pushed into stack")

def pop():
if not stack:
print("Stack is empty")
else:
removed = [Link]()
print(f"{removed} popped from stack")

def display():
print("Current Stack:", stack)

# Using the stack

push(10)
push(20)
push(30)
display()

pop()
display()

push(40)
display()

Output:

10 pushed into stack

20 pushed into stack
30 pushed into stack
Current Stack: [10, 20, 30]
30 popped from stack
Current Stack: [10, 20]
40 pushed into stack
Current Stack: [10, 20, 40]

Queue (Q) in Data Structures

Definition of Queue
A Queue (Q) is a linear data structure that stores elements in an ordered collection, where
insertion takes place at the rear (end) and deletion takes place at the front (beginning).
It follows the principle of FIFO (First In, First Out), which means the element inserted first
will be removed first—just like a line of people waiting at a ticket counter.

Important Points about Queue

1. Queue works on FIFO rule.
2. Insertion is called Enqueue (EQ), deletion is called Dequeue (DQ).
3. Queue has two pointers: Front (removal) and Rear (insertion).
4. Queues are widely used in computer science, operating systems, and networking.
5. Real-life example: A queue at a bus stop – the first person in line gets on the bus first.

Queue Operations
 Enqueue (EQ): Insert an element at the rear.
  Dequeue (DQ): Remove an element from the front.
 Peek/Front: Show the first element without removing it.
 isEmpty: Check if the queue is empty.
 isFull: Check if the queue is full (in fixed-size queues).

Types of Queue
1. Simple Queue – Basic FIFO structure.
2. Circular Queue – Rear connects back to front when full.
3. Priority Queue – Elements are dequeued based on priority, not position.
4. Deque (Double-Ended Queue): Elements can be inserted or removed from both front
and rear.

Queue Operations Syntax

Enqueue (EQ)
[Link](item)

Dequeue (DQ)
[Link](0)

Python Example Code

# Queue implementation in Python
queue = []

# Enqueue (Insert)
[Link](10)
[Link](20)
[Link](30)
print("Queue after enqueue:", queue)

# Dequeue (Remove)
removed = [Link](0)
print("Removed Element:", removed)
print("Queue after dequeue:", queue)

# Peek
print("Front Element:", queue[0])

Output:
Queue after enqueue: [10, 20, 30]
Removed Element: 10
Queue after dequeue: [20, 30]
Front Element: 20

Real-Life Example of Queue

 People standing in a line at a bank counter.
 First person goes first, then the second, and so on.

Applications of Queue in Detail

1. CPU Process Scheduling (Operating System)

 The CPU executes processes using queues.

 In Round Robin Scheduling, processes are kept in a circular queue.
 The first process enters first and gets CPU first. If incomplete, it goes back to the end of
the queue.

2. Data Packets in Networking

 Routers and switches use queues to store data packets.

 Packets arrive in order and are sent forward in the same order (FIFO).
 Prevents data loss and ensures fair communication.

3. Job Scheduling

 In printers, jobs are scheduled using a queue.

 The first document sent to the printer is printed first.

4. Breadth First Search (BFS) in Graphs

 BFS algorithm uses a queue to explore nodes level by level.

 Example: In social networks, BFS helps find friends of friends.
5. Message Queue in Distributed Systems

 In cloud computing and distributed systems, Message Queues manage communication

between different services.
 Example: Amazon SQS (Simple Queue Service).

🌳 Tree
Definition

A Tree is a non-linear data structure that organizes elements in a hierarchical form, just like
a real tree with a root and branches.

Important Points of Tree

 A tree is made of nodes connected by edges.

 The topmost node is called the root.
 Every node can have child nodes.
 Nodes without children are called leaf nodes.
 A tree is widely used to represent hierarchical relationships.

Example in Real Life

 Family Tree → Shows parents, children, and grandchildren.

 File System → Folders inside folders and files.

Diagram / Structure of Tree

Root
/ \
Child1 Child2
/ \ \
Leaf1 Leaf2 Leaf3

Properties of Tree

 Root Node → The first node (top of the tree).

  Edges → Connections between parent and child nodes.
 Height → The longest path from root to a leaf node.
 Leaf Node → Node with no children.
 Balanced Tree → A tree where left and right subtrees are almost equal in height.

Applications of Tree

 📂 File System (organizing folders and files).

 ❌ File System Deletion (deleting a folder deletes all files inside it).
 📊 Hierarchical Data Representation (organization structure of a company).
 ✅ Decision Making (decision trees in AI & ML).

💻 Python Example of Tree

# Node structure of a Tree
class Node:
def __init__(self, data):
[Link] = data
[Link] = []

def add_child(self, child):

[Link](child)

def display(self, level=0):

print(" " * level * 2 + str([Link]))
for child in [Link]:
[Link](level + 1)

# Creating tree structure

root = Node("Root")
child1 = Node("Child1")
child2 = Node("Child2")

root.add_child(child1)
root.add_child(child2)

child1.add_child(Node("Leaf1"))
child1.add_child(Node("Leaf2"))
child2.add_child(Node("Leaf3"))

# Display Tree
[Link]()

Output of Python Code

Root
Child1
Leaf1
 Leaf2
Child2
Leaf3

🚀 Applications of Tree in Detail with Python

Example: File System Simulation
class FileSystem:
def __init__(self, name, is_file=False):
[Link] = name
self.is_file = is_file
[Link] = []

def add(self, child):

[Link](child)

def display(self, level=0):

print(" " * level * 2 + ("📁 " if not self.is_file else "📄 ") + [Link])
for child in [Link]:
[Link](level + 1)

# Example File System

root = FileSystem("C:")
docs = FileSystem("Documents")
pics = FileSystem("Pictures")
file1 = FileSystem("[Link]", True)
file2 = FileSystem("[Link]", True)

[Link](docs)
[Link](pics)
[Link](file1)
[Link](file2)

# Display File System Tree

[Link]()

Output

📁 C:
📁 Documents
📄 [Link]
📁 Pictures
📄 [Link]

✅ This shows how trees are used in file systems to organize files and folders.
Introduction to Graph

Definition

A Graph is a non-linear data structure consisting of a set of nodes (vertices) and edges that
connect pairs of nodes. It is used to represent relationships between objects.

Information

 Graphs are widely used in computer science, mathematics, and real-life problems.
 A vertex (node) represents an entity, and an edge (link) represents a relationship
between two entities.
 Graphs can be directed (one-way relationships) or undirected (two-way relationships).
 They can also be weighted (edges have cost/weight like distance, time, or price).

Practical Life Example

 Social Media: People as nodes, friendships as edges.

 Google Maps: Cities as nodes, roads as edges with weights (distance).
 Airline Routes: Airports as nodes, flights as edges.

# Example: Simple graph representation in Python using dictionary

graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"]
}
print("Graph Representation:", graph)

📌 Real Life Example: Imagine bus stops as nodes and routes between them as edges.

Graph in Different Format (Relation with Tree)

 Tree is a special type of graph (acyclic, connected).
 Graph can have cycles, while trees cannot.

Points to Note:

1. Trees are hierarchical, graphs are general.

 2. Trees have one root, graphs may not.
3. Trees are acyclic, graphs may have cycles.
4. Every tree is a graph, but not every graph is a tree.

Characteristics of Graph
1. Vertices (Nodes) → Represent entities.
2. Edges (Links) → Represent connections.
3. Can be Directed/Undirected.
4. Can be Weighted/Unweighted.

Properties of Graph

1. Degree

 Definition: The number of edges connected to a node.

 In directed graph:
o In-degree → number of incoming edges.
o Out-degree → number of outgoing edges.

# Example: Degree calculation

graph = {"A": ["B", "C"], "B": ["C"], "C": ["A"]}
degree = {node: len(adj) for node, adj in [Link]()}
print("Degrees of Nodes:", degree)

📌 Practical Example: In a social network, the degree of a person = number of friends.

2. Rate (Connectivity / Density)

 Definition: Measures how connected the graph is.

 Formula: Density = 2 × |E| / (|V| × (|V|-1)) for undirected graphs.

# Example: Density of Graph

V = 4 # vertices
E = 3 # edges
density = 2*E / (V*(V-1))
print("Density of Graph:", density)

📌 Practical Example: In a road network, density tells how many direct routes exist compared
to possible routes.
3. Direction

 Definition: Shows if an edge has a specific direction (from one node to another).
 Directed graphs → one-way relationship.
 Undirected graphs → mutual relationship.

# Directed Graph Example

graph = {"A": ["B"], "B": ["C"], "C": ["A"]}
print("Directed Graph:", graph)

📌 Practical Example:

 One-way roads = Directed.

 Two-way roads = Undirected.

Types of Graph

1. Directed Graph (Digraph)

 Definition: Edges have a direction (A → B).

 Information: Used where relationships are one-way.

# Directed Graph Example

directed_graph = {"A": ["B"], "B": ["C"], "C": []}
print("Directed Graph:", directed_graph)

📌 Real Life Example: Twitter follow system → You can follow someone, but they may not
follow back.

Diagram:

A → B → C

2. Undirected Graph

 Definition: Edges have no direction (A — B).

 Information: Relationships are two-way.

# Undirected Graph Example

undirected_graph = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print("Undirected Graph:", undirected_graph)
📌 Real Life Example: Facebook friends → If A is a friend of B, B is also a friend of A.

Diagram:

A — B
|
C

3. Weighted Graph

 Definition: Each edge has a weight (cost, distance, or time).

 Information: Used in shortest path problems.

# Weighted Graph Example

weighted_graph = {
"A": {"B": 4, "C": 2},
"B": {"C": 5, "D": 10},
"C": {"D": 3},
"D": {}
}
print("Weighted Graph:", weighted_graph)

📌 Real Life Example: Google Maps → Distance between cities is edge weight.

Diagram:

A --4--> B
| |
2 10
| |
C --3--> D

Applications of Graphs (Detailed)

1. Social Networks → Represent users and their connections.
2. Google Maps & GPS → Shortest path (Dijkstra’s algorithm).
3. Computer Networks → Routers and data transfer as nodes and edges.
4. Recommendation Systems → Amazon product suggestions.
5. Web Page Ranking → Google uses graphs to rank websites.
6. Job Scheduling → Dependency graphs in operating systems.

Computational Structure

What is it?
A Computational Structure is the way in which a computer system organizes, processes, and
manages data, instructions, and operations to perform tasks efficiently.

In simple words:
It is like the blueprint of how a computer thinks, stores data, and solves problems using
algorithms, hardware, and software.

Some Important Points about Computational Structure

1. Foundation of Computer Science
o It explains how data structures, algorithms, and architectures work together to
solve problems.
o Example: How your computer stores a number, processes it, and shows the
result.
2. Levels of Structure
o Hardware level: Circuits, processors, memory.
o Software level: Programs, operating systems.
o Algorithm level: Step-by-step instructions to solve problems.
3. Data Organization
o It decides how data is stored (stack, queue, graph, tree).
o Better structure → faster and smarter programs.
4. Efficiency
o Different computational structures make solving problems faster and less
memory-consuming.
o Example: Searching in a tree is faster than searching in an unsorted list.

Amazing Information about Computational Structure

✨ Here are some cool facts:

 DNA as a Computer: Scientists are creating computational structures inside DNA

molecules, which could replace traditional silicon chips in the future.
 Brain-Inspired Computing: Modern AI uses neural networks, a computational
structure inspired by the human brain.
 Quantum Computational Structures: Unlike normal computers, quantum computers
use qubits, which can perform millions of computations at once.
 Everyday Life Example: When you Google Search, a massive computational structure
(data centers, algorithms, ranking models) finds your answer in less than a second!