DSA

  DSA (Data Structures and Algorithms) is the study of organizing data efficiently using data structures like arrays, stacks, and trees, paired with step-by-step procedures (or algorithms) to solve problems effectively. Data structures manage how data is stored and accessed, while algorithms focus on processing this data.

==========================================================================

Analysis of Algorithms

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem.

How do we compare two order of growths?
The following are some standard terms that we must remember for comparison.

c < Log Log n < Log n < n1/3 < n1/2 < n < n Log n < n2 < n2 Log n < n3 < n4 < 2n < nn

Here c is a constant

To analyze loops for complexity:

1. Understand the loop bounds

• Linear loop: for i in range(n) → O(n). 
  The time complexity of a function (or set of statements) is considered as O(1) if it doesn't contain a loop, recursion, and call to any other non-constant time function. 

   i.e. set of non-recursive and non-loop statements

• Nested loop: for i in range(n): for j in range(n) → O(n²)
  The Time Complexity of a loop is considered as O(n) if the loop variables are incremented/decremented by a constant amount.
  
  The time complexity is defined as an algorithm whose performance is directly proportional to the squared size of the input data, as in nested loops it is equal to the number of times the innermost statement is executed. For example, the following sample loops have O(n2) time complexity 

• Logarithmic loop: while i < n: i *= 2 → O(log n)
  The time Complexity of a loop is considered as O(Logn) if the loop variables are divided/multiplied by a constant amount. And also for recursive calls in the recursive function, the Time Complexity is considered as O(Logn).
  

  

  
  

• Logarithmic Time Complexity O(Log Log n): 
  The Time Complexity of a loop is considered as O(LogLogn) if the loop variables are reduced/increased exponentially by a constant amount. 
  

  
  
  

2. Look at nested vs sequential loops

• Sequential loops (one after another): Add their complexities → O(n) + O(n²) = O(n²)


  
  



• Nested loops: Multiply complexities → O(n) * O(n) = O(n²)

3. Consider conditional branches (if-else)

• Focus on the worst-case path when calculating worst-case complexity.

Asymptotic Notations for Analysis of Algorithms

Asymptotic notations describe how an algorithm’s time or space complexity grows as the input size (n) increases — particularly when n becomes very large. These notations help us compare the efficiency of algorithms, independent of machine and implementation details.

There are mainly three asymptotic notations:

1. Big-O Notation (O-notation) - worst case
2. Omega Notation (Ω-notation) - best case
3. Theta Notation (Θ-notation) - average case

🔺 1. Big-O Notation – O(f(n))

• Definition: Describes the upper bound (worst-case) of an algorithm.

• Use: Guarantees that the algorithm won’t take more than this time.

• Example:
  If an algorithm takes at most 5n^2 + 3n + 7 steps, we write:
  O(n²) (drop constants and lower-order terms).

✅ Think: "At most this fast."

---

🔻 2. Omega Notation – Ω(f(n))

• Definition: Describes the lower bound (best-case) of an algorithm.

• Use: Guarantees that the algorithm takes at least this much time.

• Example:
  If in the best case, it takes n steps, we write:
  Ω(n)

✅ Think: "At least this fast."

---

⚖️ 3. Theta Notation – Θ(f(n))

• Definition: Describes the tight bound — both upper and lower bounds.

• Use: When the algorithm always takes about this much time, regardless of best or worst case.

• Example:
  If an algorithm always takes 3n + 2 steps, then:
  Θ(n)

✅ Think: "Exactly this fast (asymptotically)."

Properties of Asymptotic Notations

✅ 1. General Property (Multiplicative Constants)

If
  f(n) = O(g(n)),
then
  a × f(n) = O(g(n)) (where a is a positive constant)

✅ 2. Transitive Property

If
  f(n) = O(g(n)) and g(n) = O(h(n)),
then
  f(n) = O(h(n))

==========================================================================

Searching Algorithms

Linear Search : It is used for an unsorted array.

Binary Search : It is used for a sorted array

-----recursive

==========================================================================

Sorting Techniques

Linear search

Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30

=============================

Binary search

used in a sorted array by repeatedly dividing the search interval in half.

It works by repeatedly dividing the search interval in half:

• If the target value is equal to the middle element — ✅ return its index.

• If the target is less than the middle element — 🔽 search the left half.

• If the target is greater — 🔼 search the right half.

