Unit-III | Queue & Linked List

Data Structures
UNIT-III: Queue and Linked List

Page 1
 Unit-III | Queue & Linked List

Python Basics

Variables
A variable is a name that holds a value.
x = 10
This means: create a box called x, and put the number 10 inside it. Later, when you write x, Python will
give you 10 back.

Lists
A list is like a row of boxes, each holding a value. We will use lists as our 'array'.
numbers = [10, 20, 30, 40]
print(numbers[0]) # prints 10 (first box)
print(numbers[1]) # prints 20 (second box)
print(numbers[-1]) # prints 40 (last box)
[Link](50) # adds 50 at the end → [10,20,30,40,50]
[Link](0) # removes first item → [20,30,40,50]
print(len(numbers)) # prints 4 (how many items)
REMEMBER: Python counts from 0, not 1. First item is numbers[0].

Dictionaries
A dictionary holds pairs: a NAME (called a key) and a VALUE. Think of it like a tiny form with labeled
fields.
student = {'name': 'Riya', 'marks': 85}
print(student['name']) # prints Riya
print(student['marks']) # prints 85
student['marks'] = 90 # change a value
print(student['marks']) # prints 90
WHY WE USE THIS: In this unit, every 'node' of a linked list will be a dictionary with two fields — 'data'
(the value) and 'next' (a link to the next node).

None
None is Python's way of saying "nothing" or "empty". We use it to say "this link points to nowhere."
x = None
print(x) # prints None

Page 2
 Unit-III | Queue & Linked List

if x is None:
print("x is empty")

global keyword
Normally, a variable created inside a function lives only inside that function. If we want to change a
variable that lives OUTSIDE the function, we must say 'global' first.
count = 0
def increase():
global count # tells Python: I want to change the outer count
count = count + 1
increase()
increase()
print(count) # prints 2
WHY THIS MATTERS: Our queues and linked lists use global variables (front, rear, head) so that all
functions can see and update them. Every function that changes them must start with 'global'.

Page 3
 Unit-III | Queue & Linked List

PART A — QUEUES

What is a Queue?
Imagine it's Monday morning at the Bengaluru Metro station. The ticket counter opens at 8:45 AM.
Twenty people are standing in a line. Who gets their ticket first? The one who came first. The one who
came last waits the longest. This is called FIFO — First In, First Out. That line is a QUEUE.

A QUEUE is a collection of items where:

• New items join at one end — we call this end the REAR (or back).
• Old items leave from the other end — we call this end the FRONT.
• The first item to join is always the first to leave. This rule is called FIFO.

leave here join here ↓

↓ FRONT → [ 10 ][ 20 ][ 30 ][ 40 ] ← REAR

A queue supports only two main actions:

• ENQUEUE — means "to add to the back." Like a new person joining the line.
• DEQUEUE — means "to remove from the front." Like the first person getting their ticket and
leaving.

REMEMBER: EN-queue = EN-ter (join). DE-queue = DE-part (leave).

• PEEK — look at the front person, but don't remove them. Like checking "who's next" without
pushing them forward.
• IS_EMPTY — is the line empty? Cashier can rest.
• IS_FULL — is the counter full? Turn new people away.

Page 4
 Unit-III | Queue & Linked List

Writing a Simple Queue in Python

We will use a Python list as our row of boxes, and two markers — front and rear — to keep track of
where things are.

Step 1 — Set Up the Storage

SIZE = 5
queue = [None] * SIZE
front = -1
rear = -1

Line of code

SIZE = 5 Decide the maximum size of our queue. We choose 5 —

the queue can hold at most 5 items.

queue = [None] * SIZE Create a list of 5 empty boxes. 'None' means empty. So
queue = [None, None, None, None, None]. Our storage is
ready.

front = -1 Create a marker called front. We set it to -1 to mean

'queue is empty — no front yet.'

rear = -1 Same for rear. -1 means 'nothing at the back yet.'

