> ## Documentation Index
> Fetch the complete documentation index at: https://akshanshgusain.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Linked List

# Theory

## Linked List Representation

### 1. Singly Linked List (Node Class)

```python Singly Linked List 1 expandable theme={null}
    class ListNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def print_ll(head: ListNode):
    while head is not None:
        print(head.data, end=" ")
        head = head.next
    print()


def insert_at_start(head: ListNode, data) -> ListNode:
    temp = ListNode(data, head)
    return temp


def insert_at_end(head: ListNode, data) -> ListNode:
    new_node = ListNode(data)
    if head is None:
        return new_node
    current = head
    while current.next is not None:
        current = current.next
    current.next = new_node
    return new_node


def delete_tail(head: ListNode):
    # Check if the linked list is empty or has only one node
    if head is None or head.next is None:
        return None

    # Create a temporary pointer for traversal
    temp = head

    # Traverse the list until the second-to-last node
    while temp.next.next is not None:
        temp = temp.next

    # Nullify the connection from the second-to-last node to delete the last node
    temp.next = None

    # Return the updated head of the linked list
    return head


def delete_front(head: ListNode):
    # Check if the linked list is empty or has only one node
    if head is None:
        return None
    head = head.next


if __name__ == "__main__":
    # Sample array and value for insertion
    arr = [12, 8, 5, 7]
    val = 100

    # Creating a linked list with initial elements from the array
    head = ListNode(12)
    head.next = ListNode(8)
    head.next.next = ListNode(5)
    head.next.next.next = ListNode(7)
    # Inserting a new node at the head of the linked list
    head = insert_at_start(head, val)

    # Printing the linked list
    # print_ll(head)

    insert_at_end(head, 10000)
    print_ll(head)
    print()
    delete_tail(head)
    print_ll(head)

```

### 2. Singly Linked List (Linked List Class)

```python Singly Linked List 2 expandable theme={null}
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class SinglyLinkedList:
    def __init__(self):
        self.head = None  # Initialize an empty list with no head

    def insert_at_start(self, data) -> Node:
        temp = Node(data, self.head)
        return temp

    def insert_at_end(self, data):
        """Insert a new node with the given data at the end of the list."""
        new_node = Node(data)
        if not self.head:  # If the list is empty, make the new node the head
            self.head = new_node
            return
        current = self.head
        while current.next:  # Traverse to the last node
            current = current.next
        current.next = new_node  # Point the last node to the new node

    def delete_from_end(self):
        if self.head is None or self.head.next is None:
            self.head = None
        current = self.head
        while current.next.next is not None:
            current = current.next
        current.next = None
        return self.head

    def delete_from_start(self):
        if self.head is None:
            return None
        self.head = self.head.next

    def length(self) -> int:
        count = 0
        current = self.head
        while current is not None:
            current = current.next
            count += 1
        return count

    def print(self):
        """Print all the nodes in the linked list."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


if __name__ == "__main__":
    ll = SinglyLinkedList()
    ll.insert_at_end(1)
    ll.insert_at_end(2)
    ll.insert_at_end(3)
    ll.print()  # Output: 1 -> 2 -> 3 -> None
    print(ll.length())
    ll.delete_from_end()
    ll.print()
    print(ll.length())

```

### 3. Doubly Linked List (DLLNode Class)

```python Doubly Linked List 1 expandable theme={null}
class DLLNode:
    def __init__(self, data, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev

def print_dll_forward(head: DLLNode):
    while head is not None:
        print(head.data, end=" ")
        last = head
        head = head.next
    print()
    return last if 'last' in locals() else None

def print_dll_backward(tail: DLLNode):
    while tail is not None:
        print(tail.data, end=" ")
        tail = tail.prev
    print()

def insert_at_start(head: DLLNode, data) -> DLLNode:
    new_node = DLLNode(data, next=head)
    if head:
        head.prev = new_node
    return new_node

def insert_at_end(head: DLLNode, data) -> DLLNode:
    new_node = DLLNode(data)
    if head is None:
        return new_node
    curr = head
    while curr.next is not None:
        curr = curr.next
    curr.next = new_node
    new_node.prev = curr
    return head

def delete_tail(head: DLLNode) -> DLLNode:
    if head is None or head.next is None:
        return None
    curr = head
    while curr.next is not None:
        curr = curr.next
    if curr.prev:
        curr.prev.next = None
    return head

def delete_front(head: DLLNode) -> DLLNode:
    if head is None:
        return None
    new_head = head.next
    if new_head:
        new_head.prev = None
    return new_head

if __name__ == "__main__":
    arr = [12, 8, 5, 7]
    val = 100
    head = DLLNode(12)
    head = insert_at_end(head, 8)
    head = insert_at_end(head, 5)
    head = insert_at_end(head, 7)
    head = insert_at_start(head, val)
    print("Forward:", end=" ")
    tail = print_dll_forward(head)
    print("Backward:", end=" ")
    print_dll_backward(tail)
    head = insert_at_end(head, 10000)
    print("After insert at end:", end=" ")
    tail = print_dll_forward(head)
    head = delete_tail(head)
    print("After delete tail:", end=" ")
    tail = print_dll_forward(head)
    head = delete_front(head)
    print("After delete front:", end=" ")
    tail = print_dll_forward(head)
```