----

⏱️ Step-by-Step Breakdown

Let’s say the array has n elements.

• 1st step: search space = n

• 2nd step: search space = n/2

• 3rd step: search space = n/4

• ...

• After k steps: n / (2^k) = 1

Solve for k:

$$\frac{n}{2^k} = 1 \Rightarrow 2^k = n \Rightarrow k = \log_2(n)$$

We want to know how many times (k) we can divide by 2 before we’re down to 1 element.

=============================

Quick sort

✅ Steps:

1. Pick a Pivot: Choose an element from the array.

   • Common choices: first, last, middle, or random.

2. Partition the Array:

   • Rearrange the elements so that:

     • All elements less than or equal to the pivot go to the left.

     • All elements greater than the pivot go to the right.

3. Recursively apply Quick Sort to the left and right sub-arrays.

4. Combine the sorted sub-arrays and the pivot to get the final sorted list.

arr = [10, 7, 8, 9, 1, 5]

Step 1: Choose a pivot

Let’s pick the last element, 5, as the pivot.

Step 2: Partition the list

• Elements less than or equal to 5 → [1]

• Pivot → 5

• Elements greater than 5 → [10, 7, 8, 9]

New list:

[1] + [5] + [10, 7, 8, 9]

---

Step 3: Recursively sort sublists

Sort [1] → already sorted.
Sort [10, 7, 8, 9], pivot = 9:

• Left of 9: [7, 8]

• Pivot: 9

• Right of 9: [10]

Sort [7, 8] (pivot = 8):

• Left: [7]

• Pivot: 8

• Right: []

Now everything is sorted:

[1] + [5] + [7] + [8] + [9] + [10]

Result:

[1, 5, 7, 8, 9, 10]

arr[:-1] — gives you everything except the last element.

=============================

Merge sort

Merge Sort is a classic Divide and Conquer algorithm. It breaks the list into smaller sublists, sorts them, and merges them back together.

🧠 Key Idea:

• Breaking down the problem into small subproblems

• Merging two sorted arrays efficiently (like zippering)

=============================

Bubble Sort - O(n^2) Time and O(1) Space

🔁 How Bubble Sort Works

1. Start from the beginning of the list.

2. Compare the first two elements:

   • If the first is greater than the second, swap them.

3. Move to the next pair (2nd and 3rd), and repeat step 2.

4. Continue until the end of the list (this completes one pass).

5. Repeat the process for the remaining elements (n-1 times in total).

🔔 Largest elements "bubble up" to the end in each pass.

👀 Visualization

For this list:
[5, 3, 8, 4, 2]

Pass 1:

• Compare 5 and 3 → Swap → [3, 5, 8, 4, 2]

• Compare 5 and 8 → OK

• Compare 8 and 4 → Swap → [3, 5, 4, 8, 2]

• Compare 8 and 2 → Swap → [3, 5, 4, 2, 8]

✅ Largest element (8) is now at the end.

Pass 2:

• Compare 3 and 5 → OK

• Compare 5 and 4 → Swap → [3, 4, 5, 2, 8]

