Government Polytechnic, JOIDA (162) Dept.

of CSE

Government of Karnataka
Department of Technical Education

Data Structures with

Python
SAYYAN SHAIKH
Course Code 25CS33I
Semester 3 (Third)
Programme Computer Science & Engineering
Type Integrated (Theory + Practice)
Teaching Scheme 3 : 0 : 4 (7 hrs/week, 5 credits)
CIE / SEE 50 / 50 (Practice)

Covers Weeks 1–13 as per the prescribed syllabus, with worked examples,
diagrams, verified code & outputs, weekly summaries and CIE evaluation schemes.

Data Structures with Python (25CS33I) Page 1

Government Polytechnic, JOIDA (162) Dept. of CSE

How to Read These Notes

These notes use a consistent visual style so that the most important things are easy to spot
while revising. The legend below explains every visual cue used throughout the book.

Visual cue Meaning

Red boxed text An exam-important DEFINITION. Learn these word-for-word.

Underlined word A key technical term you must know and be able to explain.
Grey box Python code or command syntax.
Green box The real OUTPUT produced when the code is run.
Yellow box Key points to remember at the end of each week.
Blue box An extra note, tip or clarification.
Tip: Read the diagram first, then the definition, then run the code yourself. You remember a
data structure far better after you have typed and executed it once.

Data Structures with Python (25CS33I) Page 2

Government Polytechnic, JOIDA (162) Dept. of CSE

Table of Contents
How to Read These Notes .................................................................................................... 2
Table of Contents.................................................................................................................. 3
Scheme of Evaluation — CIE Theory Test .......................................................................... 32
Scheme of Evaluation — CIE Practice Test ........................................................................ 35

Data Structures with Python (25CS33I) Page 3

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 1
Introduction to Data Structures

1.1 What is a Data Structure?

DEFINITION Data Structure
A particular way of organising and storing data in a computer’s memory so that it can be
accessed and modified efficiently.
Software has to store data — a list of students, marks, names, etc. How we arrange that
data in memory decides how fast and how easily we can use it. Choosing the right data
structure is the first step in writing an efficient program.
• Why study them: the same problem can be slow or fast depending on the structure
chosen.
• Goal: store data, then perform operations on it with the least time and memory.

1.2 Operations on Data Structures

These are the basic actions performed on the data held inside any structure.
• Traversal — visiting every element once (e.g., to print or process it).
• Insertion — adding a new element into the structure.
• Deletion — removing an existing element.
• Searching — finding the location of a particular element.
• Sorting — arranging elements in ascending or descending order.
• Merging — combining two structures into one.

1.3 Classification of Data Structures

Figure 1.1 Classification of data structures

Data Structures with Python (25CS33I) Page 4

Government Polytechnic, JOIDA (162) Dept. of CSE

Primitive vs Non-Primitive
DEFINITION Primitive Data Structure
The basic built-in types that the machine handles directly — int, float, str (string) and bool
(Boolean).

DEFINITION Non-Primitive Data Structure

Structures built using primitive types to hold a group of values — e.g., array, list, stack,
queue, tree, graph.
Built-in Data Structure User-Defined Data Structure
Already provided by Python (list, tuple, set, Created by the programmer using a class
dict). (stack, queue, linked list, tree).
Ready to use, no extra code needed. Must be coded before use, giving full control.
Best for general everyday storage. Best for modelling a real problem exactly.

Linear vs Non-Linear
DEFINITION Linear Data Structure
Elements are arranged one after another in a sequence; each element has one predecessor
and one successor (array, stack, queue, linked list).

DEFINITION Non-Linear Data Structure

Elements are arranged in a hierarchy or network, not in a single line (tree, graph).

1.4 A Linear Example — the Array

Figure 1.2 An array stores same-type items in contiguous memory

Python does not have a true array type by default; a list is used in its place. The index of
the first element is always 0.

Python
num = [10, 20, 30, 40, 50]
print(num[0]) # first element
print(num[-1]) # last element
print(len(num)) # number of elements

OUTPUT
10
50
5

1.5 Python Recap — Functions

Data Structures with Python (25CS33I) Page 5

Government Polytechnic, JOIDA (162) Dept. of CSE

A function is a reusable block of code that performs one task. It is the main tool you will use
to keep programs organised throughout this course.

Syntax & example

def greet(name): # def keyword, function name, parameter
return "Hello " + name

print(greet("Asha")) # function call

OUTPUT
Hello Asha

WEEK SUMMARY
• A data structure is a way to organise data so operations on it are fast and memory-light.
• Six core operations: traversal, insertion, deletion, searching, sorting, merging.
• Data structures are classified as primitive/non-primitive and linear/non-linear.
• Built-in structures (list, tuple, set, dict) are ready-made; user-defined ones are built with
classes.
• Functions (def … return) are the building block for writing clean programs.

KEY POINTS TO REMEMBER

• Remember the 4 primitives: int, float, str, bool.
• Linear = a line (stack, queue, list); Non-linear = a tree/graph.
• Array/list indexing always starts at 0, last item is index -1.
• Trick — “T I D S S M” = Traversal, Insertion, Deletion, Searching, Sorting,
Merging.

