Linked List

Theory

Linked List Representation

1. Singly Linked List (Node Class)

Singly Linked List 1

    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)

Singly Linked List 2

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)

Doubly Linked List 1

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)

Doubly Linked List 2

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

Solution to All Linked List solutions Github

Easy Problems

1. Inserting a node in LinkedList
2. Deleting a node in LinkedList
   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]
2. Reverse a LinkedList [Iterative]
3. Reverse a LL [Recursive]
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
2. Rotate a LL
3. Flattening of LL
4. Clone a Linked List with random and next pointer