• Compare 5 and 2 → Swap → [3, 4, 2, 5, 8]
  (No need to compare 8, it's already sorted)

...and so on until the list is sorted.

# Optimized Python program for implementation of Bubble Sort

def bubbleSort(arr):

    n = len(arr)

    

    # Traverse through all array elements

    for i in range(n):

        swapped = False

        # Last i elements are already in place

        for j in range(0, n-i-1):

            # Traverse the array from 0 to n-i-1

            # Swap if the element found is greater

            # than the next element

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

                swapped = True

        if (swapped == False):

            break

if __name__ == "__main__":

    arr = [5, 6, 1, 3]

    bubbleSort(arr)

    for i in range(len(arr)):

        print("%d" % arr[i], end=" ")

=============================

Insertion Sort - O(n^2) Time and O(1) Space

⚙️ How Insertion Sort Works

Given an array:
[7, 3, 5, 2]

You treat the first element as sorted, then:

1. Pick the next element (3) and compare it with the sorted portion (7), insert it in the correct position → [3, 7, 5, 2]

2. Pick 5, compare with 7 and 3, and insert it → [3, 5, 7, 2]

3. Pick 2, compare with all before, and insert it → [2, 3, 5, 7]

🔁 You shift larger elements to the right to make space for the insertion.

=============================

Selection Sort - O(n^2) Time and O(1) Space

👣 Step-by-Step Example

Sort [64, 25, 12, 22, 11] using selection sort:

• Step 1: Find min (11), swap with 64 → [11, 25, 12, 22, 64]

• Step 2: Find min (12), swap with 25 → [11, 12, 25, 22, 64]

• Step 3: Find min (22), swap with 25 → [11, 12, 22, 25, 64]

• Step 4: Already sorted

==========================================================================

Hashing in Data Structure

Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that allows for quick access.

• Hashing refers to the process of generating a small sized output (that can be used as index in a table) from an input of typically large and variable size. Hashing uses mathematical formulas known as hash functions to do the transformation. This technique determines an index or location for the storage of an item in a data structure called Hash Table.
• Hashing involves mapping data to a specific index in a hash table (an array of items) using a hash function. It enables fast retrieval of information based on its key.
• The great thing about hashing is, we can achieve all three operations (search, insert and delete) in O(1) time on average.
• Hashing is mainly used to implement a set of distinct items (only keys) and dictionaries (key value pairs).

There are mainly two forms of hash typically implemented in programming languages.
Hash Set : Collection of unique keys Implemented as Set in Python.
Hash Map : Collection of key value pairs with keys being unique (Implemented as dictionary in Python)

🔐 What is a Hash Function?
A hash function is a function that takes an input (or "key") and returns a fixed-size string or number, usually used to index data in a hash table.
Efficient data lookup
Quick insertion and deletion
Avoid collisions (ideally)

What is Collision in Hashing?

When two or more keys have the same hash value, a collision happens. 

Collision Resolution Techniques

✅ Collision Resolution Techniques

There are two main categories:

1. Open Hashing (Chaining)

• Each index in the hash table points to a linked list (or chain) of keys that hash to that index.

Linked List (or a Dynamic Sized Array) is used to implement this technique. So what happens is, when multiple elements are hashed into the same slot index, then these elements are inserted into a singly-linked list which is known as a chain. 

2. Closed Hashing (Open Addressing)

• All elements are stored within the table.

• On collision, find another empty slot using a probing technique.

==========================================================================

🔍 What is the Two Pointers Technique?

It involves using two variables (pointers) that move through the data structure (like an array) either:

• From both ends toward the center, or

• Sequentially through the array with different speeds or position

used for Two Sum in Sorted Arrays, Closest Two Sum, Three Sum, Four Sum, Trapping Rain Water

1.Two Sum - Pair sum in sorted array

Input: arr[] = {2, 7, 11, 15}, target = 9
Output: 1 2
Explanation: Since the array is 1-indexed, arr[1] + arr[2] = 2 + 7 = 9
Input: arr[] = [1, 3, 4, 6, 8, 11] target = 10
Output: 3 4
Explanation: Since the array is 1-indexed, arr[3] + arr[5] = 4 + 6 = 10

Input: arr[] = {10, 20, 35, 50}, target =70
Output: Yes
Explanation : There is a pair (20, 50) with given target.

Two-Pointer Technique - O(n) time and O(1) space

The idea of this technique is to begin with two corners of the given array. We use two index variables left and right to traverse from both corners.

Initialize: left = 0, right = n - 1
Run a loop while left < right, do the following inside the loop

• Compute current sum, sum = arr[left] + arr[right]
• If the sum equals the target, we’ve found the pair.
• If the sum is less than the target, move the left pointer to the right to increase the sum.
• If the sum is greater than the target, move the right pointer to the left to decrease the sum.

2. Reverse an Array

3. Remove Duplicates from Sorted Array

nums = [1, 1, 2, 2, 3, 4, 4]

Length = 4

Modified nums = [1, 2, 3, 4, _, _, _]  ← Values after 4 are irrelevant

Pointers:

i → tracks position of last unique element

j → scans the array from beginning to end

Logic:

Start with i = 0

Start j = 1 and loop through the array.

If nums[j] != nums[i], it means you've found a new unique element:

Increment i

Copy nums[j] to nums[i]

At the end, i + 1 will be the count of unique elements.

4.Two Sum - Pair Closest to 0

Input: arr[] = [-8, 5, 2, -6]

Output: -1
Explanation: The min absolute sum pair is (5, -6)

5.Sum - Triplet Sum in Array

Input: arr[] = [1, 4, 45, 6, 10, 8], target = 13
Output: true
Explanation: The triplet [1, 4, 8] sums up to 13

6.Trapping Rain Water Problem

Input: arr[] = [3, 0, 1, 0, 4, 0, 2]

Output: 10

Explanation: The expected rainwater to be trapped is shown in the above image.

🔑 Idea:

At each index, the amount of water trapped depends on the minimum of the maximum heights to its left and right, minus the height of the bar at that index.

At each index, water trapped =
sum of min(highest bar on left, highest bar on right) - current height










Steps:

1. Initialize two pointers: left = 0 and right = len(height) - 1

2. Maintain left_max and right_max

3. Move the pointer pointing to the shorter bar inward

4. If height[left] < height[right]:

   • If height[left] >= left_max, update left_max

   • Else, add left_max - height[left] to result

5. Similar logic if height[right] < height[left]

==========================================================================

Sliding Window Technique

Sliding Window Technique is a method used to solve problems that involve subarray or substring or window.

• The main idea is to use the results of previous window to do computations for the next window.
• This technique is commonly used in algorithms like finding subarrays with a specific sum, finding the longest substring with unique characters, or solving problems that require a fixed-size window to process elements efficiently.

Input  : arr[] = {100, 200, 300, 400}, k = 2
Output : 700
We get maximum sum by considering the subarray [300, 400]

1.Maximum Sum of a Subarray with K Elements

Input  : arr[] = {100, 200, 300, 400}, k = 2
Output : 700
We get maximum sum by considering the subarray [300, 400]

Slide the Window

In each step, remove the element going out from the left and add the new element coming from the right.

==========================================================================

Prefix Sum Array

Input: arr[] = [10, 20, 10, 5, 15]
Output: [10, 30, 40, 45, 60]
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 10, 
prefixSum[1] = 10 + 20 = 30, 
prefixSum[2] = 10 + 20 + 10 = 40 and so on.

==========================================================================

String in Data Structure

==========================================================================

ARRAY

Array is a collection of items of the same variable type that are stored at contiguous memory locations.

The idea of an array is to represent many instances in one variable.

🎯 Why Do We Need Arrays?

Imagine this situation:

🧠 Without Arrays:

You want to store marks for 5 students:

mark1 = 85
mark2 = 92
mark3 = 78
mark4 = 90
mark5 = 88

✅ Works for a small number.

❌ But what if there are 1000 students?
You’d have to create 1000 variables manually — that's impractical and unmanageable.

🔹 1. Fixed Size Arrays

✅ Definition: Arrays with a predetermined size that cannot change after creation.
arr = [0] * 5  # Creates: [0, 0, 0, 0, 0]

⚠️ Problems with fixed-size arrays:

• Wasted memory if array is too big.

• Insufficient memory if array is too small.

• Need to know the size in advance.

🔸 2. Dynamic Size Arrays

✅ Definition: Arrays that can grow or shrink in size during runtime.

arr = []

arr.append(10)

arr.append(20)

print(arr)  # Output: [10, 20]

INSERT

Insert Element at the Beginning of an Array

---------------------------------------------------------

Insert Element at a given position in an Array

---------------------------

Insert Element at the End of an Array

 # Insert element at the end

    arr.append(ele)

DELETE

Delete an Element from the Beginning of an Array

-------------------------------

Delete First Occurrence of Given Element from an Array

------------

# Python program to delete the first occurrence of an

# element in the array using custom method

if __name__ == "__main__":

    arr = [10, 20, 20, 20, 30]

    n = len(arr)

    ele = 20

    print("Array before deletion")

    for i in range(n):

        print(arr[i], end=" ")

    

    found = False

    for i in range(n):

      

        # If the element has been found previously,

        # shift the current element to the left

        if found:

            arr[i - 1] = arr[i]

        

        # check if the current element is equal to

        # the element to be removed

        elif arr[i] == ele:

            found = True

    

    # If element was found, reduce the size of array

    if found:

        n -= 1

    

    print("\nArray after deletion")

    for i in range(n):

        print(arr[i], end=" ")

Remove All Occurrences of an Element in an Array

Delete an Element from the end of an array

-------------------------

Reverse Traversal

Searching Elements in an Array

===========================================================

QUEUE

A Queue is a linear data structure that stores elements in the order they were added.
It follows the FIFO (First In, First Out) principle:

• The first element inserted is the first one to be removed.

📦 Think of it like a line at a ticket counter — first person in the line is served first.

Python Queue can be implemented by the following ways:

• list
• collections.deque
• queue.Queue

Append # Use append() to add the element 8 to the end of the list

1.Implementation using collections.deque

Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. Instead of enqueue and deque, append() and popleft() functions are used.

2.Implementation using queue.Queue

Queue is built-in module of Python which is used to implement a queue. queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A maxsize of zero ‘0’ means a infinite queue. This Queue follows FIFO rule. 

There are various functions available in this module: 

• maxsize – Number of items allowed in the queue.
• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
• get() – Remove and return an item from the queue. If queue is empty, wait until an item is available.
• get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
• put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
• qsize() – Return the number of items in the queue.

========================================

Deque in Python

A deque stands for Double-Ended Queue. It is a data structure that allows adding and removing elements from both ends efficiently. Unlike regular queues, which are typically operated on using FIFO (First In, First Out) principles, a deque supports both FIFO and LIFO (Last In, First Out) operations.

🔁 What Makes a deque Special?

Unlike regular queues or stacks, a deque allows:

• Appending at both ends: append() and appendleft()

• Popping from both ends: pop() and popleft()

This makes it useful for implementing both:

• FIFO → like a regular queue (append + popleft)

• LIFO → like a stack (append + pop)

Types of Restricted Deque Input

• Input Restricted Deque:  Input is limited at one end while deletion is permitted at both ends.
• Output Restricted Deque: output is limited at one end but insertion is permitted at both ends.

Appending and Deleting Dequeue Items

• append(x): Adds x to the right end of the deque.
• appendleft(x): Adds x to the left end of the deque.
• extend(iterable): Adds all elements from the iterable to the right end.
• extendleft(iterable): Adds all elements from the iterable to the left end (in reverse order).
• remove(value): Removes the first occurrence of the specified value from the deque. If value is not found, it raises a ValueError.
• pop(): Removes and returns an element from the right end.
• popleft(): Removes and returns an element from the left end.
• clear(): Removes all elements from the deque.

Accessing Item and length of deque

• Indexing: Access elements by position using positive or negative indices.
• len(): Returns the number of elements in the deque.

Count, Rotation and Reversal of a deque

• count(value): This method counts the number of occurrences of a specific element in the deque.
• rotate(n): This method rotates the deque by n steps. Positive n rotates to the right and negative n rotates to the left.
• reverse(): This method reverses the order of elements in the deque.

==========================================================================

Stack Data Structure

🥞 What is a Stack?

A Stack is a linear data structure where:

• Insertion and deletion of elements happen at only one end: the top.

• It follows the LIFO (Last In, First Out) principle.

Think of it like:

• A stack of books or plates.

• You can only take the top one off first.

• You can only add one on top.

Basic Operations on Stack:

In order to make manipulations in a stack, there are certain operations provided to us.

• push() to insert an element into the stack
• pop() to remove an element from the stack
• top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• isFull() returns true if the stack is full else false.

✅ Algorithm for Push Operation

1. Check for Overflow:

   • If the stack has reached its maximum capacity (top == capacity - 1), it’s full, and we cannot push any more items.

   • This condition is called Stack Overflow.

2. Insert the Element:

   • If there's space, increment top by 1: top = top + 1.

   • Place the new element at the top index: stack[top] = value.

✅ Algorithm for Pop Operation

1. Check for Underflow:

   • If the stack is empty (top == -1), there are no elements to pop.

   • This situation is called Stack Underflow.

2. Remove the Element:

• Store the value at the top index.

• Decrease top by 1 (top = top - 1).

• Return or print the stored value.

Implementation using Fixed Sized Array

Implementation using Dynamic Sized Array

Stack - Linked List Implementation

# Node structure

class Node:

    def __init__(self, new_data):

        self.data = new_data

        self.next = None

# Stack using linked list

class Stack:

    def __init__(self):

        self.head = None

    # Check if stack is empty

    def isEmpty(self):

        return self.head is None

    # Push an element onto stack

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

    # Pop the top element

    def pop(self):

        if self.isEmpty():

            return

        self.head = self.head.next

    # Return the top element

    def peek(self):

        if not self.isEmpty():

            return self.head.data

        return float('-inf')

st = Stack()

st.push(11)

st.push(22)

st.push(33)

st.push(44)

print(st.peek())

st.pop()

st.pop()

print(st.peek())

Stack Implementation using Deque

=================================================================

Linked List

A linked list is a fundamental data structure in computer science. It mainly allows efficient insertion and deletion operations compared to arrays.

📌 What is a Singly Linked List?

A Singly Linked List is a linear data structure consisting of a sequence of nodes, where each node contains:

1. Data – the value stored in the node.

2. Next – a reference (or pointer) to the next node in the sequence.

The last node has its next set to None, indicating the end of the list.

1.Traversal of Singly Linked List

or recursion

2.Searching in Singly Linked List

recursion

3.Find Length of a Linked List

4.Insertion in Singly Linked List

Step-by-step approach at start:

• 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.

Original Linked List: 2 3 4 5
After inserting Nodes at the front: 1 2 3 4 5

Step-by-step approach to insert at last:

• 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.

Step-by-step approach at any position:

• 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.Reverse in Singly Linked List

Step-by-step approach:

• Initialize three pointers:
  • prev = NULL (to track the previous node)
  • current = head (starting point)
  • next = NULL (to store the next node temporarily)
• Iterate through the list:
  • Store next = current->next (save next node).
  • Reverse the link: current->next = prev.
  • Move prev and current forward (prev = current, current = next).
• Update head to prev (new head is the last node).

recursion

6.Deleting in Singly Linked List

Steps-by-step approach at start:

• 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.

Step-by-step approach at end:

• 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.

Step-by-step approach at pos:

• 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.

=================================================================

Doubly Linked List Tutorial

The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. 

This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.

1.Step-by-Step Approach for Traversal:

1. Start from the head of the list.
2. 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).
3. 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).