Data Structures with Python (25CS33I) Page 6

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 2
Sets and Tuples

2.1 Sets
DEFINITION Set
An unordered collection of unique elements — duplicates are automatically removed and the
items have no fixed position.
• Unordered: items have no index; you cannot do set[0].
• Unique: a value can appear only once.
• Mutable: you can add or remove elements, but each element must itself be immutable.
Creating & modifying a set
colours = {"red", "green", "red", "blue"}
print(colours) # duplicate 'red' removed
[Link]("yellow") # insertion
[Link]("green") # deletion

OUTPUT
{'red', 'green', 'blue'}

Set Operations

Figure 2.1 Union, intersection, difference and symmetric difference

Python
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}
print("Union:", A | B)
print("Intersection:", A & B)
print("Difference A-B:", A - B)
print("Symmetric:", A ^ B)

OUTPUT
Union: {1, 2, 3, 4, 5, 6, 7}
Intersection: {4, 5}
Difference A-B: {1, 2, 3}
Symmetric: {1, 2, 3, 6, 7}

2.2 Tuples
DEFINITION Tuple
An ordered collection of items that is immutable — once created, its elements cannot be
changed, added or removed.
• Ordered & indexed: supports indexing and slicing like a list.

Data Structures with Python (25CS33I) Page 7

Government Polytechnic, JOIDA (162) Dept. of CSE

• Immutable: safe for fixed data such as coordinates or database records.

Packing puts several values into one tuple; unpacking pulls them back into separate
variables.

Python
student = (101, "Asha", 2007) # packing
sid, name, year = student # unpacking
print("ID:", sid, "Name:", name, "Year:", year)
print("Slice:", student[0:2])

OUTPUT
ID: 101 Name: Asha Year: 2007
Slice: (101, 'Asha')

Set vs Tuple vs List — quick comparison

Feature Set Tuple List
Ordered? No Yes Yes
Duplicates? No Yes Yes
Changeable? Yes No (immutable) Yes
Syntax {} () []

WEEK SUMMARY
• A set is unordered and stores only unique values; great for removing duplicates.
• Set operations: union ( | ), intersection ( & ), difference ( - ), symmetric difference ( ^ ).
• A tuple is ordered but immutable — ideal for fixed records.
• Packing builds a tuple from values; unpacking spreads a tuple into variables.

KEY POINTS TO REMEMBER

• Braces tell the type: {} set, () tuple, [] list.
• Sets kill duplicates automatically — the fastest way to find unique items.
• Tuple is “write-protected”: use it when data must never change.
• Operator memory: | = Union (joins), & = And/Intersection (common).

Data Structures with Python (25CS33I) Page 8

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 3
Lists and Dictionaries

3.1 Lists
DEFINITION List
An ordered, changeable (mutable) collection that can hold items of any type and allows
duplicate values.
The list is the most-used Python structure. Common operations:
• append(x) — add x at the end.
• insert(i, x) — insert x at index i.
• remove(x) / pop(i) — delete by value / by index.
• sort() — arrange in order; [a:b] — slicing.
Python
marks = [50, 90, 70]
[Link](85) # add at end
[Link]() # ascending order
print(marks)
print(marks[1:3]) # slice

OUTPUT
[50, 70, 85, 90]
[70, 85]

List Comprehension
DEFINITION List Comprehension
A short, single-line way to build a new list from an existing sequence, optionally with a
condition.
Python
nums = [1, 2, 3, 4, 5, 6]
# square even numbers, multiply odd numbers by 3
result = [n*n if n%2==0 else n*3 for n in nums]
print(result)

OUTPUT
[3, 4, 9, 16, 15, 36]

NOTE
• This exact example appears in the CIE model question paper (Section 1, Q1-b). Make
sure you can write it without looking.

3.2 Dictionaries
DEFINITION Dictionary
An unordered collection of key : value pairs, where each key is unique and is used to look up
its value.
• Fast lookup: find a value instantly using its key (not its position).
• Mutable: add, update or delete pairs at any time.

Data Structures with Python (25CS33I) Page 9

Government Polytechnic, JOIDA (162) Dept. of CSE

Python
emp = {"id": 1, "name": "Ravi", "salary": 40000}
emp["dept"] = "CSE" # add a new pair
print([Link]())
print([Link]())
print([Link]("name")) # safe lookup

OUTPUT
dict_keys(['id', 'name', 'salary', 'dept'])
dict_values([1, 'Ravi', 40000, 'CSE'])
Ravi
Useful methods: keys(), values(), items(), get(), update(), pop().

WEEK SUMMARY
• A list is ordered, changeable and allows duplicates — the work-horse structure.
• List comprehension builds a list in one line: [expr for item in seq if condition].
• A dictionary stores key : value pairs and gives very fast key-based lookup.
• Dictionary keys must be unique; values can repeat.

KEY POINTS TO REMEMBER

• List = ordered box you can keep changing; access by index.
• Dict = labelled box; access by key, not position.
• Comprehension pattern: [ output for item in list if test ].
• Use .get(key) instead of [key] to avoid a KeyError.

