1.

Linear Data Structures

Stack and Queue

Understanding Stacks: LIFO operations, Applications.

Understanding Queues: FIFO operations, types of queue.

Implementation using Arrays and Linked Lists

Practical Problems.
 A stack is a data structure that follows the Last In, First Out (LIFO) principle. This means that the
last element added to the stack will be the first one to be removed. Think of it like a stack of
plates: the last plate you put on the top is the first one you take off when needed.

 Basic Operations in a Stack:

 1. Push: Adding an item to the stack.
 2. Pop: Removing the top item from the stack.
 3. Peek (or Top): Viewing the top item without removing it.
 4. isEmpty: Checking if the stack is empty.
 5. Size: Checking how many elements are in the stack.

 Types of Stacks:

 1. Array-based Stack:
 - Uses a fixed-size array to store elements.
 - It has a simple structure but is limited by the fixed size of the array.
 - Operations like push, pop, and peek are performed in constant time O(1), but resizing an
array when it’s full can be costly.
 Example:
 Let’s consider a stack and demonstrate the LIFO operations:
 Initial Stack:

 1. Push Operations:
 Push(10):
 Stack after operation: [10]
 Push(20):
 Stack after operation: [10, 20]
 Push(30):
 Stack after operation: [10, 20, 30]
 2. Pop Operation:
 Pop() (removes 30, as it’s the last item added):
 Stack after operation: [10, 20]
 Pop() (removes 20):Stack after operation: [10]
 Pop() (removes 10):Stack after operation: (Stack is now empty)

 3. Peek Operation:
 After pushing an element, you can Peek to check the top element.
 Push(40):Stack after operation: [40]
 Peek():
 Returns 40, as it's the top element without removing it.

 4. IsEmpty:
 After popping all elements:
 IsEmpty() will return True when the stack is empty.
 2. Linked List-based Stack:
 - Uses a linked list where each element points to the next one.
 - This allows dynamic resizing (no fixed size), as it can grow or shrink based on the
number of elements.
 - Operations like push, pop, and peek are still \(O(1)\), and there’s no need for resizing
like in array-based stacks.

 3. Two-Stack Implementation in One Array:

 - In this type, two stacks are implemented using the same array. One stack is built from
the left side, and the other from the right side.
 - This is an optimization technique to efficiently use the array's memory by utilizing both
ends.
 4. Multi-Stack (Stack of Stacks):
 - In this type, multiple stacks are managed within a single data structure. This can be
useful in certain applications, like managing multiple tasks or undo operations.
 - Each stack can grow independently, but they're all part of a larger collection.

 Real-life Examples of Stacks:

 - Browser History: The pages you visit are pushed onto the stack. You press "back," and
the last visited page (top of the stack) is popped.
 - Undo/Redo functionality in software: Each action is pushed onto the stack, and when
you press undo, the most recent action is popped off.
Example: Undo Feature with Stack

 Undo works by reversing the last action.

 We store each user action (e.g., typing, deleting, formatting) on a stack.
 When the user clicks Undo, we pop the last action off the stack and reverse it.

 🧰 Tools Used:

 Stack (LIFO): Last action performed is the first to be undone.

 Python list is used to implement the stack.

 🧰 Step-by-Step Example:

 Scenario: A user types characters into a document.

 Action sequence:
 Type 'H', Type 'e', Type 'l', Type 'l', Type 'o'
 Then the user hits Undo 2 times.

 1. Initialize the stack:

