Topic: Linked Lists in Python – Part 1: Introduction and Singly Linked List Basics

---

What is a Linked List?

• A linked list is a linear data structure where each element (called a node) contains:

• The data value.
• A pointer (or reference) to the next node.

• Unlike arrays, linked lists don’t require contiguous memory and can grow dynamically.

---

Why Use Linked Lists?

• Efficient insertions/deletions at the beginning or middle.
• No need for pre-defining size, unlike arrays.
• Used in memory-efficient applications like OS kernels, compilers, and real-time systems.

---

Types of Linked Lists

• Singly Linked List – Each node points to the next.
• Doubly Linked List – Nodes have next and previous pointers.
• Circular Linked List – The last node points back to the head.

---

Basic Structure of a Node

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

---

Building a Singly Linked List

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

---

Traversing the List

def display(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

Usage:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # Output: 10 -> 20 -> 30 -> None

---

Inserting at the Beginning

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

---

Summary

• A singly linked list stores data as a sequence of nodes linked by references.

• Supports dynamic memory usage, fast insertions, and flexible resizing.

• The key is managing node connections safely and efficiently.

---

Exercise

• Implement a method length() that returns the number of nodes in the list.

---

#DataStructures #LinkedList #DSA #Python #CodingBasics

https://t.iss.one/DataScience4

Topic: Linked Lists in Python – Part 2: Insertion, Deletion, and Search Operations

---

Recap from Part 1

• A singly linked list consists of nodes, where each node holds data and a pointer to the next node.

• We've implemented basic append and display functions.

Now we’ll explore insertion at specific positions, deletion, and searching.

---

1. Insert at a Specific Position

def insert_at_position(self, index, data):
    if index < 0:
        raise IndexError("Index cannot be negative")
    
    new_node = Node(data)
    
    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return

    current = self.head
    for _ in range(index - 1):
        if not current:
            raise IndexError("Index out of bounds")
        current = current.next
    
    new_node.next = current.next
    current.next = new_node

---

2. Delete a Node by Value

def delete_by_value(self, value):
    if not self.head:
        return

    if self.head.data == value:
        self.head = self.head.next
        return

    current = self.head
    while current.next and current.next.data != value:
        current = current.next

    if current.next:
        current.next = current.next.next

---

3. Delete a Node by Index

def delete_by_index(self, index):
    if index < 0:
        raise IndexError("Index cannot be negative")

    if not self.head:
        raise IndexError("List is empty")

    if index == 0:
        self.head = self.head.next
        return

    current = self.head
    for _ in range(index - 1):
        if not current.next:
            raise IndexError("Index out of bounds")
        current = current.next

    if current.next:
        current.next = current.next.next

---

4. Search for an Element

def search(self, value):
    current = self.head
    index = 0
    while current:
        if current.data == value:
            return index
        current = current.next
        index += 1
    return -1  # Not found

---

5. Complete Class with All Methods

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data): ...
    def display(self): ...
    def insert_at_position(self, index, data): ...
    def delete_by_value(self, value): ...
    def delete_by_index(self, index): ...
    def search(self, value): ...

*(You can reuse the method definitions above.)*

---

Summary

• You can manipulate linked lists with insertions and deletions at any position.

• Searching through a singly linked list is O(n).

• Always check for edge cases: empty list, index bounds, and duplicates.

---

Exercise

• Write a method reverse() that reverses the linked list in-place and test it on a list of 5+ elements.

---

#DSA #LinkedList #Python #Insertion #Deletion #Search

https://t.iss.one/DataScience4

Topic: Linked Lists in Python – Part 3: Reversing, Detecting Loops, and Middle Node

---

In this part, we’ll explore advanced operations that are frequently asked in coding interviews using singly linked lists.

---

1. Reverse a Linked List (Iterative)

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

• Time Complexity: O(n)
• Space Complexity: O(1)

---

2. Find the Middle of the Linked List

• Use the slow and fast pointer approach.

def find_middle(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data if slow else None

---

3. Detect a Loop in the Linked List

• Use Floyd’s Cycle Detection Algorithm (a.k.a. Tortoise and Hare).

def has_loop(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

---

4. Find the N-th Node from the End

def nth_from_end(self, n):
    first = self.head
    second = self.head

    for _ in range(n):
        if not first:
            return None
        first = first.next

    while first:
        first = first.next
        second = second.next

    return second.data

---

5. Full Example: Testing All Methods

ll = LinkedList()
for value in [10, 20, 30, 40, 50]:
    ll.append(value)

ll.display()
ll.reverse()
ll.display()
print("Middle:", ll.find_middle())
print("Has Loop?", ll.has_loop())
print("3rd from End:", ll.nth_from_end(3))

---

Summary

• Use pointer manipulation for efficient algorithms in linked lists.

• Common techniques:
• Fast/slow pointers
• Reversal by in-place re-linking
• Two-pointer gap approach for nth from end

---

Exercise

• Write a method is_palindrome() that checks if the linked list reads the same forwards and backwards (without converting it to a list or using extra space).

---

#DSA #LinkedList #ReverseList #LoopDetection #TwoPointerTechnique

https://t.iss.one/DataScience4

Topic: Linked Lists in Python – Part 4: Merging, Sorting, and Advanced Interview Problems

---

In this final part of the Linked List series, we’ll tackle more advanced and practical use cases like merging sorted lists, sorting a linked list, and interview-level challenges.

---

1. Merging Two Sorted Linked Lists

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

---

2. Sorting a Linked List (Merge Sort – O(n log n))

def merge_sort(head):
    if not head or not head.next:
        return head

    # Split list
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge_sorted_lists(left, right)

• Attach this to your LinkedList class to sort self.head.

---

3. Removing Duplicates from a Sorted List

def remove_duplicates(self):
    current = self.head
    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

---

4. Intersection Point of Two Linked Lists

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # Can be None or the intersecting node

---

5. Flatten a Multilevel Linked List

Imagine a list where each node has next and child pointers. Recursively flatten:

def flatten(node):
    if not node:
        return None

    next_node = node.next
    if node.child:
        child_tail = flatten(node.child)
        node.next = node.child
        node.child = None
        child_tail.next = flatten(next_node)
        return child_tail if child_tail.next else child_tail
    else:
        node.next = flatten(next_node)
        return node

---

Summary

• You now know how to merge, sort, and deduplicate linked lists.

• Techniques like merge sort, two-pointer traversal, and recursive flattening are essential for mastering linked lists.

• These problems are frequently asked in interviews at top tech companies.

---

Exercise

• Given two unsorted linked lists, write a function that returns a new linked list containing only the elements present in both lists (intersection), without using extra space or sets.

---

#DSA #LinkedList #MergeSort #AdvancedDSA #CodingInterview

https://t.iss.one/DataScience4