Data Structures with Python (25CS33I) Page 10

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 4
Strings and Files

4.1 Strings
DEFINITION String
An ordered, immutable sequence of characters enclosed in single or double quotes.
• Indexing: s[0] is the first character, s[-1] the last.
• Immutable: you cannot change a character in place — you build a new string instead.

String manipulation & built-in methods

• Concatenation: "Data" + "Structures" joins strings.
• Repetition: "ab" * 3 gives "ababab".
• Slicing: s[0:4] takes characters 0 to 3.
Python
s = "Data Structures"
print(s[0], s[-1]) # indexing
print([Link]()) # to capitals
print([Link]("Data","Python"))
print([Link]()) # split into words
print("Length:", len(s))

OUTPUT
D s
DATA STRUCTURES
Python Structures
['Data', 'Structures']
Length: 15
Common methods: upper(), lower(), strip(), replace(), split(), find(), count().

4.2 Files
DEFINITION File
A named location on disk used to store data permanently, so that information survives after
the program ends.

File operations
Working with a file follows three steps: open → read/write → close.

Mode Meaning
"r" Read (default). Error if file is missing.
"w" Write. Creates a new file or erases existing content.
"a" Append. Adds to the end of the file.
"r+" Read and write.
Python
# write to a file
with open("[Link]", "w") as f:
[Link]("User logged in\n")

Data Structures with Python (25CS33I) Page 11

Government Polytechnic, JOIDA (162) Dept. of CSE

Mode Meaning
# read it back
with open("[Link]", "r") as f:
print([Link]())

OUTPUT
User logged in

NOTE
• The with statement closes the file automatically — the safest way to handle files.
Common file attributes: [Link], [Link], [Link].

WEEK SUMMARY
• A string is an immutable sequence of characters; index from 0, last is -1.
• Operations: concatenation (+), repetition (*), slicing ([a:b]) plus many methods.
• A file stores data permanently on disk; steps are open → read/write → close.
• File modes: r (read), w (write/overwrite), a (append), r+ (read+write).

KEY POINTS TO REMEMBER

• Strings can’t be edited in place — they are immutable; methods return a new
string.
• Mode memory: r=Read, w=Write(wipes), a=Add(append).
• Always prefer with open(...) as f: — it auto-closes the file.
• Trick — "-".join(list) turns a list of words back into one string.

Data Structures with Python (25CS33I) Page 12

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 5
Error and Exception Handling

5.1 Types of Errors

DEFINITION Syntax Error
A mistake in the grammar of the code (e.g., a missing colon). The program will not run at all
until it is fixed.

DEFINITION Runtime Error (Exception)

An error that occurs while the program is running, such as dividing by zero or opening a
missing file.

DEFINITION Logical Error

The program runs without crashing but gives a wrong result because the logic is incorrect.

5.2 Exception Handling

DEFINITION Exception Handling
The mechanism of catching and responding to runtime errors so that the program does not
crash but continues gracefully.

Figure 5.1 Flow of try / except / finally

Python uses four keywords:

• try — the code that might fail.
• except — runs only if an error occurs.
• else — runs if no error occurs.
• finally — always runs, error or not (used for clean-up).

Data Structures with Python (25CS33I) Page 13

Government Polytechnic, JOIDA (162) Dept. of CSE

Python
try:
a = 10; b = 0
print(a / b)
except ZeroDivisionError:
print("Cannot divide by zero!")
finally:
print("Done")

OUTPUT
Cannot divide by zero!
Done

Common built-in exceptions

Exception Raised when…
ZeroDivisionError a number is divided by zero.
ValueError a value is of the right type but wrong content (int("abc")).
TypeError an operation is applied to a wrong type ("5" + 5).
FileNotFoundError a file to be read does not exist.
IndexError a list index is out of range.
KeyError a dictionary key is not found.

WEEK SUMMARY
• Three error types: syntax (grammar), runtime/exception (during execution), logical
(wrong result).
• Exception handling keeps a program running instead of crashing.
• Keywords: try, except, else, finally.
• finally always runs — perfect for closing files or releasing resources.

KEY POINTS TO REMEMBER

• Syntax error = won’t even start; logical error = runs but wrong.
• Put risky code in try, recovery code in except.
• finally runs no matter what — use it for clean-up.
• Always catch a specific exception (ZeroDivisionError) rather than a bare except.

Data Structures with Python (25CS33I) Page 14

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 6
Recursion

6.1 What is Recursion?

DEFINITION Recursion
A technique where a function solves a problem by calling itself on a smaller version of the
same problem.

Figure 6.1 The call stack winds down and then unwinds for fact(4)

Every recursive call is stored on the call stack. When the simplest case is reached, the calls
return one by one (the stack unwinds).

6.2 Structure of a Recursive Function

DEFINITION Base Case
The simplest condition that stops the recursion — without it the function would call itself
forever.

DEFINITION Recursive Case

The part where the function calls itself with a smaller or simpler input, moving towards the
base case.
Python — factorial
def fact(n):
if n == 1: # base case
return 1
return n * fact(n-1) # recursive case