undo_stack = [] This will hold the actions
 text = "" Simulated text area

 2. Perform typing actions:

 def type_char(c):
 global text
 text += c
 undo_stack.append(('type', c)) Push the action to the stack
 print(f"Typed: {c}, Current text: '{text}'")
 Typing the characters:

 type_char('H') Text: H
 type_char('e') Text: He
 type_char('l') Text: Hel
 type_char('l') Text: Hell
 type_char('o') Text: Hello
 📝 Stack contents now (top at right):

 [('type', 'H'), ('type', 'e'), ('type', 'l'), ('type', 'l'), ('type', 'o')]

 3. Undo action:

 def undo():
 global text
 if undo_stack:
 action, value = undo_stack.pop() Get the last action
 if action == 'type':
 text = text[:-1] Remove last character
 print(f"Undo: Removed '{value}', Current text: '{text}'")
 else:
 print("Nothing to undo.")
 Now call `undo()` two times:

 undo() Removes 'o' → "Hell"

 undo() Removes 'l' → "Hel"

 Final Output:

 Final text: `'Hel'`

 Undo Stack:

 [('type', 'H'), ('type', 'e'), ('type', 'l')]

 🔁 Full Working Code:

 ```python
 undo_stack = []
 text = ""
 def type_char(c):
 global text
 text += c
 undo_stack.append(('type', c))
 print(f"Typed: {c}, Current text: '{text}'")

 def undo():
 global text
 if undo_stack:
 action, value = undo_stack.pop()
 if action == 'type':
 text = text[:-1]
 print(f"Undo: Removed '{value}', Current text: '{text}'")
 else:
 print("Nothing to undo.")
 Simulating typing
 type_char('H')
 type_char('e')
 type_char('l')
 type_char('l')
 type_char('o')

 Undo actions
 undo()
 undo()
Use Case: Web Browser Back Button (with Stack)
 🧠 Key Concept:
 Every time a user navigates to a new page, it's pushed onto a stack.
 When the user presses Back, the browser pops the last visited page from the stack and
goes back to the previous page.
 🔁 Stack Behavior: LIFO (Last In, First Out)

 Step-by-Step Explanation
 Let’s simulate browsing the following pages:
 Home → About → Services → Contact
 1 2 3 4
 Step 1: Initialize
 back_stack = [] Stores history of visited pages
 current_page = None
 Step 2: Visiting Pages
 Each time we visit a new page:
 The current page is pushed to the back stack.
 The new page becomes the current page.

 def visit_page(url):
 global current_page
 if current_page:
 back_stack.append(current_page)
 current_page = url
 print(f"Visited: {current_page}")
 Example browsing:
 visit_page("Home")
 visit_page("About")
 visit_page("Services")
 visit_page("Contact")

 Back Stack after all visits:

['Home', 'About', 'Services']
Current Page: 'Contact‘

 Step 3: Going Back

 When the user presses the Back button:
 The last page in the stack is popped.
 That page becomes the current page.
 def go_back():
 global current_page
 if back_stack:
 current_page = back_stack.pop()
 print(f"Went back to: {current_page}")
 else:
 print("No history to go back to.")

 Example usage:
 go_back() Back to 'Services'
 go_back() Back to 'About'
 go_back() Back to 'Home'
 go_back() Stack is empty
 Final Output:

 Visited: Home
 Visited: About
 Visited: Services
 Visited: Contact
 Went back to: Services
 Went back to: About
 Went back to: Home
 No history to go back to.
Action Stack (Top → Bottom) Current Page
Visit Home [] Home

Visit About ['Home'] About

Visit Services ['Home', 'About'] Services

Visit Contact ['Home', 'About', 'Services'] Contact

Go Back (1) ['Home', 'About'] Services

Go Back (2) ['Home'] About

Go Back (3) [] Home

Go Back (4) (empty) No history

Queue
 Queue:-
 A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means
that the first element added to the queue will be the first one to be removed. Imagine a line at
a ticket counter: the person who gets in line first is the first one to be served.
 Types of Queues:
 There are several types of queues based on their behavior or how elements are handled. Some
of the common types include:
 1. Simple Queue (Linear Queue)
 Description: A simple queue is the most basic form of a queue. It works on the FIFO principle,
where elements are added to the rear and removed from the front.
 Drawback: In a simple queue, once the front of the queue has been dequeued, the space is
wasted until the queue is completely empty. This leads to inefficient use of memory if the queue
is implemented using an array.
 Operations:
 Enqueue (add to the rear)
 Dequeue (remove from the front)
 Example:
 Front -> [10] [20] [30] -> Rear
 Enqueue 40: [10] [20] [30] [40]
 Dequeue: [20] [30] [40]
 2. Circular Queue
 Description: A circular queue addresses the inefficiency problem of a simple queue. In a
circular queue, the rear end can wrap around to the front of the queue once the rear
reaches the end of the array. This means that the space freed by a dequeue operation
can be reused for new elements.
 Advantages: Circular queues ensure efficient memory utilization.
 Operations:
 Enqueue (add to the rear, wrapping around)
 Dequeue (remove from the front)
 Example:
 Front -> [10] [20] [30] -> Rear
 After dequeue, the front moves to 20.
 Enqueue 40: [20] [30] [40] [10] (Rear wraps to front)
 1. Customer Support Call Queue

 A company has 5 support agents.

 Calls come in one by one and go to the next available agent.
 If Agent 5 just got a call, the next one goes back to Agent 1 (if free).
 It cycles through agents — just like a circular queue.


 2. Queue of Printers in an Office

 5 printers are set to take turns printing documents.

 If Printer 5 just printed, the next job goes to Printer 1 (if idle).
 It rotates the jobs in a loop — just like a circular queue.
 Customer Support Call Queue

 A company has a customer support line.

 When customers call, they are placed in a queue (a line).
 The first caller gets helped first — that’s FIFO (First In, First Out).

 Step-by-Step Using a Queue (Size = 5)

 Let’s say the queue can hold 5 customers at a time.

 Initial Queue:

 Queue: [ _, _, _, _, _ ]
 front = -1, rear = -1 (empty)
 Step 1: Customer A calls (Enqueue A)
 Queue: [ A, _, _, _, _ ]
 front = 0, rear = 0

 Step 2: Customer B calls (Enqueue B)

 Queue: [ A, B, _, _, _ ]
 front = 0, rear = 1

 Step 3: Customer C calls (Enqueue C)

 Queue: [ A, B, C, _, _ ]
 front = 0, rear = 2
 Step 4: Agent is free → Serve Customer A (Dequeue A)
 Queue: [ _, B, C, _, _ ]
 front = 1, rear = 2

 Step 5: Customer D calls (Enqueue D)

 Queue: [ _, B, C, D, _ ]
 front = 1, rear = 3

 Step 6: Customer E calls (Enqueue E)

 Queue: [ _, B, C, D, E ]
 front = 1, rear = 4
 Step 7: Agent is free → Serve Customer B (Dequeue B)
 Queue: [ _, _, C, D, E ]
 front = 2, rear = 4

 Step 8: Customer F calls

 Now we have space at the start (index 0), so we can use a circular queue to wrap around.

 Next position: = 0

 Queue: [ F, _, C, D, E ]
 front = 2, rear = 0
 Why This Is Useful in Customer Support:
 Calls come in order and get handled in order.
 If someone finishes their call (dequeue), the next person steps up.
 With circular behavior, you can reuse space and never miss a call (until the queue is
truly full).
 2. Queue of Printers in an Office
 Real-Life Scenario:

 An office has 5 printers: P1, P2, P3, P4, and P5.

 Print jobs come in and are sent to the printers one by one, in a circular order.
 When the last printer (P5) gets a job, the next one goes back to P1 — forming a circular queue.
 🧰 Circular Queue Behavior:

 Enqueue: A new print job is added to the next available printer.

 Dequeue: A print job finishes printing, and the printer becomes available again.

 🧰 Step-by-Step Example (Circular Queue of Printers)

 We’ll assume:

 Each printer takes 1 job at a time.

 Queue size = 5 (since there are 5 printers).
 Jobs are named J1, J2, J3...
 Step 1: Job J1 comes in → Assigned to P1

 Queue: [ J1, _, _, _, _ ]
 front = 0, rear = 0

 Step 2: Job J2 → Assigned to P2

 Queue: [ J1, J2, _, _, _ ]

 front = 0, rear = 1

 Step 3: Job J3 → Assigned to P3

 Queue: [ J1, J2, J3, _, _ ]

 front = 0, rear = 2
 Step 4: Job J1 (P1) finishes → Dequeue

 Queue: [ _, J2, J3, _, _ ]

 front = 1, rear = 2

 Step 5: Job J4 → Assigned to P4

 Queue: [ _, J2, J3, J4, _ ]
 front = 1, rear = 3

 Step 6: Job J5 → Assigned to P5

 Queue: [ _, J2, J3, J4, J5 ]
 front = 1, rear = 4

 Step 7: Job J2 (P2) finishes → Dequeue

 Queue: [ _, _, J3, J4, J5 ]
 front = 2, rear = 4
 Step 8: Job J6 → Wraps around and is assigned to P1

 Since position 0 is now free, and we use a circular queue, rear wraps:
 rear = 0
 Queue: [ J6, _, J3, J4, J5 ]
 front = 2, rear = 0
 Summary Table:

 | Step | Action | Queue Status | Front | Rear |

 | ---- | ------------------------ | --------------------------- | ------- | ------- |
 | 1 | Enqueue J1 (P1) | \[J1, \_, \_, \_, \_] | 0 | 0 |
 | 2 | Enqueue J2 (P2) | \[J1, J2, \_, \_, \_] | 0 | 1 |
 | 3 | Enqueue J3 (P3) | \[J1, J2, J3, \_, \_] | 0 | 2 |
 | 4 | Dequeue J1 (P1) | \[\_, J2, J3, \_, \_] | 1 | 2 |
 | 5 | Enqueue J4 (P4) | \[\_, J2, J3, J4, \_] | 1 | 3 |
 | 6 | Enqueue J5 (P5) | \[\_, J2, J3, J4, J5] | 1 | 4 |
 | 7 | Dequeue J2 (P2) | \[\_, \_, J3, J4, J5] | 2 | 4 |
 | 8 | Enqueue J6 (P1) | \[J6, \_, J3, J4, J5] | 2 | 0 |

 Why This Is a Circular Queue:

 Once the rear reaches the last printer (P5), the next job is placed at the start (P1) — reusing
space.
 It avoids wasting slots and keeps the job distribution efficient.
 3. Priority Queue
 Description: A priority queue is a special type of queue where each element is assigned a
priority. Elements with higher priority are dequeued before those with lower priority,
regardless of their arrival order. The queue can be implemented using a heap data
structure.
 Operations :
 Enqueue (add with a priority)
 Dequeue (remove the element with the highest priority)
 Example:
 Elements: [(10, 'Low'), (20, 'High'), (30, 'Medium')]
 Priority Queue: (20, 'High') -> (30, 'Medium') -> (10, 'Low')
 Dequeue: (20, 'High') is dequeued first.
 Example:-Task Scheduling in an Operating System
Your computer runs many tasks at the same time:

 Opening apps
 Playing music
 Scanning for viruses
 Saving files
 Running system updates

 The CPU (brain of the computer) decides which task to run next — this is called task scheduling.

 But not all tasks are equally important.

 That’s why the operating system uses a priority queue.

 What is a Priority Queue in Task Scheduling?

 Tasks are placed in a queue based on priority.

 Higher-priority tasks run first, even if they arrived later.
 If two tasks have the same priority, the one that came first runs first (FIFO).
 Step-by-Step Example

 Let’s say your computer has to run these 4 tasks:

 | Task | Arrival Order | Type | Priority |

 | ------------------------- | ------------------ | -------------------------------------- | ---------- |
 | T1: Music App | 1st | User-level app | 3 (Low) |
 | T2: Save File | 2nd | Critical system task | 1 (High) |
 | T3: Antivirus | 3rd | Background security scan | 2 (Medium) |
 | T4: Open Word | 4th | User app | 3 (Low) |

 Lower number = higher priority

 Step 1: Tasks Enter the Scheduler

 Tasks are added to the priority queue:
 Queue (by priority): [T2 (1), T3 (2), T1 (3), T4 (3)]
 Step 2: First Task Runs

 T2 has the highest priority (1) — saving a file.

 It runs first, even though it came in second.
 T2 runs and finishes.

 Step 3: Second Task Runs

 Next is T3 with priority 2 (Antivirus scan).

 It runs second.
 T3 runs and finishes.

 Step 4: Remaining Tasks (T1 and T4)

 Both have priority 3.

 So now we go by arrival order.
 T1 (Music App) runs next.
 T4 (Word App) runs last.
 Final Execution Order:

 1st → T2 (Save File - High Priority)

 2nd → T3 (Antivirus - Medium)
 3rd → T1 (Music App - Low)
 4th → T4 (Open Word - Low)

 🧰 Why Use a Priority Queue?

 | Feature | Explanation |
 | ------------------------- | -------------------------------------------- |
 | Critical tasks come first | System tasks (like saving files) don’t wait |
 | Better performance | Important tasks handled faster |
 | Fair for same priority | FIFO is still followed when priorities match |

 Real World Result:

 Your music may pause for a moment while the file is being saved — because the CPU gave priority to the
save task.
 4. Double-Ended Queue (Deque):
 A deque is a queue where insertion and deletion can happen at both ends, i.e., both
the front and rear of the queue.
 This allows for more flexibility than a simple queue, where elements can be added or
removed from either side.
 Example:
 Front -> [10, 20, 30] -> Rear
Add to Front -> [5, 10, 20, 30]
 Add to Rear -> [5, 10, 20, 30, 40]
 Music Playlist with Skip Option
 Imagine you're using a music player (like Spotify or YouTube Music), and you have the ability
to:

 Add a song to the end of the playlist (normal behavior).

 Add a song to the front (to play next).
 Skip songs from the front (like "next song").
 Remove the last song (maybe you're no longer in the mood).

 This is exactly how a deque (double-ended queue) works.

 Step-by-Step Example Using a Deque

 Let’s say your playlist is empty at the start:

 Playlist (Deque): [ ]
 Step 1: Add "Song A" to the rear

 (You’re adding a normal song to the end of the playlist)

 Playlist: [ A ]

 Step 2: Add "Song B" to the rear

 (Normal behavior – added to the end)

 Playlist: [ A, B ]

 Step 3: Add "Song C" to the front

 (You want this to play next, so you add it to the front)

 Playlist: [ C, A, B ]

 Now C will play before A and B.

 Step 4: Play/Skip (Remove from front)

 (You listen to or skip "C")

 Playlist: [ A, B ]

 Step 5: Add "Song D" to the rear

 (New song added at the end)

 Playlist: [ A, B, D ]

 Step 6: Remove last song (remove from rear)

 (You decide to remove "D")

 Playlist: [ A, B ]
 Step 7: Add "Song E" to the front

 (You want to hear it right now)

 Playlist: [ E, A, B ]

 Final Playlist Order:

 Front → E → A → B ← Rear

 🧰 Why This is a Deque:

 | Action | Deque Operation |

 | ---------------------- | --------------- |
 | Add song to end | Enqueue Rear |
 | Add song to play next | Enqueue Front |
 | Skip/play current song | Dequeue Front |
 | Remove last song | Dequeue Rear |
 ✅ Summary:

 A deque lets your playlist be dynamic:

 You can jump songs to the front

 Skip or remove any from both ends
 And the queue adapts in real time, just like smart playlists
 5. Input-Restricted Queue:
 In an input-restricted queue, elements can only be added (enqueued) at the rear, but
elements can be removed (dequeued) from both the front and the rear.

 Example:
 Enqueue at Rear only, but Dequeue from both Front and Rear.
 Front -> [10, 20] -> Rear
 Dequeue -> [20] (from front)
 Dequeue -> [10] (from rear)
 Task Queue in Office – Input-Restricted Queue Example

 1. In an office, tasks are added to a shared task list for a team.

 2. Employees are only allowed to add tasks at the end of the list (rear).
 3. This keeps the task list organized in order of arrival.
 4. The queue is input-restricted because you cannot add tasks at the front.
 5. The manager reviews tasks and can choose to work on:

 The oldest task (front of the queue), or

 A new urgent task (rear of the queue).
 6. For example:

 Task 1: Write report (added first)

 Task 2: Send email (added second)
 Task 3: Fix server issue (urgent, added last)
 7. Even though the server issue was added last, the manager can remove it from the rear
to work on it immediately.
 8. Meanwhile, the team continues to add new tasks only at the rear.
 9. If the manager finishes the front task (e.g., Task 1), it’s removed from the front.
 10. If an urgent client complaint comes in as the last task, it can be removed from the rear
and handled first.
 11. This gives flexibility in which task to prioritize while keeping task entries organized.
 12. The queue doesn’t allow adding tasks at the front, so everyone follows the same
process.
 13. This structure prevents team members from jumping the line with their tasks.
 14. The manager’s ability to choose from front or rear helps balance routine and urgent
work.
 15. So the task queue in an office acts as an input-restricted queue: only add at rear,
remove from both ends.
 6. Output-Restricted Queue:
 In an output-restricted queue, elements can only be dequeued from the front, but they
can be enqueued at both the front and the rear.
 Example:
 Enqueue at Front or Rear, but only Dequeue from Front.
 Front -> [10, 20] -> Rear
 Dequeue -> [20] (from front)
 Enqueue at Rear -> [20, 30] -> Rear
 Warehouse Loading Queue

 A deque (double-ended queue) where:

 ✅ You can insert at both ends
 ❌ But you can remove (dequeue) only from one end

 Let’s say you manage a small warehouse where goods are loaded into a truck.

 1. In a warehouse, packages are lined up to be loaded onto a delivery truck.

 2. Workers can add new packages to either the front or rear of the line.
 3. For example:
 Urgent packages are added to the front.
 Regular packages are added to the rear.
 4. This gives flexibility to insert from both ends.
 5. But when it's time to load the truck, packages are only removed from the front.
 6. This makes it an output-restricted queue — only one end is used for removal.
 7. So:

 Insert at front (urgent)

 Insert at rear (normal)
 Remove only from front (loading)
 8. Example queue: `[Urgent1, Normal1, Normal2]`
 9. A worker may insert `Urgent2` at the front → `[Urgent2, Urgent1, Normal1, Normal2]`
 10. When loading starts, only `Urgent2` (front) can be removed, not from the rear.
 11. This keeps the truck loading organized and predictable.
 12. It also ensures that urgent packages are loaded first, even if they arrived later.
 13. But it prevents confusion by not allowing unloading from the back.
 14. This structure is useful in many logistics or task scenarios where only one removal point
is safe or efficient.
 15. So, the warehouse queue acts as an output-restricted queue: insert both sides,
remove only from front.

 🧰 Quick Summary of Rules:

 | Operation | Allowed |
 | ----------------- | -------- |
 | Insert at front | ✅ Yes |
 | Insert at rear | ✅ Yes |
 | Remove from front | ✅ Yes |
 | Remove from rear | ❌ No |
 Summary:
 Simple Queue: Basic queue with FIFO behavior.
 Circular Queue: Reuses space to avoid wasted memory.
 Priority Queue: Processes elements based on priority rather than FIFO.
 Deque (Double-Ended Queue): Allows insertion and removal from both ends.
 Input-Restricted Queue: Enqueue only at rear, but dequeue from both ends.
 Output-Restricted Queue: Enqueue at both ends, but dequeue only from the front.
 These different types of queues are used in various applications depending on how
data needs to be managed or processed.
2. Linked Lists.

Introduction to Linked list: Singly, Doubly and Circular Linked Lists.

Operations: Insertion , Deletion, Traversal , Reversal

Real Life application of Linked lists.

Hands on Problems.
Linked Lists
 A linked list is a linear data structure where elements (also called nodes) are connected
using pointers. Each node contains two parts:
 Data: The actual value stored in the node.
 Next Pointer: A reference (or address) to the next node in the sequence.
 The main advantage of linked lists over arrays is that they allow for efficient insertion
and deletion operations, especially when manipulating data in the middle of the list.
 There are several types of linked lists based on how nodes are connected:
 1. Singly Linked List
 A singly linked list is a fundamental data structure, it consists of nodes where each node
contains a data field and a reference to the next node in the linked list. The next of the last
node is null, indicating the end of the list. Linked Lists support efficient insertion and deletion
operations.
 Understanding Node Structure
 In a singly linked list, each node consists of two parts: data and a pointer to the next node.
This structure allows nodes to be dynamically linked together, forming a chain-like
sequence.
 In this example, the Node class contains an integer data field (data) to store the information
and a pointer to another Node (next) to establish the link to the next node in the list.

 Example:
 1. Traversal of Singly Linked List
 Traversal in a linked list means visiting each node and performing operations like printing
or processing data.

 Step-by-step approach:

 Initialize a pointer (current) to the head of the list.

 Loop through the list using a while loop until current becomes NULL.
 Process each node (e.g., print its data).
 Move to the next node by updating current = current->next.
 2. Searching in Singly Linked List
 Searching in a Singly Linked List refers to the process of looking for a specific element or
value within the elements of the linked list.

 Step-by-step approach:

 Start from the head of the linked list.

 Check each node’s data:
 If it matches the target value, return true (element found).
 Otherwise, move to the next node.
 Repeat until the end (NULL) is reached.
 If no match is found, return false.
 3. Length of Singly Linked List
 Finding the length of a Singly Linked List means counting the total number of nodes.

 Step-by-step approach:

 Initialize a counter (length = 0).

 Start from the head, assign it to current.
 Traverse the list:
 Increment length for each node.
 Move to the next node (current = current->next).
 Return the final length when current becomes NULL.
 4. Insertion in Singly Linked List
 Insertion is a fundamental operation in linked lists that involves adding a new node to the
list. There are several scenarios for insertion:
 a. Insertion at the Beginning of Singly Linked List: Insertion at the beginning involves
adding a new node before the current head, making it the new head.
 Step-by-step approach:
 Create a new node with the given value.
 Set the next pointer of the new node to the current head.
 Move the head to point to the new node.
 Return the new head of the linked list.
 b. Insertion at the End of Singly Linked List: To insert a node at the end of the list, traverse
the list until the last node is reached, and then link the new node to the current last node
 Step-by-step approach:
 Create a new node with the given value.
 Check if the list is empty:
 If it is, make the new node the head and return.
 Traverse the list until the last node is reached.
 Link the new node to the current last node by setting the last node's next pointer to the
new node.
 c. Insertion at a Specific Position of the Singly Linked List:
 To insert a node at a specific position, traverse the list to the desired position, link the new node to
the next node, and update the links accordingly.

 Step-by-step approach:
 Create a new node and assign it a value.
 If inserting at the beginning (position = 1):
 Point the new node’s next to the current head.
 Update the head to the new node.
 Return (Insertion done).
 Otherwise, traverse the list:
 Start from the head and move to the (position - 1)ᵗʰ node (just before the desired position).
 If the position is beyond the list length, return an error or append at the end.
 Insert the new node:
 Point the new node’s next to the next node of the current position.
 Update the previous node’s next to the new node.
 Return the updated list.
 5. Deletion in Singly Linked List.
 Deletion involves removing a node from the linked list. Similar to insertion, there are different
scenarios for deletion:
 a. Deletion at the Beginning of Singly Linked List: To delete the first node, update the head
to point to the second node in the list.
 Steps-by-step approach:
 Check if the head is NULL.
 If it is, return NULL (the list is empty).
 Store the current head node in a temporary variable temp.
 Move the head pointer to the next node.
 Delete the temporary node.
 Return the new head of the linked list.
 b. Deletion at the End of Singly Linked List: To delete the last node, traverse the list until the
second-to-last node and update its next field to None.
 Step-by-step approach:
 Check if the head is NULL.
 If it is, return NULL (the list is empty).
 Check if the head's next is NULL (only one node in the list).
 If true, delete the head and return NULL.
 Traverse the list to find the second last node (second_last).
 Delete the last node (the node after second_last).
 Set the next pointer of the second last node to NULL.
 Return the head of the linked list.

 c. Deletion at a Specific Position of Singly Linked List: To delete a node at a specific position,
traverse the list to the desired position, update the links to bypass the node to be deleted.
 Step-by-step approach:
 Check if the list is empty or the position is invalid, return if so.
 If the head needs to be deleted, update the head and delete the node.
 Traverse to the node before the position to be deleted.
 If the position is out of range, return.
 Store the node to be deleted.
 Update the links to bypass the node.
 Delete the stored node.
 Use Cases:-
 1. Inserting at a Specific Position
 2. Deleting a Node by Value
 3. Searching for a Value

 Base Classes (Same as Before)

 class Node:
 def __init__(self, data):
 [Link] = data
 [Link] = None

 class LinkedList:
 def __init__(self):
 [Link] = None
[Link] at a Specific Position (0-based index)

 def insert_at_position(self, data, position):

 new_node = Node(data)
 if position == 0: Insert at head
 new_node.next = [Link]
 [Link] = new_node
 print(f"Inserted {data} at position 0 (head)")
 return

 current = [Link]
 index = 0
 while current and index < position - 1:
 current = [Link]
 index += 1
 if not current:
 print(f"Position {position} out of bounds")
 return

 new_node.next = [Link]
 [Link] = new_node
 print(f"Inserted {data} at position {position}")
 [Link] a Node by Value
 def delete_by_value(self, value):
 current = [Link]
 previous = None

 while current:
 if [Link] == value:
 if previous:
 [Link] = [Link]
 else:
 [Link] = [Link]
 print(f"Deleted node with value {value}")
 return
 previous = current
 current = [Link]

 print(f"Value {value} not found in list")

3. Search for a Value
 def search(self, value):
 current = [Link]
 position = 0
 while current:
 if [Link] == value:
 print(f"Value {value} found at position {position}")
 return True
 current = [Link]
 position += 1
 print(f"Value {value} not found")
 return False
 Complete Example Usage
 Add display method to view the list
 def display(self):
 current = [Link]
 while current:
 print([Link], end=" -> ")
 current = [Link]
 print("None")

 Add these methods to LinkedList class above this block:

 [Link] = display

 Test
 ll = LinkedList()
 ll.insert_at_position(10, 0) Insert at head
 ll.insert_at_position(20, 1) Insert at position 1
 ll.insert_at_position(30, 2) Insert at position 2
 [Link]() 10 -> 20 -> 30 -> None
 ll.delete_by_value(20) Delete node with value 20
 [Link]() 10 -> 30 -> None

 [Link](30) Found
 [Link](100) Not found

 Output:
 Inserted 10 at position 0 (head)
 Inserted 20 at position 1
 Inserted 30 at position 2
 10 -> 20 -> 30 -> None
 Deleted node with value 20
 10 -> 30 -> None
 Value 30 found at position 1
 Value 100 not found
What Are Base Classes in This
Context?
 In our singly linked list example:
 Node is the basic unit of the list — it stores data and a reference to the next node.
 Linked List is the controller or wrapper class that manages the nodes — insertions,
deletions, traversal, etc.
 These are "base" in the sense that:
 They define the foundation of the data structure.
 All higher-level operations build on top of them.
 Why Use Base Classes Like Node and Linked List?

1. Encapsulation
•Keeps logic organized by bundling data and methods into classes.
•Example: Node knows about its own data and next; Linked List handles list-level logic.

2. Separation of Concerns
•Node handles individual elements.
•Linked List handles overall structure and behavior.
•This makes your code cleaner and easier to debug or maintain.

3. Reusability
•Once Node and Linked List are defined, you can:
•Reuse them in different programs.
•Extend them into more advanced structures like doubly linked lists or circular lists.
4. Readability
•Using classes provides a clear blueprint of how the data structure works.
•Easier for others (and your future self) to understand your logic.

5. Scalability
•As your list grows in complexity, having base classes makes it easier to:
•Add features like search, sort, reverse, etc.
•Implement inheritance or polymorphism if needed.
Doubly Linked List
 2. Doubly Linked List
 Each node contains three parts: data, a pointer to the next node, and a pointer to the
previous node.
 This allows traversal in both directions, making operations like deletion from the tail or
insertion before a specific node easier.
 Advantages: More flexible because you can go forward and backward.
 Operations: Both insertion and deletion are more efficient than in singly linked lists,
especially at the tail.
 Example:
 Representation of Doubly Linked List in Data Structure
 In a data structure, a doubly linked list is represented using nodes that have three fields:
1. Data
2. A pointer to the next node (next)
3. A pointer to the previous node (prev)
Each node in a Doubly Linked List contains the data it holds, a pointer to the next node in the
list, and a pointer to the previous node in the list. By linking these nodes together through
the next and prev pointers, we can traverse the list in both directions (forward and
backward), which is a key feature of a Doubly Linked List.
 1. Traversal in Doubly Linked List
 Traversal in a Doubly Linked List involves visiting each node, processing its data, and moving to
the next or previous node using the forward (next) and backward (prev) pointers.

 Step-by-Step Approach for Traversal:

 Start from the head of the list.

 Traverse forward:
 Visit the current node and process its data (e.g., print it).
 Move to the next node using current = current->next.
 Repeat the process until the end of the list (current == NULL).
 Optionally, traverse backward:
 Start from the tail (last node).
 Visit the current node and process its data.
 Move to the previous node using current = current->prev.
 Repeat the process until the beginning of the list (current == NULL).
 Traversal is useful for displaying or processing all nodes in a doubly linked list.
 2. Finding Length of Doubly Linked List
 A Doubly Linked List (DLL) is a type of linked list where each node has two pointers:

 One pointing to the next node in the sequence.

 One pointing to the previous node in the sequence.
 To find the length of a doubly linked list, we need to traverse the list while counting the nodes.

 Step-by-Step Approach for finding length:

 Initialize a counter: Start with a counter variable (count = 0).

 Set a pointer to the head node: Use a pointer (current) and initialize it to the head of the linked
list.
 Traverse the list:
 While the pointer (current) is not NULL, increment the count by 1.
 Move to the next node (current = [Link]).
 Stop at the end of the list: When the pointer reaches NULL, stop the loop.
 Return the count: The final value of count gives the length of the doubly linked list.
 3. Insertion in a Doubly Linked List
 Insertion in a Doubly Linked List (DLL) involves adding a new node at a specific position
while maintaining the connections between nodes. Since each node contains a pointer
to both the previous and next node, insertion requires adjusting these pointers carefully.

 There are three primary types of insertion in a DLL:

 1. Insertion at the Beginning

 Create a new node with the given data.

 Set the next pointer of the new node to the current head.
 If the list is not empty, update the prev pointer of the current head to point to the new
node.
 Update the head of the list to the new node.
 2. Insertion at the End

 Create a new node with the given data.

 If the list is empty, set the new node as the head.
 Traverse the list until the last node is found.
 Set the next pointer of the last node to the new node.
 Set the prev pointer of the new node to the last node.

 3. Insertion at a Specific Position

 Create a new node with the given data.

 If inserting at the beginning, follow the steps for insertion at the start.
 Traverse the list to find the node after which insertion is needed.
 Set the next pointer of the new node to the next node of the current position.
 Set the prev pointer of the new node to the current node.
 Update the prev pointer of the next node to point to the new node (if it exists).
 Update the next pointer of the previous node to point to the new node.
 4. Deletion in a Doubly Linked List
 Deletion in a Doubly Linked List (DLL) involves removing a node while maintaining the
integrity of the list. Since each node contains pointers to both its previous and next nodes,
deletion requires careful pointer adjustments to ensure no broken links occur.

 Types of Deletion in a Doubly Linked List

 1. Deletion at the Beginning

 Check if the list is empty; if it is, return as there is nothing to delete.
 Store the current head node in a temporary variable.
 Move the head pointer to the next node.
 If the new head exists, update its prev pointer to NULL.
 Delete the old head node to free memory.
 2. Deletion at the End

 Check if the list is empty; if it is, return.

 Traverse the list to find the last node.
 Store the last node in a temporary variable.
 Update the next pointer of the second-last node to NULL, making it the new tail.
 Delete the last node to free memory.

 3. Deletion at a Specific Position

 Check if the list is empty; if it is, return.

 Traverse the list to find the node to be deleted.
 Store the node to be deleted in a temporary variable.
 Update the next pointer of the previous node to point to the next node.
 Update the prev pointer of the next node to point to the previous node (if it exists).
 Delete the target node to free memory.
 1. Inserting at a Specific Position.
 2. Deleting a Node by Value.
 3. Searching for a Value.

 Step 1: Define Node and Doubly Linked List Classes

 class Node:
 def __init__(self, data):
 [Link] = data
 [Link] = None
 [Link] = None

 class DoublyLinkedList:
 def __init__(self):
 [Link] = None
 [Link] at a Specific Position (0-based)

 def insert_at_position(self, data, position):

 new_node = Node(data)

 if position == 0:
 new_node.next = [Link]
 if [Link]:
 [Link] = new_node
 [Link] = new_node
 print(f"Inserted {data} at head")
 return

 current = [Link]
 index = 0
 while current and index < position - 1:
 current = [Link]
 index += 1
 if current is None:
 print(f"Position {position} out of bounds")
 return

 new_node.next = [Link]
 new_node.prev = current

 if [Link]:
 [Link] = new_node

 [Link] = new_node
 print(f"Inserted {data} at position {position}")
 [Link] a Node by Value
 def delete_by_value(self, value):
 current = [Link]

 while current:
 if [Link] == value:
 if [Link]:
 [Link] = [Link]
 else:
 [Link] = [Link] Node is head

 if [Link]:
 [Link] = [Link]
 print(f"Deleted node with value {value}")
 return
 current = [Link]

 print(f"Value {value} not found in list")

 [Link] for a Value

 def search(self, value):

 current = [Link]
 position = 0
 while current:
 if [Link] == value:
 print(f"Found {value} at position {position}")
 return True
 current = [Link]
 position += 1
 print(f"{value} not found")
 return False
 Display List Forward


 def display_forward(self):
 current = [Link]
 print("List (forward):", end=" ")
 while current:
 print([Link], end=" <-> ")
 last = current
 current = [Link]
 print("None")
Example Usage
 dll = DoublyLinkedList()
 dll.insert_at_position(10, 0) Insert at head
 dll.insert_at_position(20, 1) Insert at tail
 dll.insert_at_position(15, 1) Insert in middle
 dll.display_forward() 10 <-> 15 <-> 20 <-> None

 dll.delete_by_value(15)
 dll.display_forward() 10 <-> 20 <-> None

 [Link](20) Found
 [Link](100) Not found
Output:
 Inserted 10 at head
 Inserted 20 at position 1
 Inserted 15 at position 1
 List (forward): 10 <-> 15 <-> 20 <-> None
 Deleted node with value 15
 List (forward): 10 <-> 20 <-> None
 Found 20 at position 1
 100 not found
 Applications of Doubly Linked List
 Implementation of undo and redo functionality in text editors.
 Cache implementation where quick insertion and deletion of elements are required.
 Browser history management to navigate back and forth between visited pages.
 Music player applications to manage playlists and navigate through songs efficiently.
 Implementing data structures like Deque (double-ended queue) for efficient insertion
and deletion at both ends.
Circular Linked Lists
 What is a Circular Linked List?
 A circular linked list is a special type of linked list where all the nodes are connected to form
a circle. Unlike a regular linked list, which ends with a node pointing to NULL, the last node
in a circular linked list points back to the first node. This means that you can keep traversing
the list without ever reaching a NULL value.

 Types of Circular Linked Lists

 We can create a circular linked list from both singly linked lists and doubly linked lists. So,
circular linked lists are basically of two types:
 1. Circular Singly Linked List
 In Circular Singly Linked List, each node has just one pointer called the “next” pointer. The
next pointer of the last node points back to the first node and this results in forming a
circle.
 In this type of Linked list, we can only move through the list in one direction.
 2. Circular Doubly Linked List:
 In circular doubly linked list, each node has two pointers prev and next, similar to doubly
linked list.
 The prev pointer points to the previous node and the next points to the next node. Here,
in addition to the last node storing the address of the first node, the first node will also
store the address of the last node.
 Representation of a Circular Singly Linked List
 Let’s take a look on the structure of a circular linked list.


 Example of Creating a Circular Linked List
 Here’s an example of creating a circular linked list with three nodes (2, 3, 4):

 we have created three nodes first, second, and last having values 2, 3, and 4 respectively.
 After creating three nodes, we have connected these node in a series.
 Connect the first node “first” to “second” node by storing the address of “second” node
into first’s next
 Connect the second node “second” to “third” node by storing the address of “third” node
into second’s next
 After connecting all the nodes, we reach the key characteristic of a circular linked
list: linking the last node back to the first node. Therefore, we store the address of the “first”
node in the “last” node.
 Why have we taken a pointer that points to the last node instead of the first node?
 For the insertion of a node at the beginning, we need to traverse the whole list. Also, for
insertion at the end, the whole list has to be traversed. If instead of the start pointer, we
take a pointer to the last node, then in both cases there won’t be any need to traverse
the whole list. So insertion at the beginning or at the end takes constant time, irrespective
of the length of the list.
 Operations on the Circular Linked list
 We can do some operations on the circular linked list similar to the singly and doubly linked
list which are:

 1. Insertion

 Insertion at the empty list

 Insertion at the beginning
 Insertion at the end
 Insertion at the given position
 2. Deletion

 Delete the first node

 Delete the last node
 Delete the node from any position

 3. Searching
 Insertion in the circular linked list
 Insertion is a fundamental operation in linked lists that involves adding a new node to
the list. The only extra step is connecting the last node to the first one. In the circular
linked list mentioned below, we can insert nodes in four ways:

 1. Insertion in an empty List in the circular linked list

 To insert a node in empty circular linked list, creates a new node with the given data,
sets its next pointer to point to itself, and updates the last pointer to reference this new
node.
 2. Insertion at the beginning in circular linked list
 To insert a new node at the beginning of a circular linked list, we create a new node and
check if the list is empty. If empty, the new node points to itself. If not, we make the new
node’s next pointer point to the current head (last->next) and update the last node’s
next to the new node, preserving the circular structure.
 3. Insertion at the end in circular linked list
 To insert a node at the end of a circular linked list, we create the new node and, if the list
is empty, make it point to itself. Otherwise, we update the tail’s next pointer to the new
node and then set the tail to the new node, preserving the circular linkage.
 4. Insertion at specific position in circular linked list
 To insert a node at a specific position in a circular linked list, we handle edge cases for an
empty list and invalid positions. For valid positions, we traverse the list and adjust the
pointers to insert the new node, updating the tail if it’s inserted at the end.
 Deletion from a Circular Linked List
 Deletion involves removing a node from the linked list. The main difference is that we need
to ensure the list remains circular after the deletion. We can delete a node in a circular
linked list in three ways:

 1. Delete the first node in circular linked list

 To delete the first node of a circular linked list, we check if the list is empty or has only one
node. If so, we handle those cases by deleting the node and updating the last pointer. For
multiple nodes, we update the last node’s next pointer to skip the head and free the head
node, returning the updated last pointer.
 2. Delete a specific node in circular linked list
 To delete a specific node from a circular linked list, we handle empty list and single node
cases. For other nodes, we use two pointers to find the node, update the previous node’s
next pointer to skip the target, and delete it, updating the last pointer if needed.
 3. Deletion at the end of Circular linked list
 To delete the last node in a circular linked list, we handle the empty and single node
cases. For multiple nodes, we traverse to find the second last node, update its next pointer
to the head, delete the last node, and return the updated last pointer.
 Applications of Circular Linked Lists
 It is used for time-sharing among different users, typically through a Round-Robin
scheduling mechanism.
 In multiplayer games, a circular linked list can be used to switch between players.
After the last player’s turn, the list cycles back to the first player.
 Circular linked lists are often used in buffering applications, such as streaming data,
where data is continuously produced and consumed.
 In media players, circular linked lists can manage playlists, this allowing users to loop
through songs continuously.
 Browsers use circular linked lists to manage the cache. This allows you to navigate
back through your browsing history efficiently by pressing the BACK button.
•Insert at Specific Position
•Delete by Value
•Search for a Value

•Step 1: Node and Circular LinkedList Classes

•class Node:
• def __init__(self, data):
• [Link] = data
• [Link] = None

•class CircularLinkedList:
• def __init__(self):
• [Link] = None
 [Link] at a Specific Position (0-based)
 def insert_at_position(self, data, position):
 new_node = Node(data)

 if [Link] is None:
 Empty list case
 new_node.next = new_node Circular link to self
 [Link] = new_node
 print(f"Inserted {data} in empty list")
 return

 if position == 0:
 Inserting at head
 new_node.next = [Link]
 current = [Link]
 while [Link] != [Link]:
 current = [Link]
 [Link] = new_node
 [Link] = new_node
 print(f"Inserted {data} at head")
 return
 Insert at specific position (not head)
 current = [Link]
 index = 0
 while [Link] != [Link] and index < position - 1:
 current = [Link]
 index += 1

 new_node.next = [Link]
 [Link] = new_node
 print(f"Inserted {data} at position {position}")
 [Link] by Value
 def delete_by_value(self, value):
 if [Link] is None:
 print("List is empty")
 return

 current = [Link]
 prev = None

 while True:
 if [Link] == value:
 if prev is None:
 Deleting the head
 if [Link] == [Link]:
 [Link] = None Only one node
 else:
 tail = [Link]
 while [Link] != [Link]:
 tail = [Link]
 [Link] = [Link]
 [Link] = [Link]
 print(f"Deleted head node with value {value}")
 else:
 [Link] = [Link]
 print(f"Deleted node with value {value}")
 return
 prev = current
 current = [Link]
 if current == [Link]:
 break

 print(f"Value {value} not found")

[Link] for a Value
 def search(self, value):
 if [Link] is None:
 print("List is empty")
 return False

 current = [Link]
 index = 0
 while True:
 if [Link] == value:
 print(f"Found {value} at position {index}")
 return True
 current = [Link]
 index += 1
 if current == [Link]:
 break

 print(f"{value} not found")

 return False
Example Usage
 cll = CircularLinkedList()
 cll.insert_at_position(10, 0)
 cll.insert_at_position(20, 1)
 cll.insert_at_position(30, 2)
 [Link]() 10 -> 20 -> 30 -> (back to head)

 cll.insert_at_position(5, 0)
 [Link]() 5 -> 10 -> 20 -> 30 -> (back to head)

 cll.delete_by_value(20)
 [Link]() 5 -> 10 -> 30 -> (back to head)

 [Link](10) Found
 [Link](100) Not found
Output:-
 Inserted 10 in empty list
 Inserted 20 at position 1
 Inserted 30 at position 2
 List: 10 -> 20 -> 30 -> (back to head: 10)
 Inserted 5 at head
 List: 5 -> 10 -> 20 -> 30 -> (back to head: 5)
 Deleted node with value 20
 List: 5 -> 10 -> 30 -> (back to head: 5)
 Found 10 at position 1
 100 not found