1. Forward Traversal

recursion

2. Backward Traversal of Doubly Linked List

2. Finding Length of Doubly Linked List

3. Insertion in a Doubly Linked List

1. Insertion at the Beginning

1. Create a new node with the given data.
2. Set the next pointer of the new node to the current head.
3. If the list is not empty, update the prev pointer of the current head to point to the new node.
4. Update the head of the list to the new node.

2. Insertion at a Specific Position

1. Create a new node with the given data.
2. If inserting at the beginning, follow the steps for insertion at the start.
3. Traverse the list to find the node after which insertion is needed.
4. Set the next pointer of the new node to the next node of the current position.
5. Set the prev pointer of the new node to the current node.
6. Update the prev pointer of the next node to point to the new node (if it exists).
7. Update the next pointer of the previous node to point to the new node.

# Python Program to insert a node at a given position

class Node:

    def __init__(self, new_data):

        self.data = new_data

        self.next = None

        self.prev = None

def insert_at_position(head, pos, new_data):

  

    # Create a new node

    new_node = Node(new_data)

    # Insertion at the beginning

    if pos == 1:

        new_node.next = head

        # If the linked list is not empty, set the prev of head to new node

        if head is not None:

            head.prev = new_node

        # Set the new node as the head of the linked list

        head = new_node

        return head

    curr = head

    

    # Traverse the list to find the node before the insertion point

    for _ in range(1, pos - 1):

        if curr is None:

            print("Position is out of bounds.")

            return head

        curr = curr.next

    # If the position is out of bounds

    if curr is None:

        print("Position is out of bounds.")

        return head

    # Set the prev of new node to curr

    new_node.prev = curr

    # Set the next of new node to next of curr

    new_node.next = curr.next

    # Update the next of current node to new node

    curr.next = new_node

    # If the new node is not the last node, update prev of next node to new node

    if new_node.next is not None:

        new_node.next.prev = new_node

    return head