print("5! =", fact(5))

OUTPUT
5! = 120

Recursion vs Iteration
Recursion Iteration (loops)
Function calls itself. Repeats with for / while.
Uses extra stack memory. Uses very little memory.

Data Structures with Python (25CS33I) Page 15

Government Polytechnic, JOIDA (162) Dept. of CSE

Recursion Iteration (loops)

Short, elegant code. Usually faster.
Needs a base case to stop. Needs a stop condition in the loop.

WEEK SUMMARY
• Recursion = a function that calls itself on a smaller problem.
• Every recursive function needs a base case (to stop) and a recursive case (to shrink).
• Each call is stored on the call stack; the stack unwinds when the base case is hit.
• Iteration is usually faster and lighter, but recursion is cleaner for tree-like problems.

KEY POINTS TO REMEMBER

• No base case = infinite recursion = crash (RecursionError).
• Pattern: if base: return value else: return f(smaller).
• Recursion trades memory for simplicity.
• Trick — always ask: “What is the smallest input, and how do I shrink towards it?”

Data Structures with Python (25CS33I) Page 16

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 7
Abstract Data Types (ADT) and User-Defined Types (UDT)

7.1 Abstract Data Type (ADT)

DEFINITION Abstract Data Type (ADT)
A model that describes WHAT operations a data type provides, without saying HOW they are
implemented internally.
An ADT hides the inner details (this is called abstraction) and exposes only a clean set of
operations. The user knows what it does, not how it does it.
• Common ADTs: Stack, Queue, List, Tree, Graph, Hash Table.

NOTE
• Example: a Stack ADT promises push and pop. Whether it is built with a Python list or a
linked list is hidden from the user.

7.2 User-Defined Type (UDT) — the class

DEFINITION User-Defined Data Type (UDT)
A new data type created by the programmer using the class keyword, bundling data
(attributes) and operations (methods) together.
Key terms: a class is the blueprint; an object is one item made from it; __init__ sets up the
data; self refers to the current object.

Python
class Student:
def __init__(self, name, marks): # constructor
[Link] = name # attribute
[Link] = marks
def display(self): # method
print(f"{[Link]} scored {[Link]}")

s1 = Student("Kiran", 92) # object

[Link]()

OUTPUT
Kiran scored 92

7.3 Using a UDT to Implement an ADT

We use a class (UDT) to actually build an ADT. For example, a Stack ADT is implemented
as a Stack class that stores items in a list and offers push/pop methods — you will do
exactly this in Week 8.

WEEK SUMMARY
• An ADT describes WHAT operations exist (Stack, Queue, Tree…), hiding HOW they
work — this is abstraction.
• A UDT is a programmer-made type built with class, combining attributes + methods.

Data Structures with Python (25CS33I) Page 17

Government Polytechnic, JOIDA (162) Dept. of CSE

• Key class terms: class (blueprint), object (instance), __init__ (constructor), self (current
object).
• ADTs are implemented using UDTs (classes).

KEY POINTS TO REMEMBER

• ADT = the promise (what), UDT/class = the delivery (how).
• Every method’s first parameter is self; the constructor is __init__.
• Class is the blueprint; object is the house built from it.
• Trick — read [Link]() as “run display on object s1”.

Data Structures with Python (25CS33I) Page 18

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 8
Stack (LIFO Structure)

8.1 What is a Stack?

DEFINITION Stack
A linear data structure in which insertion and deletion of elements happen only at one end,
called the top, following the LIFO order.
Think of a pile of plates. You add a plate on the top, and you also remove a plate from the
top. The plate placed last is the one taken out first. A stack works exactly the same way.

DEFINITION LIFO
Last In, First Out — the element inserted most recently is the first one to be removed.

An authentic textbook diagram: push adds on top, pop removes from the top.

Stack operations — push grows the stack upward, pop shrinks it from the top.

8.2 Stack Operations

Operation Meaning Python (list)
push Add an item on the top [Link](x)
pop Remove and return the top item [Link]()
peek / top Look at the top item without removing it s[-1]
isEmpty Check whether the stack has no items len(s)==0

NOTE

Data Structures with Python (25CS33I) Page 19

Government Polytechnic, JOIDA (162) Dept. of CSE

Operation Meaning Python (list)

• A Python list already behaves like a stack: append() pushes and pop() removes
from the same (right) end.

8.3 Stack using a Python List

stack_demo.py
stack = [] # empty stack

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

print("Pop :", [Link]()) # removes 30 (last in)

print("Top :", stack[-1]) # peek at new top
print("Stack:", stack)

OUTPUT
Stack : [10, 20, 30]
Pop : 30
Top : 20
Stack: [10, 20]

8.4 Where Stacks are Used

• Undo / Redo in editors — the last action is undone first.
• Browser back button — the last page visited is shown first.
• Function calls — Python keeps a call stack of running functions.
• Expression evaluation and checking for balanced brackets.

WEEK SUMMARY
• A stack is a LIFO structure with one open end called the top.
• Only four operations matter: push, pop, peek, isEmpty.
• A Python list works as a ready-made stack using append() and pop().
• Real uses: undo, browser back, function call stack, bracket matching.

