Day 5 Python 2024

Sure! Here's a brief overview of Linked Lists in Python to help you prepare for your interview.

Linked Lists Overview

A linked list is a linear data structure where each element is a separate object. Each element (node) of a list comprises two items:

1. Data

2. Reference (or link) to the next node in the sequence.

Types of Linked Lists

1. Singly Linked List: Each node has a single link to the next node.

2. Doubly Linked List: Each node has two links, one to the next node and another to the previous node.

3. Circular Linked List: The last node points back to the first node, forming a circle.

Key Concepts and Operations

1. Node Class:

   • Each node contains data and a reference to the next node.

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

2. Linked List Class:

   • Contains methods to insert, delete, and traverse nodes.

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

        # Insert at the beginning
        def insert_at_beginning(self, data):
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node

        # Insert at the end
        def insert_at_end(self, data):
            new_node = Node(data)
            if not self.head:
                self.head = new_node
                return
            last_node = self.head
            while last_node.next:
                last_node = last_node.next
            last_node.next = new_node

        # Delete a node
        def delete_node(self, key):
            current = self.head
            if current and current.data == key:
                self.head = current.next
                current = None
                return
            prev = None
            while current and current.data != key:
                prev = current
                current = current.next
            if current is None:
                return
            prev.next = current.next
            current = None

        # Traverse the list
        def print_list(self):
            current = self.head
            while current:
                print(current.data, end=" -> ")
                current = current.next
            print("None")

Common Operations

1. Insertion:

   • At the beginning: Updates the head to point to the new node.

   • At the end: Traverses to the end and adds the new node.

2. Deletion:

   • Find the node to delete, update the references to bypass the node.

3. Traversal:

   • Start from the head node and visit each node until reaching the end.

Example Usage

# Create a linked list and perform operations
ll = LinkedList()
ll.insert_at_beginning(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.print_list()  # Output: 1 -> 2 -> 3 -> None

ll.delete_node(2)
ll.print_list()  # Output: 1 -> 3 -> None

Key Points to Remember

• Linked lists are dynamic and can grow and shrink in size.

• They are useful for applications where insertion and deletion are frequent.

• They do not allow random access (unlike arrays), making traversal potentially slower.

This should give you a good starting point for understanding and discussing linked lists in your interview. Good luck!

Understanding Singly, Doubly, and Circular Linked Lists

Singly Linked List

A singly linked list is the simplest type of linked list where each node points to the next node in the sequence. The last node points to None.

Operations:

1. Insertion: At the beginning, end, or at a specific position.

2. Deletion: Remove a node by value or position.

3. Traversal: Visit all the nodes from the head to the end.

Example Implementation:

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

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

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

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def delete_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if current is None:
            return
        prev.next = current.next
        current = None

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

Doubly Linked List

A doubly linked list contains nodes with two references: one to the next node and one to the previous node.

Operations:

1. Insertion: At the beginning, end, or at a specific position.

2. Deletion: Remove a node by value or position.

3. Traversal: Can be done in both directions (forward and backward).

Example Implementation:

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

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

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

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node

    def delete_node(self, key):
        current = self.head
        while current:
            if current.data == key:
                if current.prev:
                    current.prev.next = current.next
                if current.next:
                    current.next.prev = current.prev
                if current == self.head:
                    self.head = current.next
                current = None
                return
            current = current.next

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

Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circle.

Operations:

1. Insertion: At the beginning, end, or at a specific position.

2. Deletion: Remove a node by value or position.

3. Traversal: Start from any node and return to it after traversing the entire list.

Example Implementation:

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

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

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        last_node = self.head
        while last_node.next != self.head:
            last_node = last_node.next
        last_node.next = new_node
        new_node.next = self.head

    def delete_node(self, key):
        if self.head is None:
            return
        current = self.head
        prev = None
        while True:
            if current.data == key:
                if prev:
                    prev.next = current.next
                else:
                    # Handle the case where we need to delete the head node
                    while current.next != self.head:
                        current = current.next
                    current.next = self.head.next
                    self.head = self.head.next
                return
            prev = current
            current = current.next
            if current == self.head:
                break

    def print_list(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print(current.data, end=" (head)\n")

Solving Problems with Linked Lists

1. Reverse a Linked List:

   • Iteratively reverse the pointers of each node.

    def reverse_linked_list(head):
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev

2. Detect a Cycle in a Linked List:

   • Use Floyd’s Cycle-Finding Algorithm (Tortoise and Hare).

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

3. Merge Two Sorted Linked Lists:

   • Merge two sorted linked lists into a single sorted linked list.

    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

4. Find the Middle of a Linked List:

   • Use the slow and fast pointer technique.

    def find_middle(head):
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Practice Problems

• Implement a function to remove duplicates from a sorted linked list.

• Implement a function to add two numbers represented by linked lists.

• Implement a function to check if a linked list is a palindrome.

Understanding these concepts and practicing these problems will help you prepare for your interview.