def print_list(head):

    curr = head

    while curr is not None:

        print(curr.data, end=" ")

        curr = curr.next

    print()

if __name__ == "__main__":

  

    # Create a hardcoded doubly linked list:

    # 1 <-> 2 <-> 4

    head = Node(1)

    head.next = Node(2)

    head.next.prev = head

    head.next.next = Node(4)

    head.next.next.prev = head.next

    # Print the original list

    print("Original Linked List: ", end="")

    print_list(head)

    # Insert new node with data 3 at position 3

    print("Inserting Node with data 3 at position 3: ", end="")

    data = 3

    pos = 3

    head = insert_at_position(head, pos, data)

    # Print the updated list

    print_list(head)

4. Deletion in a Doubly Linked List

1. Deletion at the Beginning

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

2. Deletion at the End

3. Deletion at a Specific Position

=======================================================

Circular Linked List

🔁 What is a Circular Linked List?

A Circular Linked List is a variation of a linked list in which the last node points back to the first node, forming a closed loop.

• There is no NULL at the end.

• Traversal can start at any node and continue indefinitely.

• Can be singly or doubly circular.

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.

Representation of Circular Singly Linked List

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.

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

2. Insertion at the beginning in circular linked list

Step-by-step approach:

• Create a new node with the given value.
• Check Empty List (last == nullptr):
  • Make newNode->next point to itself.