KEY POINTS TO REMEMBER

• LIFO = Last In, First Out. Last plate placed is the first removed.
• push → append() | pop → pop() | peek → s[-1].
• Always check isEmpty before pop, or you get an error on an empty stack.
• Memory trick: a stack of plates — you only touch the top plate.

Data Structures with Python (25CS33I) Page 20

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 9
Queue (FIFO Structure)

9.1 What is a Queue?

DEFINITION Queue
A linear data structure in which elements are inserted at one end (rear) and removed from the
other end (front), following the FIFO order.
Think of a line of people at a ticket counter. A new person joins at the back, and the person
at the front is served first. The one who came first leaves first.

DEFINITION FIFO
First In, First Out — the element inserted first is the first one to be removed.

An authentic textbook diagram: people join at the rear and leave from the front.

Queue operations — enqueue adds at the rear, dequeue removes from the front.

9.2 Queue Operations

Operation Meaning Python (deque)
enqueue Add an item at the rear [Link](x)
dequeue Remove and return the front item [Link]()
front Look at the front item q[0]
isEmpty Check whether the queue is empty len(q)==0

NOTE

Data Structures with Python (25CS33I) Page 21

Government Polytechnic, JOIDA (162) Dept. of CSE

Operation Meaning Python (deque)

• Use [Link] for queues. Removing from the front of a normal list
([Link](0)) is slow; [Link]() is fast.

9.3 Queue using [Link]

queue_demo.py
from collections import deque

q = deque() # empty queue

[Link]("A") # enqueue A
[Link]("B") # enqueue B
[Link]("C") # enqueue C
print("Queue :", q)

print("Dequeue:", [Link]()) # removes A (first in)

print("Front :", q[0]) # new front
print("Queue :", q)

OUTPUT
Queue : deque(['A', 'B', 'C'])
Dequeue: A
Front : B
Queue : deque(['B', 'C'])

9.4 Stack vs Queue

Point Stack Queue
Order LIFO (Last In First Out) FIFO (First In First Out)
Insert at Top Rear
Remove from Top (same end) Front (other end)
Real example Pile of plates Line of people
Python tool list [Link]

9.5 Where Queues are Used

• Printer jobs — documents print in the order they were sent.
• Customer support tickets — served in arrival order.
• CPU task scheduling and handling requests on a server.

WEEK SUMMARY
• A queue is a FIFO structure with two ends: rear (insert) and front (remove).
• Core operations: enqueue, dequeue, front, isEmpty.
• Use [Link] — popleft() removes the front quickly.
• Stack = one end (LIFO); Queue = two ends (FIFO).

KEY POINTS TO REMEMBER

• FIFO = First In, First Out. The first person in line is served first.
• enqueue → append() | dequeue → popleft().

Data Structures with Python (25CS33I) Page 22

Government Polytechnic, JOIDA (162) Dept. of CSE

• Prefer deque over a list for queues — it is much faster at the front.
• Memory trick: a ticket queue — enter at the back, leave from the front.

Data Structures with Python (25CS33I) Page 23

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 10
Singly Linked List

10.1 Why Linked Lists?

A Python list keeps items next to each other in memory. Inserting or deleting in the middle
then forces every later item to shift, which is slow. A linked list stores items anywhere in
memory and joins them with links, so inserting and deleting become easy.

DEFINITION Linked List

A linear data structure in which each element (node) stores its own data and a reference
(link) to the next node; the nodes need not be stored next to each other in memory.

DEFINITION Node
The basic building block of a linked list, made of two parts: the data, and a link (pointer) to the
next node.

An authentic textbook diagram: each box (node) holds data and points to the next.

A singly linked list — head points to the first node; the last node links to None.

10.2 Parts of a Singly Linked List

• Node — holds data and a link next.
• head — a reference to the first node; the entry point of the list.
• next of the last node is None, which marks the end.

10.3 Singly Linked List in Python

singly_linked_list.py
class Node:
def __init__(self, data):
[Link] = data # the value
[Link] = None # link to next node

Data Structures with Python (25CS33I) Page 24

Government Polytechnic, JOIDA (162) Dept. of CSE

class LinkedList:
def __init__(self):
[Link] = None # empty list

def add(self, data): # insert at end

new = Node(data)
if [Link] is None:
[Link] = new
return
cur = [Link]
while [Link]: # walk to last node
cur = [Link]
[Link] = new

def display(self):
cur = [Link]
while cur:
print([Link], end=" -> ")
cur = [Link]
print("None")

ll = LinkedList()
[Link](10); [Link](20); [Link](30)
[Link]()

OUTPUT
10 -> 20 -> 30 -> None

10.4 Array (List) vs Linked List

Point Python List (Array) Linked List
Memory Items stored together Nodes scattered, joined by links
Access by index Fast, direct Slow, must walk from head
Insert / delete in Slow (shifting needed) Fast (just relink)
middle
Size Fixed block, resized internally Grows one node at a time