### 4. Doubly Linked List (DLL Class)

```python Doubly Linked List 2 expandable theme={null}
class Node:
    def __init__(self, data, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev


class DoublyLinkedList:
    def __init__(self):
        self.head = None  # Initialize an empty list

    def insert_at_start(self, data):
        """Insert a new node at the start of the list."""
        new_node = Node(data, next=self.head)
        if self.head:
            self.head.prev = new_node  # Update the previous pointer of the old head
        self.head = new_node  # Update the head to the new node

    def insert_at_end(self, data):
        """Insert a new node at the end of the list."""
        new_node = Node(data)
        if not self.head:  # If the list is empty, make the new node the head
            self.head = new_node
            return
        current = self.head
        while current.next:  # Traverse to the last node
            current = current.next
        current.next = new_node  # Point the last node to the new node
        new_node.prev = current  # Set the previous pointer of the new node

    def delete_from_start(self):
        """Delete the node at the start of the list."""
        if not self.head:  # If the list is empty, do nothing
            return
        if not self.head.next:  # If there's only one node, remove it
            self.head = None
            return
        self.head = self.head.next  # Update the head
        self.head.prev = None  # Remove the reference to the old head

    def delete_from_end(self):
        """Delete the node at the end of the list."""
        if not self.head:  # If the list is empty, do nothing
            return
        if not self.head.next:  # If there's only one node, remove it
            self.head = None
            return
        current = self.head
        while current.next:  # Traverse to the last node
            current = current.next
        current.prev.next = None  # Remove the last node

    def length(self):
        """Return the length of the list."""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

    def print_forward(self):
        """Print all the nodes in the linked list from head to tail."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def print_backward(self):
        """Print all the nodes in the linked list from tail to head."""
        current = self.head
        if not current:
            print("None")
            return
        while current.next:  # Traverse to the last node
            current = current.next
        while current:  # Traverse backward using prev pointers
            print(current.data, end=" -> ")
            current = current.prev
        print("None")


if __name__ == "__main__":
    # Example Usage
    dll = DoublyLinkedList()
    dll.insert_at_start(3)
    dll.insert_at_start(2)
    dll.insert_at_start(1)
    dll.print_forward()  # Output: 1 -> 2 -> 3 -> None
    dll.print_backward()  # Output: 3 -> 2 -> 1 -> None

    dll.insert_at_end(4)
    dll.insert_at_end(5)
    dll.print_forward()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None
    dll.print_backward()  # Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

    dll.delete_from_start()
    dll.print_forward()  # Output: 2 -> 3 -> 4 -> 5 -> None
    dll.delete_from_end()
    dll.print_forward()  # Output: 2 -> 3 -> 4 -> None

```

## Common Operations

ctd.

***

# Problems

<Info>
  Solution to All Linked List solutions [Github](https://github.com/akshanshgusain/data_structures_algorithms_python/tree/master/linked_list)
</Info>

### Easy Problems

1. [Inserting a node in LinkedList]()
2. [Deleting a node in LinkedList](https://leetcode.com/problems/delete-node-in-a-linked-list/description/)\
   2.2. [Deleting a node(front,middle, end) in LinkedList]()
3. [Find the length of the linkedlist]()
4. [Search an element in the LL]()

#### Doubly Linked List

5. [Insert a node in DLL]()
6. [Delete a node in DLL]()
7. [Reverse a DLL]()

### Medium Problems

1. [Middle of a LinkedList \[TortoiseHare Method\]](https://leetcode.com/problems/middle-of-the-linked-list/description/)
2. [Reverse a LinkedList \[Iterative\]](https://leetcode.com/problems/reverse-linked-list/description/)
3. [Reverse a LL \[Recursive\]](https://leetcode.com/problems/reverse-linked-list/description/)
4. [Detect a loop in LL]()
5. [Find the starting point in LL]()
6. [Length of Loop in LL]()
7. [Check if LL is a palindrome or not]()
8. [Segregate odd and even nodes in LL]()
9. [Remove Nth node from the back of the LL]()
10. [Delete the middle node of LL]()
11. [Sort LL]()
12. [Sort a LL of 0's 1's and 2's by changing links]()
13. [Find the intersection point of Y LL]()
14. [Add 1 to a number represented by LL]()
15. [Add 2 numbers in LL]()

#### Doubly Linked List

16. [Delete all occurrences of a key in DLL]()
17. [Find pairs with the given sum in DLL]()
18. [Remove duplicates from sorted DLL]()
19. [Add 2 numbers in a DLL]()

### Hard Problems

1. [Reverse LL in group of given size K](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)
2. [Rotate a LL](https://leetcode.com/problems/rotate-list/)
3. [Flattening of LL]()
4. [Clone a Linked List with random and next pointer](https://leetcode.com/problems/copy-list-with-random-pointer/description/)