• Insert at Beginning:
  • Set newNode->next to last->next.
  • Update last->next to newNode.

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

# Function to insert a node at the beginning of the circular linked list

def insert_at_beginning(last, value):

    new_node = Node(value)

    # If the list is empty, make the new node point to itself and set it as last

    if last is None:

        new_node.next = new_node

        return new_node

    # Insert the new node at the beginning

    new_node.next = last.next

    last.next = new_node

    return last

# Function to print the circular linked list

def print_list(last):

    if last is None:

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

# Create circular linked list: 2, 3, 4

first = Node(2)

first.next = Node(3)

first.next.next = Node(4)

last = first.next.next

last.next = first

print("Original list: ", end="")

print_list(last)

# Insert 5 at the beginning

last = insert_at_beginning(last, 5)

print("List after inserting 5 at the beginning: ", end="")

print_list(last)

3. Insertion at the end in circular linked list

class Node:

    def __init__(self, value):

        self.data = value

        self.next = None

# Function to insert a node at the end of a circular linked list

def insert_end(tail, value):

    new_node = Node(value)

    if tail is None:

        # If the list is empty, initialize

        # it with the new node

        tail = new_node

        new_node.next = new_node

    else:

        # Insert new node after the current tail

        # and update the tail pointer

        new_node.next = tail.next

        tail.next = new_node

        tail = new_node

    return tail