WEEK SUMMARY
• A linked list joins nodes with links instead of storing items side by side.
• Each node has two parts: data and next.
• head points to the first node; the last node's next is None.
• Linked lists make insertion and deletion easy; arrays give fast index access.

KEY POINTS TO REMEMBER

• Node = data + link. head = door to the list.
• End of list is marked by None, never forget to set it.
• To reach any node you must walk from the head — there is no direct index.
• Memory trick: a treasure hunt — each clue (node) points to the next clue.

Data Structures with Python (25CS33I) Page 25

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 11
Doubly Linked List

11.1 From Singly to Doubly

In a singly linked list you can move forward only. A doubly linked list adds a second link in
each node that points backward, so you can move both ways.

DEFINITION Doubly Linked List

A linked list in which every node has two links — one to the next node and one to the
previous node — allowing movement in both directions.

A doubly linked list — each node links to both the next and the previous node.

11.2 Parts of a Node

• prev — link to the previous node (None for the first node).
• data — the value stored.
• next — link to the next node (None for the last node).

11.3 Doubly Linked List in Python

doubly_linked_list.py
class Node:
def __init__(self, data):
[Link] = data
[Link] = None # link backward
[Link] = None # link forward

class DoublyLinkedList:
def __init__(self):
[Link] = None

def add(self, data): # insert at end

new = Node(data)
if [Link] is None:
[Link] = new
return
cur = [Link]
while [Link]:
cur = [Link]
[Link] = new
[Link] = cur # set backward link

def display(self):
cur = [Link]

Data Structures with Python (25CS33I) Page 26

Government Polytechnic, JOIDA (162) Dept. of CSE

while cur:
print([Link], end=" <-> ")
cur = [Link]
print("None")

dll = DoublyLinkedList()
[Link](10); [Link](20); [Link](30)
[Link]()

OUTPUT
10 <-> 20 <-> 30 <-> None

11.4 Singly vs Doubly Linked List

Point Singly Linked List Doubly Linked List
Links per node One (next) Two (prev and next)
Direction Forward only Forward and backward
Memory per node Less More (extra link)
Delete a known Need previous node Easy, prev is stored
node

WEEK SUMMARY
• A doubly linked list lets you move both forward and backward.
• Each node has three parts: prev, data, next.
• prev of the first node and next of the last node are both None.
• It uses more memory than a singly linked list but is more flexible.

KEY POINTS TO REMEMBER

• Node now has prev, data and next — two links.
• Both ends point to None: [Link] and [Link].
• When inserting, remember to set both links, not just next.
• Memory trick: a train — each coach is joined to the one ahead and behind.

Data Structures with Python (25CS33I) Page 27

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 12
Trees

12.1 A Non-Linear Structure

Stacks, queues and linked lists are linear — items form a single line. A tree is non-linear:
data branches out like a family tree, with one item at the top connected to many below it.

DEFINITION Tree
A non-linear data structure made of nodes connected by edges, in which one node is the root
and every other node has exactly one parent.

A tree — the root at the top, branching into child nodes, ending in leaves.

12.2 Tree Terminology

Term Meaning
Root The topmost node; it has no parent.
Parent A node that has one or more nodes below it.
Child A node directly connected below another node.
Leaf A node with no children (the ends of the tree).
Edge The link connecting a parent to a child.
Subtree Any node together with all the nodes below it.
Height The longest path from the root down to a leaf.
Level The distance of a node from the root (root is level 0).

12.3 Binary Tree

DEFINITION Binary Tree
A tree in which every node has at most two children, usually called the left child and the right
child.

Data Structures with Python (25CS33I) Page 28

Government Polytechnic, JOIDA (162) Dept. of CSE

The binary tree is the most used tree in programming. Because each node has at most two
children, it is simple to store and to search.

12.4 Representing a Tree Node in Python

binary_tree.py
class Node:
def __init__(self, data):
[Link] = data
[Link] = None # left child
[Link] = None # right child

# 1 build this tree

# / \\
# 2 3
# / \\
# 4 5
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
print("Root :", [Link])
print("Its kids :", [Link], [Link])

OUTPUT
Root : 1
Its kids : 2 3

WEEK SUMMARY
• A tree is a non-linear structure that branches from a single root.
• Key terms: root, parent, child, leaf, edge, subtree, height, level.
• A binary tree allows at most two children per node (left and right).
• Each node is an object with data, left and right references.

KEY POINTS TO REMEMBER

• Root on top, leaves at the bottom — the tree grows downward.
• Binary tree = at most two children: left and right.
• Every node except the root has exactly one parent.
• Memory trick: a family tree — one ancestor at the top, branches of descendants
below.

Data Structures with Python (25CS33I) Page 29

Government Polytechnic, JOIDA (162) Dept. of CSE

WEEK 13
Tree Traversal

13.1 What is Traversal?

DEFINITION Tree Traversal
The process of visiting every node of a tree exactly once in a defined order.
Unlike a list, a tree has no single straight line to follow, so we need a rule for the order in
which nodes are visited. The three standard depth-first orders differ only in when the root is
visited.

The three depth-first traversals of the same binary tree and their visiting order.