WHY -1 AND NOT 0? Because 0 is a valid position in the list (it's the first slot). We need a special value
that means 'NO position yet.' -1 is not a valid list position, so we use it as our 'empty' signal.

Step 2 — The enqueue Function (Add to Back)

def enqueue(x):
global front, rear
if rear == SIZE - 1:
print("Queue Overflow")
return
if front == -1:
front = 0
rear = rear + 1
queue[rear] = x
print("Added", x)

Line of code

def enqueue(x): Define a function called enqueue. It takes one input — x

Page 5
 Unit-III | Queue & Linked List

Line of code

— the value the user wants to add.

global front, rear Tell Python: I am going to change the outer variables
front and rear. Without this, Python would create new
local copies.

if rear == SIZE - 1: Check: is rear pointing to the very last box? SIZE is 5, so
SIZE-1 is 4 (the last index). If yes, the queue is full.

print("Queue Overflow") Print an error message to say the queue is full.

return Exit the function immediately. Do not add anything.

if front == -1: Check: is the queue empty right now? We use front == -1
as our 'empty' signal.

front = 0 If it was empty, set front to 0 — the first item will go into
box 0, so front now points there.

rear = rear + 1 Move the rear marker one step to the right. Now it
points to the next empty box.

queue[rear] = x Put the value x into the box at position rear.

print("Added", x) Confirm to the user that x was added.

Run — Let's Watch It Work

Start: front = -1, rear = -1, queue = [None, None, None, None, None]
Call enqueue(10):
• Is rear == 4? No (rear is -1). Keep going.
• Is front == -1? Yes. Set front = 0.
• rear = rear + 1 → rear becomes 0.
• queue[0] = 10 → queue is now [10, None, None, None, None]
• State after: front=0, rear=0, queue=[10, None, None, None, None]
Call enqueue(20):
• Is rear == 4? No (rear is 0). Keep going.
• Is front == -1? No (front is 0). Skip.
• rear = 1. queue[1] = 20.
• State: front=0, rear=1, queue=[10, 20, None, None, None]
Continue for enqueue(30), (40), (50). Queue becomes [10,20,30,40,50], rear=4.
Call enqueue(60): Is rear == 4? YES. Print "Queue Overflow" and exit. The queue cannot take more.

Page 6
 Unit-III | Queue & Linked List

Step 3 — The dequeue Function (Remove from Front)

def dequeue():
global front, rear
if front == -1 or front > rear:
print("Queue is Empty")
return None
value = queue[front]
front = front + 1
return value

Line of code

def dequeue(): Define a function called dequeue. It takes no input.

global front, rear We will read and maybe change the outer front and
rear.

if front == -1 or front > rear: Check if queue is empty. Two cases: (1) front is -1 →
never had items. (2) front has moved past rear → all
items were removed.

print("Queue is Empty") Print error.

return None Return None to signal 'nothing removed'.

value = queue[front] Remember the value at the front. We will return this to
the user.

front = front + 1 Move the front marker one step to the right. The old
front slot is now considered 'removed'.

return value Give back the value to whoever called dequeue.

Run
Starting state: front=0, rear=4, queue=[10,20,30,40,50]
Call dequeue():
• Is queue empty? No — front=0, rear=4.
• value = queue[0] → value = 10.
• front = front + 1 → front = 1.
• Return 10. The user gets 10.
• State: front=1, rear=4, queue=[10,20,30,40,50] — notice 10 is STILL in the list physically, but
front has moved past it, so we treat it as gone.
NOTICE THIS PROBLEM: After a few dequeues, the front slots are 'wasted' — they still exist in the list
but we can never use them again. When rear hits 4, we say 'overflow' even though slots 0,1,2 may be
empty. This is called FALSE OVERFLOW. We will fix it with a Circular Queue.

Page 7
 Unit-III | Queue & Linked List

The Circular Queue (Fixing False Overflow)

In the simple queue, when rear reached the last position, we got stuck — even if the front positions
were empty. The trick of a circular queue is: when rear reaches the end, make it jump back to position 0
(if that slot is free). Treat the list as if it is bent into a circle, so index 0 comes right after the last index.
Imagine a ring road around Bengaluru. If you keep driving past the last exit, you come back to the first
exit. You never hit a dead end — you just keep going round. A circular queue works the same way.

The Percent Sign (%)

In Python, the % sign means REMAINDER. For example:
7 % 5 = 2 (7 divided by 5 leaves remainder 2)
5 % 5 = 0 (5 divided by 5 leaves remainder 0)
0 % 5 = 0
4 % 5 = 4
Watch what happens when we compute (rear + 1) % 5 for different values of rear:
• If rear = 0, (0+1) % 5 = 1
• If rear = 1, (1+1) % 5 = 2
• If rear = 2, (2+1) % 5 = 3
• If rear = 3, (3+1) % 5 = 4
• If rear = 4, (4+1) % 5 = 0 ← JUMPS BACK TO 0!
That's the magic. The modulo operator does the wrapping for us, automatically. One small formula
replaces a lot of if-else code.

Two Key Conditions

• QUEUE IS EMPTY: front is -1 (same as before — we never added anything).
• QUEUE IS FULL: (rear + 1) % SIZE == front. If the NEXT slot after rear is where front currently sits,
we have completely filled the circle.

The Code
SIZE = 5
cq = [None] * SIZE
front = -1
rear = -1

Page 8
 Unit-III | Queue & Linked List

def enqueue(x):
global front, rear
if (rear + 1) % SIZE == front:
print("Queue is Full")
return
if front == -1:
front = 0
rear = (rear + 1) % SIZE
cq[rear] = x
print("Added", x)

def dequeue():
global front, rear
if front == -1:
print("Queue is Empty")
return None
value = cq[front]
if front == rear:
front = -1
rear = -1
else:
front = (front + 1) % SIZE
return value

Line-by-Line for enqueue

Line of code

def enqueue(x): Start the enqueue function with input x.

global front, rear We will change the outer front and rear.

if (rear + 1) % SIZE == front: Check if queue is full. If the NEXT slot is where front sits,
the circle is full.

print("Queue is Full") Tell the user.

return Stop.

if front == -1: Was the queue empty?

front = 0 Yes — set front to 0 so the first item has a place.

rear = (rear + 1) % SIZE Move rear forward by 1, but wrap around if needed. This

Page 9
 Unit-III | Queue & Linked List

Line of code

is the heart of the circular queue.

cq[rear] = x Put x in the new rear position.

print("Added", x) Confirm.

Line-by-Line for dequeue

Line of code

def dequeue(): Start the dequeue function.

global front, rear We will change them both.

if front == -1: Is the queue empty?

print("Queue is Empty") Tell the user.

return None Return None — nothing to give.

value = cq[front] Remember the front value.

if front == rear: Special case: only ONE item left. After removing it, the
queue will be empty.

front = -1 Reset front to -1 (empty signal).

rear = -1 Reset rear to -1 too.

else: Otherwise, normal case.

front = (front + 1) % SIZE Move front forward by 1, wrapping if needed.

return value Give the value back to the caller.

Run
SIZE=5, starting empty. front=-1, rear=-1.
• enqueue(10), (20), (30), (40), (50) → front=0, rear=4, cq=[10,20,30,40,50]
• dequeue() → returns 10. front moves from 0 to 1. cq=[10,20,30,40,50] (slot 0 ignored).
• dequeue() → returns 20. front moves to 2.
• enqueue(60) → rear was 4. (4+1)%5 = 0. Rear becomes 0. cq[0] = 60. Now cq=[60,20,30,40,50].
We reused slot 0!
• enqueue(70) → (0+1)%5 = 1. rear=1. cq=[60,70,30,40,50].
• enqueue(80) → check (1+1)%5 == front (2==2) → YES, queue is FULL. Rejected.
NO MORE FALSE OVERFLOW: We filled exactly 5 slots and then said full — which is correct. No
memory is wasted anymore.

Page 10
 Unit-III | Queue & Linked List

Page 11
 Unit-III | Queue & Linked List

Deque (Double-Ended Queue)

What Makes It Different

A normal queue is strict — add only at rear, remove only at front. A DEQUE (pronounced 'deck') is more
flexible: you can add AND remove from BOTH ends. Four actions instead of two.
Think of a web browser. Every page you visit goes into a history. When the history gets too long, the
oldest page falls off the OTHER end. New items go in one door, old items fall out the other. That's a
deque.

Four Actions
• insert_front(x) — add x at the front end.
• insert_rear(x) — add x at the back end.
• delete_front() — remove from the front end.
• delete_rear() — remove from the back end.

The Code
dq = []
def insert_front(x):
[Link](0, x)
print("Inserted", x, "at front")
def insert_rear(x):
[Link](x)
print("Inserted", x, "at rear")
def delete_front():
if len(dq) == 0:
print("Deque is empty")
return None
return [Link](0)
def delete_rear():
if len(dq) == 0:
print("Deque is empty")
return None
return [Link]()
def display():
print("Deque:", dq)

Page 12
 Unit-III | Queue & Linked List

Line-by-Line
Line of code

dq = [] Create an empty list called dq. This is our deque storage.

def insert_front(x): Define function to add at front.

[Link](0, x) Python's insert(0, x) means: put x at position 0, shifting

everyone else to the right.

def insert_rear(x): Define function to add at rear.

[Link](x) Python's append(x) adds x at the very end.

def delete_front(): Define function to remove from front.

if len(dq) == 0: len(dq) gives the number of items. If it's 0, deque is

empty.

return None Nothing to remove.

return [Link](0) pop(0) removes AND returns the item at position 0. The
user gets it.

def delete_rear(): Define function to remove from rear.

return [Link]() pop() with no number means pop from the end. Returns
and removes the last item.

Run
insert_rear(10) # dq = [10]
insert_rear(20) # dq = [10, 20]
insert_front(5) # dq = [5, 10, 20]
insert_front(1) # dq = [1, 5, 10, 20]
print(delete_rear()) # prints 20, dq = [1, 5, 10]
print(delete_front())# prints 1, dq = [5, 10]

Two Special Types

• INPUT-RESTRICTED DEQUE — you can add only at rear, but remove from either end.
• OUTPUT-RESTRICTED DEQUE — you can add at either end, but remove only from front.
These are used when we want a bit of extra flexibility, but not full freedom on both ends.

Page 13
 Unit-III | Queue & Linked List

Priority Queue

Not a Fair Queue

A normal queue is fair — first come, first served. A PRIORITY QUEUE is not fair. Each item has a priority
number attached to it. The item with the most urgent priority gets served first, even if it joined last.
In a hospital emergency room, suppose a man with a broken arm comes at 9 AM. At 9:15, a woman
with a heart attack comes in. Who does the doctor see first? The heart attack patient. Even though she
came LATER, her priority is higher. This rule is called TRIAGE — and it is exactly a priority queue.

In our code we use: smaller number = higher priority. So priority 1 beats priority 2, priority 2 beats
priority 3. You could do it the other way — just be consistent.

The Code
We will store each item as a pair: (priority, value). A pair in Python is called a tuple — written in round
brackets.
pq = []
def enqueue(value, priority):
[Link]((priority, value))
print("Added", value, "with priority", priority)
def dequeue():
if len(pq) == 0:
print("Priority queue is empty")
return None # find the index with the smallest priority
min_index = 0
for i in range(1, len(pq)):
if pq[i][0] < pq[min_index][0]:
min_index = i
item = [Link](min_index)
return item[1] # return just the value
def display():
print("Priority queue:", pq)

Line-by-Line for dequeue

Line of code

pq = [] Our priority queue storage — starts empty.

Page 14
 Unit-III | Queue & Linked List

Line of code

def enqueue(value, priority): Two inputs now: the value and its priority number.

[Link]((priority, value)) Add the pair (priority, value) at the end. The round
brackets make it a tuple.

def dequeue(): Remove the item with the highest priority.

if len(pq) == 0: If empty, say so.

min_index = 0 Start by assuming the first item has the best priority.

for i in range(1, len(pq)): Loop through every other item, starting from index 1.

if pq[i][0] < pq[min_index][0]: pq[i][0] is the priority of item i. If this item's priority is
smaller (better) than our current best, update.

min_index = i Remember which index has the smallest priority.

item = [Link](min_index) Remove that item. pop(min_index) gives us (priority,

value) and removes it from the list.

return item[1] Return just the value — item[1] is the second part of the
pair.

Run
enqueue("BrokenArm", 3)
enqueue("HeartAttack", 1)
enqueue("HighFever", 2)
print(dequeue()) # prints HeartAttack (priority 1 = highest)
print(dequeue()) # prints HighFever (priority 2)
print(dequeue()) # prints BrokenArm (priority 3 = lowest)
Notice: HeartAttack came in the MIDDLE but got served FIRST because its priority was the smallest
number. The order of insertion did not matter.

Where This Is Used

• Hospital emergency rooms (literal triage).
• Google Maps — finding the shortest route uses a priority queue internally.
• CPU scheduling — high-priority tasks run first.
• Airports — VIP / first class passengers board first.

Page 15
 Unit-III | Queue & Linked List

Where Queues Are Used in Real Life

6.1 Printing Documents

When you press Ctrl+P on Windows, your document does not print instantly. It goes into a PRINT
QUEUE. If you press Ctrl+P three times for three files, they print in the order you asked — first file first.
This queue is managed by software called the Print Spooler. Linux uses a similar system called CUPS.
Both are queues.

6.2 Call Centers

When you call Airtel or Jio customer care, you sometimes hear: 'You are number 7 in the queue.' That 7
is literally your position in a queue data structure on their server. As each caller ahead finishes, everyone
moves up by one. When you reach position 1, an agent picks up your call.

6.3 The Keyboard Buffer

Type a sentence on your keyboard very fast. Even if the CPU is busy for a split second, your characters
don't get lost. They sit in a KEYBOARD BUFFER — which is a queue. When the CPU is free, it reads the
characters out in the same order you typed them. That is why even on a laggy computer, your typing
shows up correctly once the lag clears.

6.4 YouTube and Netflix Buffering

When you play a video, little pieces of the video are downloaded in advance and stored in a buffer. The
video player reads pieces from this buffer in order. The buffer is a queue — first piece in, first piece
played.

6.5 WhatsApp Message Delivery

If you are offline and you type a message, WhatsApp stores it locally. When you come back online, the
messages you typed while offline get sent out — in the order you typed them. A queue handles this.

6.6 Traffic Signals

At a red signal, vehicles line up. When green comes, they leave in the order they arrived. A real-world
queue.

6.7 Order Processing — Amazon, Flipkart, Swiggy

When you place an order on Amazon, your order joins a queue at the warehouse. Orders are processed
roughly in the order they come in. A queue ensures fairness.

Page 16
 Unit-III | Queue & Linked List

PART B — LINKED LISTS

The Problem With Lists
Imagine you run a library with 100,000 books stored in a Python list in alphabetical order. A new book
comes in starting with the letter 'A'. You need to add it at position 0. What has to happen? Every other
book must shift one slot to the right. 100,000 shifts for ONE insertion!
Similarly, deleting the first book would require 99,999 shifts. Python lists are great for many things, but
they are SLOW when we add or remove items at the beginning or middle.

The Idea: Don't Store Them Together

What if we gave up the idea of keeping items side-by-side in memory? What if each item just held a
POINTER to the next item, wherever it happens to be in memory? Then to insert a new item, we
wouldn't shift anything — we'd just change a couple of pointers. That idea is called a LINKED LIST.

What Is a Linked List?

A linked list is a chain of items, where each item has two parts:
1. The DATA — the actual value we care about (e.g., 10, or 'Ram', or '[Link]').
2. A POINTER — a reference to the next item in the chain. The last item's pointer is None
(meaning: nothing after me).

[ 10 | → ] → [ 20 | → ] → [ 30 | → ] → [ 40 | None ]
Each box has two halves: the data (left) and the pointer to the next box (right). The last box points to
None.
A linked list is like a TREASURE HUNT. You are given the first clue. It tells you where the second clue is.
The second clue tells you where the third clue is. Each clue leads to the next. The last clue says STOP.
You cannot jump to clue 5 directly — you have to follow the chain from clue 1.

Real-World Analogy: A Train

A train is a perfect linked list. Each coach is a node. Each coach has a coupling (a physical link) to the next
coach. The last coach has no coupling behind it. You can:
• Add a coach at the front (uncouple engine, attach new coach to engine, attach new coach to old
first coach).
• Add a coach at the back (go to the last coach, attach new coach to it).
• Insert a coach in the middle (uncouple A from B, attach A to new coach, attach new coach to B).
All of these happen by CHANGING A FEW COUPLINGS. You never have to shift the whole train.

Page 17
 Unit-III | Queue & Linked List

How to Store a Node in Python

We will use a DICTIONARY to represent each node. A dictionary can hold two fields — we will call them
'data' and 'next'.
node = {'data': 10, 'next': None}

Line of code

node The name of our node — think of it as an ID card.

'data': 10 The first field, called 'data', holds the value 10.

'next': None The second field, called 'next', is supposed to hold the
next node. We set it to None for now — it points to
nothing yet.

To link two nodes together:

node1 = {'data': 10, 'next': None}
node2 = {'data': 20, 'next': None}
node1['next'] = node2 # link node1 to node2
Now node1's 'next' field holds node2. If you do node1['next']['data'] you get 20 — the data of the next
node.

The All-Important head Variable

To access the linked list, we only need one thing — the address of the FIRST node. We store it in a
variable called head. From head we can reach every other node by following the chain.
WARNING: If you lose the head variable, you lose the entire list. It's gone from memory, forever.
Always protect head. Never overwrite it without thinking.

Page 18
 Unit-III | Queue & Linked List

Building a Singly Linked List, Step by Step

A Singly Linked List (SLL) is the simplest linked list. Each node has only ONE pointer — to the next node.
You can only travel forward.

Step 1 — Set Up
head = None

Line of code

head = None Create the head variable and set it to None. This means:
the list is empty — there is no first node yet.

Step 2 — Helper to Create a Node

def create_node(x):
return {'data': x, 'next': None}

Line of code

def create_node(x): Define a small helper function that takes a value x.

return {'data': x, 'next': None} Build and return a dictionary with two fields: data=x and
next=None. That's our new node, ready to be linked.

Step 3 — Insert at Beginning

def insert_at_beginning(x):
global head
new_node = create_node(x)
new_node['next'] = head
head = new_node

Line of code

def insert_at_beginning(x): Define the function with input x — the value to add.

global head We will change the outer head variable.

new_node = create_node(x) Build a new node holding x. Its 'next' is currently None.

new_node['next'] = head Make the new node point to whatever head currently
points to. If head was None, new_node['next'] becomes
None — fine, new_node will be the only item. If head

Page 19
 Unit-III | Queue & Linked List

Line of code

pointed to the old first node, new_node now points

there.

head = new_node Move head so it now points to the new node. The new
node is the first node.

Run
Before inserting: head → None (empty list)
Call insert_at_beginning(10):
• new_node = {'data': 10, 'next': None}
• new_node['next'] = head → new_node['next'] = None (head was None)
• head = new_node
• Now: head → [10 | None]
Call insert_at_beginning(20):
• new_node = {'data': 20, 'next': None}
• new_node['next'] = head → new_node's next now points to the node holding 10.
• head = new_node → head now points to the 20 node.
• Now: head → [20 | →] → [10 | None]
COMMON MISTAKE: Students often do head = new_node FIRST, then try new_node['next'] = head.
But now head already points to new_node, so new_node['next'] points to new_node itself — an
infinite loop! Always point the new node forward FIRST, then move head.

Step 4 — Insert at End

def insert_at_end(x):
global head
new_node = create_node(x)
if head is None:
head = new_node
return
t = head
while t['next'] is not None:
t = t['next']
t['next'] = new_node

Line of code

def insert_at_end(x): Add x at the end of the list.

global head We may need to change head (only if the list is empty).

Page 20
 Unit-III | Queue & Linked List

Line of code

new_node = create_node(x) Build the new node.

if head is None: Is the list empty?

head = new_node Yes — the new node is the first AND last. head points to
it.

return Done.

t = head Otherwise, we need to walk to the last node. Start from

head. t is a 'walker' pointer.

while t['next'] is not None: Keep walking as long as there is a next node.

t = t['next'] Move t forward one node.

t['next'] = new_node When the loop exits, t is at the LAST node. Set its next to
the new node. Done.

Run
Starting list: head → [10|→] → [20|None]
Call insert_at_end(30):
• new_node = {data:30, next:None}
• Is head None? No.
• t = head → t points to [10|→]
• Check t['next'] is not None? [10]'s next is [20] — not None. Enter loop.
• t = t['next'] → t now points to [20|None]
• Check t['next'] is not None? [20]'s next is None. Exit loop.
• t['next'] = new_node → [20]'s next now points to the new [30] node.
• Final: head → [10|→] → [20|→] → [30|None]

Page 21
 Unit-III | Queue & Linked List

Insert at a Position + Delete Operations

Insert at a Specific Position

For example, in the list [10, 20, 30, 40], if we insert 99 at position 2, the list becomes [10, 20, 99, 30, 40].
Position 2 means 'at index 2', i.e., the third slot.
def insert_at_position(x, pos):
global head
if pos == 0:
insert_at_beginning(x)
return
new_node = create_node(x)
t = head
for i in range(pos - 1):
if t is None:
print("Position out of range")
return
t = t['next']
if t is None:
print("Position out of range")
return
new_node['next'] = t['next']
t['next'] = new_node

Line of code

def insert_at_position(x, pos): Add x at position pos.

if pos == 0: Special case: position 0 means beginning.

insert_at_beginning(x) Use the function we already wrote.

return Done.

new_node = create_node(x) Build the new node.

t = head Start a walker at head.

for i in range(pos - 1): Walk pos-1 steps. We want to stop at the node JUST
BEFORE position pos.

if t is None: If we fell off the end before reaching position pos, bad
input.

return Exit.

t = t['next'] Move one step.

Page 22
 Unit-III | Queue & Linked List

Line of code

new_node['next'] = t['next'] TRAIN COUPLING TRICK step 1 — connect the new

node's next to whatever was after t.

t['next'] = new_node TRAIN COUPLING TRICK step 2 — connect t to the new

node. Now the new node sits between t and the old
next.

WHY THIS ORDER MATTERS: Imagine A → B and you want to insert N between them. If you FIRST set
A→N, then try to set N→B, you have already lost the original link from A to B! Always save the
forward link FIRST (new_node['next'] = t['next']), THEN change t ('s next.

Delete From Beginning

def delete_from_beginning():
global head
if head is None:
print("List is empty")
return
print("Deleted", head['data'])
head = head['next']

Line of code

def delete_from_beginning(): Remove the first node.

global head We are changing head.

if head is None: If the list is empty, nothing to delete.

print("Deleted", head['data']) Show what we are removing.

head = head['next'] Move head to the second node. The old first node has
no more references — Python will automatically clean it
up from memory.

Delete From End

def delete_from_end():
global head
if head is None:
return
if head['next'] is None:
head = None
return

Page 23
 Unit-III | Queue & Linked List

t = head
while t['next']['next'] is not None:
t = t['next']
t['next'] = None

Line of code

def delete_from_end(): Remove the last node.

if head is None: Empty list — nothing to delete.

if head['next'] is None: Only ONE node in the list? Then deleting from end
means the list becomes empty.

head = None Set head to None. List is empty.

t = head Otherwise, walk until we find the second-last node.

while t['next']['next'] is not None: Keep walking as long as there are TWO more nodes
ahead. When this is False, t is second-last.

t = t['next'] Move forward.

t['next'] = None Cut off the last node by setting the second-last's next to
None. The last node is now unreachable — Python
cleans it up.

Delete a Given Value

def delete_value(x):
global head
if head is None:
return
if head['data'] == x:
head = head['next']
return
t = head
while t['next'] is not None and t['next']['data'] != x:
t = t['next']
if t['next'] is None:
print("Value", x, "not found")
return
t['next'] = t['next']['next']

Line of code

def delete_value(x): Remove the first node whose data is x.

Page 24
 Unit-III | Queue & Linked List

Line of code

if head['data'] == x: If the head node has the value, just move head forward.

head = head['next'] Head now skips the old head.

t = head Walker starts at head.

while t['next'] is not None and Keep walking until either we fall off the end OR we find a
t['next']['data'] != x: node whose NEXT has the value x.

t = t['next'] Step forward.

if t['next'] is None: We fell off the end — value was not in the list.

t['next'] = t['next']['next'] 'Skip over' the matching node by pointing t directly to

the node after the match. The match becomes
unreachable.

Display the Whole List

def display():
t = head
while t is not None:
print(t['data'], end=" → ")
t = t['next']
print("None")

Line of code

def display(): Print all nodes in order.

t = head Start at head.

while t is not None: As long as there is a node.

print(t['data'], end=" → ") Print its data, followed by an arrow. end=' → ' tells print
NOT to go to a new line.

t = t['next'] Move to next.

print("None") After all nodes, print None to show the list ends.

Page 25
 Unit-III | Queue & Linked List

Doubly Linked List (DLL)

The Problem With a Singly Linked List

In an SLL, if you are at node 5 and want to go back to node 4, you cannot. You have no link backwards.
You'd have to start over from head. This is slow.

The Fix — Add a Second Pointer

A Doubly Linked List gives each node TWO pointers:
• 'next' — points to the node ahead.
• 'prev' — points to the node behind.
Now you can walk forward AND backward with equal ease.
Think of a music playlist in Spotify. When you press NEXT, you go to the next song. When you press
PREVIOUS, you go back. Each song in the playlist knows what comes before AND what comes after.
That's a doubly linked list. Same for browser history (back / forward), Ctrl+Z / Ctrl+Y, and photo
galleries.

Node Structure
# A doubly-linked-list node has three fields
def create_dnode(x):
return {'data': x, 'prev': None, 'next': None}

Visual
None ← [prev | 10 | next] ⇄ [prev | 20 | next] ⇄ [prev | 30 | next] → None
The arrows go both ways. The first node's 'prev' is None (nothing before it). The last node's 'next' is
None (nothing after it).

Insert at the Beginning

head = None
def insert_at_beginning(x):
global head
new_node = create_dnode(x)
new_node['next'] = head
if head is not None:
head['prev'] = new_node
head = new_node

Line of code

def insert_at_beginning(x): Add x at the start.

new_node = create_dnode(x) Build a new node. prev=None, next=None.

Page 26
 Unit-III | Queue & Linked List

Line of code

new_node['next'] = head New node points forward to the current first node.

if head is not None: If the list already had nodes, the old first node's prev
must now point BACK to the new node.

head['prev'] = new_node Set it.

head = new_node Move head to the new node.

Insert at the End

def insert_at_end(x):
global head
new_node = create_dnode(x)
if head is None:
head = new_node
return
t = head
while t['next'] is not None:
t = t['next']
t['next'] = new_node
new_node['prev'] = t

Line of code

def insert_at_end(x): Add x at the end.

if head is None: Empty list.

head = new_node New node is the only node.

t = head Walk to the last node.

while t['next'] is not None: Keep walking as long as there's a next.

t['next'] = new_node Connect last node's next to new node.

new_node['prev'] = t Connect new node's prev BACK to the old last node.
Both directions now linked.

Delete a Specific Node

In a DLL, given a reference to ANY node, we can delete it in O(1) — no need to walk from head. This is a
huge advantage over SLL.
def delete_node(target):
global head
if target is None:
return

Page 27
 Unit-III | Queue & Linked List

if target['prev'] is not None:

target['prev']['next'] = target['next']
else:
head = target['next']
if target['next'] is not None:
target['next']['prev'] = target['prev']

Line of code

def delete_node(target): Remove the given node from the list.

if target['prev'] is not None: Is there a node before target?

target['prev']['next'] = Yes — make the previous node's next skip over target.
target['next']

else: No node before target — target is the head.

head = target['next'] Move head to whatever comes after target.

if target['next'] is not None: Is there a node after target?

target['next']['prev'] = Yes — make the next node's prev skip over target
target['prev'] backward.

Display Forward and Backward

def display_forward():
t = head
while t is not None:
print(t['data'], end=" ⇄ ")
t = t['next']
print("None")
def display_backward():
if head is None:
return
t = head
while t['next'] is not None:
t = t['next']
while t is not None:
print(t['data'], end=" ⇄ ")
t = t['prev']
print("None")

Line of code

def display_backward(): Print from last to first.

while t['next'] is not None: First, walk to the very last node.

Page 28
 Unit-III | Queue & Linked List

Line of code

t = t['next'] Step forward.

while t is not None: Now walk BACK using the prev pointers.

t = t['prev'] Step backward.

Page 29
 Unit-III | Queue & Linked List

Circular Linked List (CLL)

In a regular linked list, the last node's next is None — the chain ends. In a CIRCULAR linked list, the last
node's next points BACK to the first node (head). The chain loops forever.

Visual
┌────────────────────────────────────────┐ ↓
│ [ 10 | → ] → [ 20 | → ] → [ 30 | → ] → [ 40 | ↑ ]
The last node's arrow swings back to the first. There is no end.
Remember the round-robin CPU scheduler? Processes A, B, C, D each get a time slice, and after D, the
scheduler comes back to A again. It never 'ends' as long as there are processes. That is exactly a
circular linked list. Another example — Ludo or any turn-based game. Player 1, 2, 3, 4, back to 1, 2, 3,
4... turns cycle forever.

Insert at the End

head = None
def insert_at_end(x):
global head
new_node = {'data': x, 'next': None}
if head is None:
head = new_node
new_node['next'] = head
return
t = head
while t['next'] != head:
t = t['next']
t['next'] = new_node
new_node['next'] = head

Line of code

if head is None: Empty list.

head = new_node New node is the only node.

new_node['next'] = head In a circular list, a single node points to ITSELF. Weird

but correct — the circle has just one member.

t = head Walk to the last node.

while t['next'] != head: In a normal list we check for None. Here we check 'have I
come back to head?' — that means I'm at the last node.

t = t['next'] Keep walking.

Page 30
 Unit-III | Queue & Linked List

Line of code

t['next'] = new_node The old last's next now points to the new node.

new_node['next'] = head New node's next points back to head — closing the
circle.

Display
def display():
if head is None:
print("List is empty")
return
t = head
while True:
print(t['data'], end=" → ")
t = t['next']
if t == head:
break
print("(back to head)")

Line of code What it means in simple English

while True: Start an infinite loop — we'll break out manually when
we come back to head.

print(t['data'], end=" → ") Print the current node.

t = t['next'] Move forward.

if t == head: Have we come back to where we started?

break Yes — exit the loop.

INFINITE LOOP WARNING: A student might write 'while t is not None' for a circular list. But t will
NEVER be None! The program runs forever and the terminal freezes. ALWAYS stop when you come
back to head.

Where It's Used

• Round-robin CPU scheduling — operating systems.
• Multiplayer games — turns rotate forever.
• Music player on repeat-all mode.
• Alt+Tab on Windows — keeps cycling through open apps.

Page 31
 Unit-III | Queue & Linked List

Comparing Everything

Python List vs Linked List

Feature Python List Linked List

Memory All items side-by-side Items scattered, connected by

pointers

Access item at index i Very fast — direct access Slow — must walk from head

Insert at beginning Slow — all items shift right Very fast — change one pointer

Insert at end Fast (append) Slow — must walk to the last node

Delete at beginning Slow Very fast

Size Auto-grows Grows one node at a time

Best used for Random reading, known size Lots of insert / delete at start or
middle

Singly vs Doubly vs Circular

Feature Singly Doubly Circular

Pointers per node 1 (next) 2 (prev, next) 1 or 2

Direction Forward only Both ways Cycles

Last node's next None None Points to head

Memory per node Low High Low to medium

Best for Simple lists, queues, Playlists, browser Round-robin, turns

stacks history, undo

Page 32
 Unit-III | Queue & Linked List

Practice Questions

Short Answer (2 marks each)

1. Define FIFO with one example.
2. Differentiate a stack and a queue in two lines.
3. What is the condition for a circular queue to be full?
4. Give one advantage of a linked list over a Python list.
5. What is stored in the 'head' variable of a linked list?
6. What is a priority queue? Give one real example.

Medium Answer (5 marks each)

1. Explain the false overflow problem of a simple queue. How does a circular queue solve it?
Give a dry-run example.
2. Write a Python function to insert a node at the beginning of a singly linked list. Explain each
line.
3. Differentiate Python lists and linked lists in terms of memory, access, and insertion/deletion.
4. Describe any three real-world uses of queues and explain why a queue is the right choice.
5. Write Python code to reverse the display of a doubly linked list (from last to first).

Long Answer (10 marks each)

1. Build a queue using a linked list in Python with enqueue, dequeue, peek, and display.
Explain each function.
2. Write and explain Python code for a circular singly linked list supporting insert at end and
display.
3. Compare singly, doubly, and circular linked lists in terms of structure, memory, use cases,
and one real-world application each.

Page 33