# Function to print the circular linked list

def print_list(last):

    if last is None:

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

if __name__ == "__main__":

    # Create circular linked list: 2, 3, 4

    first = Node(2)

    first.next = Node(3)

    first.next.next = Node(4)

    last = first.next.next

    last.next = first

    print("Original list: ", end="")

    print_list(last)

    # Insert elements at the end of the circular linked list

    last = insert_end(last, 5)

    last = insert_end(last, 6)

    print("List after inserting 5 and 6: ", end="")

    print_list(last)

4. Insertion at specific position in circular linked list

class Node:

    def __init__(self, value):

        self.data = value

        self.next = None

# Function to insert a node at a specific position in a circular linked list

def insertAtPosition(last, data, pos):

    if last is None:

        # If the list is empty

        if pos != 1:

            print("Invalid position!")

            return last

        # Create a new node and make it point to itself

        new_node = Node(data)

        last = new_node

        last.next = last

        return last

    # Create a new node with the given data

    new_node = Node(data)

    # curr will point to head initially

    curr = last.next

    if pos == 1:

        # Insert at the beginning

        new_node.next = curr

        last.next = new_node

        return last

    # Traverse the list to find the insertion point

    for i in range(1, pos - 1):

        curr = curr.next

        # If position is out of bounds

        if curr == last.next:

            print("Invalid position!")

            return last

    # Insert the new node at the desired position

    new_node.next = curr.next

    curr.next = new_node

    # Update last if the new node is inserted at the end

    if curr == last:

        last = new_node

    return last

# Function to print the circular linked list

def print_list(last):

    if last is None:

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

if __name__ == "__main__":

    # Create circular linked list: 2, 3, 4

    first = Node(2)

    first.next = Node(3)

    first.next.next = Node(4)

    last = first.next.next

    last.next = first

    print("Original list: ", end="")

    print_list(last)

    # Insert elements at specific positions

    data = 5

    pos = 2

    last = insertAtPosition(last, data, pos)

    print("List after insertions: ", end="")

    print_list(last)

Deletion from a Circular Linked List

1. Delete the first node in circular linked list

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