13.2 The Three Depth-First Traversals

DEFINITION Inorder (Left, Root, Right)
Visit the left subtree, then the node itself, then the right subtree.

DEFINITION Preorder (Root, Left, Right)

Visit the node itself first, then the left subtree, then the right subtree.

DEFINITION Postorder (Left, Right, Root)

Visit the left subtree, then the right subtree, then the node itself last.

13.3 Traversal in Python

tree_traversal.py
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

def inorder(node):
if node:
inorder([Link]) # L
print([Link], end=" ") # Root
inorder([Link]) # R

def preorder(node):
if node:
print([Link], end=" ") # Root
preorder([Link]) # L

Data Structures with Python (25CS33I) Page 30

Government Polytechnic, JOIDA (162) Dept. of CSE

preorder([Link]) # R

def postorder(node):
if node:
postorder([Link]) # L
postorder([Link]) # R
print([Link], end=" ") # Root

root = Node(1)
[Link] = Node(2); [Link] = Node(3)
[Link] = Node(4); [Link] = Node(5)

print("Inorder :", end=" "); inorder(root); print()

print("Preorder :", end=" "); preorder(root); print()
print("Postorder:", end=" "); postorder(root); print()

OUTPUT
Inorder : 4 2 5 1 3
Preorder : 1 2 4 5 3
Postorder: 4 5 2 3 1

NOTE
• All three use recursion (Week 6). The only difference is the line at which print
appears: before the children (preorder), between them (inorder), or after them
(postorder).

13.4 Level-Order Traversal (Breadth-First)

A fourth order visits the tree level by level, top to bottom and left to right. It uses a queue
(Week 9) instead of recursion. For the tree above, the level-order is 1 2 3 4 5.

WEEK SUMMARY
• Traversal means visiting every node exactly once in a fixed order.
• Inorder = L, Root, R | Preorder = Root, L, R | Postorder = L, R, Root.
• All three depth-first traversals are written with simple recursion.
• Level-order visits the tree level by level and uses a queue.

KEY POINTS TO REMEMBER

• The traversal name tells you where the Root is: Pre=first, In=middle, Post=last.
• Left is always visited before right in all three orders.
• Inorder of a binary search tree gives values in sorted order.
• Memory trick: PRE-In-POST tells the Root’s position — first, middle, last.

Data Structures with Python (25CS33I) Page 31

Government Polytechnic, JOIDA (162) Dept. of CSE

Scheme of Evaluation — CIE Theory Test

NOTE
• This scheme matches the structure of the CIE Theory Test model question paper
(Section 9 of the syllabus).
• Total: 50 marks | Time: 90 minutes | Two sections; the student answers ONE full
question from each section (25 + 25).

Section 1 — answer any ONE full question (25 marks)

Q1 (a) Difference between a tuple and a list — 5 marks
Point to award Marks
Tuple is immutable; list is mutable (the main difference). 2
Syntax shown: tuple ( ) vs list [ ]. 1
Any correct use case (tuple for fixed data, list for changing data). 1
One more valid point (both ordered / both allow duplicates). 1

Q1 (b) Function: square the even numbers and multiply the odd numbers by 3 —
10 marks
For the input [1, 2, 3, 4, 5, 6].

Model answer
def transform(nums):
return [n*n if n%2==0 else n*3 for n in nums]

print(transform([1, 2, 3, 4, 5, 6]))

OUTPUT
[3, 4, 9, 16, 15, 36]

Point to award Marks

Correct function header with a parameter. 2
Correct even / odd test using n % 2. 2
Correct operation: n*n for even, n*3 for odd. 3
Returns or prints the resulting list. 1
Correct output [3, 4, 9, 16, 15, 36]. 2

Q1 (c) Find the oldest person from a list of (name, age) records — 10 marks
Model answer
people = [("Asha", 21), ("Ravi", 25), ("Kiran", 23)]
oldest = people[0]
for person in people:
if person[1] > oldest[1]:
oldest = person
print("Oldest:", oldest[0], "Age:", oldest[1])

OUTPUT
Oldest: Ravi Age: 25

Point to award Marks

Data Structures with Python (25CS33I) Page 32

Government Polytechnic, JOIDA (162) Dept. of CSE

Uses a correct data structure (list of tuples). 2

Initialises a 'maximum' record and loops through the list. 4
Correctly compares ages and updates the oldest. 2
Prints the name and age of the oldest person. 1
Correct output for the given input. 1

Q2 (a) Demonstrate the four set operations — 5 marks

Point to award Marks
Union ( | ) correct. 1
Intersection ( & ) correct. 1
Difference ( - ) correct. 1
Symmetric difference ( ^ ) correct. 1
Correct sample output for all four. 1

Q2 (b) Find the oldest person — 10 marks

Same logic and mark split as Q1 (c) above.

Q2 (c) Build a tuple from two sets — 10 marks

Typical task: take two sets, combine them (union), and store the result as a tuple.

Point to award Marks

Creates the two sets correctly. 2
Applies the correct set operation (union / intersection as asked). 4
Converts the result to a tuple using tuple(...). 3
Correct output. 1

