Introduction

A linked list is a linear data structure where elements (nodes) are connected by pointers. Unlike arrays, linked lists allow dynamic memory allocation and efficient insertion/deletion operations.

Types of Linked Lists

1. Singly Linked List

  • Each node has a value and a pointer to the next node.
  • Efficient for forward traversal.

2. Doubly Linked List

  • Each node has a value, a pointer to the next node, and a pointer to the previous node.
  • Supports forward and backward traversal.

3. Circular Linked List

  • The last node points back to the head, forming a cycle.

Common Techniques

1. Traversal

Iterate through the linked list using a while loop until you reach the end.

# Example: Traverse a Singly Linked List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def traverse(head):
    current = head
    while current:
        print(current.val)
        current = current.next

2. Detect Cycle (Floyd’s Cycle Detection Algorithm)

Use two pointers (slow and fast) to detect cycles in a linked list.

# Example: Detect Cycle
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

3. Reverse a Linked List

Reverse a singly linked list using an iterative approach.

# Example: Reverse a Singly Linked List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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