def deleteFirstNode(last):

    if last is None:

        # If the list is empty

        print("List is empty")

        return None

    head = last.next

    if head == last:

        # If there is only one node in the list

        last = None

    else:

        # More than one node in the list

        last.next = head.next

    return last

def print_list(last):

    if last is None:

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

# Create circular linked list: 2, 3, 4

first = Node(2)

first.next = Node(3)

first.next.next = Node(4)

last = first.next.next

last.next = first

print("Original list: ", end="")

print_list(last)

# Delete the first node

last = deleteFirstNode(last)

print("List after deleting first node: ", end="")

print_list(last)

2. Delete a specific node in circular linked list

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

def deleteSpecificNode(last, key):

    if last is None:

        # If the list is empty

        print("List is empty, nothing to delete.")

        return None

    curr = last.next

    prev = last

    # If the node to be deleted is the only node in the list

    if curr == last and curr.data == key:

        last = None

        return last

    # If the node to be deleted is the first node

    if curr.data == key:

        last.next = curr.next

        return last

    # Traverse the list to find the node to be deleted

    while curr != last and curr.data != key:

        prev = curr

        curr = curr.next

    # If the node to be deleted is found

    if curr.data == key:

        prev.next = curr.next

        if curr == last:

            last = prev

    else:

        # If the node to be deleted is not found

        print(f"Node with data {key} not found.")

    return last

def printList(last):

    if last is None:

        print("List is Empty")

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

# Create circular linked list: 2, 3, 4

first = Node(2)

first.next = Node(3)

first.next.next = Node(4)

last = first.next.next

last.next = first

print("Original list: ", end="")

printList(last)

# Delete a specific node

key = 3

last = deleteSpecificNode(last, key)

print(f"List after deleting node {key}: ", end="")

printList(last)

3. Deletion at the end of Circular linked list

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

def deleteLastNode(last):

    if last is None:

        # If the list is empty

        print("List is empty, nothing to delete.")

        return None

    head = last.next

    # If there is only one node in the list

    if head == last:

        last = None

        return last

    # Traverse the list to find the second last node

    curr = head

    while curr.next != last:

        curr = curr.next

    # Update the second last node's next pointer to point to head

    curr.next = head

    last = curr

    return last

def printList(last):

    if last is None:

        return

    head = last.next

    while True:

        print(head.data, end=" ")

        head = head.next

        if head == last.next:

            break

    print()

# Create circular linked list: 2, 3, 4

first = Node(2)

first.next = Node(3)

first.next.next = Node(4)

last = first.next.next

last.next = first

print("Original list: ", end="")

printList(last)

# Delete the last node

last = deleteLastNode(last)

print("List after deleting last node: ", end="")

printList(last)

Searching in Circular Linked list

Approach: The approach to find an element in Circular Linked List can be visualized as follows:

1. Keep a pointer to the head of the Circular Linked List. This will help us to determine if the Linked List has been traversed already.
2. Now traverse the Linked List one by one and check if the element is present or not.
3. If the element is present, return true.
4. Now if the element is not present and the traversal pointer reaches the head again, it means the element is not present in the CLL. Therefore return false.

# Python  program to search for an element in a circular

# linked list

class Search:

    class Node:

        def __init__(self, data):

            self.data = data

            self.next = None

    def __init__(self):

        self.head = None

        self.tempo = None

    # Function to add new nodes at the end of the list

    def addNode(self, data):

        new1 = Search.Node(data)

        # If linked list is empty

        if self.head is None:

            self.head = new1

        else:

            self.tempo.next = new1

        self.tempo = new1

        # last node points to the first node

        self.tempo.next = self.head

    def find(self, key):

        # temp will traverse the circular linked list for searching the element

        temp = self.head

        # flag used to check if the element is found or not

        f = 0

        if self.head is None:

            print("List is empty")

        else:

            while True:

                if temp.data == key:

                    print(key, " Found")

                    f = 1

                    break

                temp = temp.next

                if temp == self.head:

                    break

            if f == 0:

                print(key, " Not Found")

# Driver code

if __name__ == "__main__":

    s = Search()

    # Adds data to the list

    s.addNode(5)

    s.addNode(4)

    s.addNode(3)

    s.addNode(2)

    # Search for node 2 in the list

    key = 2

    s.find(key)

    # Search for node 6 in the list

    key = 6

    s.find(key)

# This code is contributed by Susobhan Akhuli

=======================================================