Section 2 — answer any ONE full question (25 marks)

Q3 Trace the nested-sum program that uses a stack — 25 marks
Program input: [1, 2, (3, 4), [5, (6, 7)], 8]. The program flattens the nested
structure using a stack and adds all the numbers.

Point to award Marks

Explains that the stack starts with the whole structure inside it. 3
Explains the while-loop: pop one item, then look inside it. 4
Explains the isinstance check: lists/tuples are pushed back; numbers are added. 5
Correctly traces the stack contents at each step. 6
Shows the running total building up (1+2+3+4+5+6+7+8). 4
States the correct final answer = 36. 3

NOTE

Data Structures with Python (25CS33I) Page 33

Government Polytechnic, JOIDA (162) Dept. of CSE

Point to award Marks

• Answer key — final total = 36. Award the trace marks even if the student lists the
stack states in a slightly different pop order, as long as every number is counted
exactly once.

Q4 Two short programming tasks — 25 marks (a = 13, b = 12)

Q4 (a) Work on a collection (count items, find an item's index, take the last five, list the
unique values) — 13 marks.

Point to award Marks

Correct count using len(); correct index using .index() / loop. 4
Correct slicing for the last five items (list[-5:]). 4
Correct unique values using set() (or Counter). 3
Correct outputs for all parts. 2
Q4 (b) Analyse a piece of text (total length, word count, remove stop-words, capitalise,
check if numeric) — 12 marks.

Point to award Marks

Correct length with len() and word count with split(). 3
Correct stop-word removal (filter words not in a stop-word list). 4
Correct use of capitalize() / title() and isnumeric() / isalpha(). 3
Correct outputs. 2

WEEK SUMMARY
• Theory test = 50 marks, 90 minutes, two sections, one full question answered from
each.
• Section 1 is built from Weeks 2–3 (sets, tuples, lists, comprehension, dictionaries).
• Section 2 is built from Weeks 4 and 8 (strings, files and the stack trace).
• Award method marks for correct logic even when the final value has a small slip.

Data Structures with Python (25CS33I) Page 34

Government Polytechnic, JOIDA (162) Dept. of CSE

Scheme of Evaluation — CIE Practice Test

NOTE
• This scheme matches the CIE Practice (lab) Test model question paper (Section 10 of
the syllabus).
• Total: 50 marks | Time: 180 minutes | One programming problem, marked on three
areas.

Model problem
Separate a mixed set of inputs into text data and numerical data, then classify every word
as UPPERCASE, lowercase or Mixed-case, and report the totals.

Marks distribution (as per syllabus rubric)

Area Marks
(a) Program Design & Conceptual Clarity 10
(b) Implementation & Execution 30
(c) Best Practices (readability, error handling) 10
Total 50

(a) Program Design & Conceptual Clarity — 10 marks

Point to award Marks
Chooses correct data structures (list/dict for text, list for numbers). 3
Clear plan: read input → separate → classify → count → display. 3
Correct logic for telling text from numbers (isnumeric / isalpha). 2
Correct rule for case classification (isupper / islower / else mixed). 2

(b) Implementation & Execution — 30 marks

Point to award Marks
Reads the input correctly into a usable structure. 4
Correctly separates text items from numerical items. 6
Correctly classifies each word as upper / lower / mixed case. 8
Counts each category and stores the totals. 4
Program runs without errors and gives correct output for normal input. 6
Handles a second sample input correctly (re-run by examiner). 2

(c) Best Practices — 10 marks

Point to award Marks
Meaningful names for variables and functions. 3
Code split into functions; not one long block. 2
Comments explaining the key steps. 2

Data Structures with Python (25CS33I) Page 35

Government Polytechnic, JOIDA (162) Dept. of CSE

Point to award Marks

Handles empty or unexpected input without crashing (try / except or checks). 3

Reference solution (outline)

Reference solution
def classify(items):
text, numbers = [], []
upper = lower = mixed = 0
for x in items:
if [Link](): # numerical data
[Link](int(x))
else: # text data
[Link](x)
if [Link](): upper += 1
elif [Link](): lower += 1
else: mixed += 1
return text, numbers, upper, lower, mixed

data = ["Hello", "WORLD", "python", "42", "Data123", "7"]

text, numbers, u, l, m = classify(data)
print("Text :", text)
print("Numbers:", numbers)
print("UPPER:", u, " lower:", l, " Mixed:", m)

OUTPUT
Text : ['Hello', 'WORLD', 'python', 'Data123']
Numbers: [42, 7]
UPPER: 1 lower: 1 Mixed: 2

NOTE
• Note: "Data123" is counted as Mixed-case because it has both capital and small
letters. "42" and "7" pass isnumeric() so they go to numbers.

WEEK SUMMARY
• Practice test = 50 marks, 180 minutes, one full programming problem.
• Marks split: Design 10, Implementation 30, Best Practices 10.
• Implementation carries the most weight — a running, correct program is essential.
• Award the Best-Practices marks for clean names, functions, comments and safe input
handling.

Data Structures with Python (25CS33I) Page 36