Linked List Interview Questions

📘 Basic Concepts

  1. What is a linked list?
    A linear data structure where elements are linked using pointers, allowing dynamic memory allocation.
  2. How does a linked list differ from an array?
    Arrays have fixed size and contiguous memory, while linked lists are dynamic and non-contiguous.
  3. What are the main components of a linked list node?
    Data field and a pointer/reference to the next node.
  4. What is the time complexity of accessing an element in a linked list?
    O(n) linear time, as you must traverse from the head.
  5. What is a doubly linked list?
    A list where each node contains pointers to both next and previous nodes.

📗 Common Operations

  1. How would you insert a node at the beginning?
    Create new node, point its next to current head, then update head pointer.
  2. What's the process to delete the first node?
    Store head node temporarily, move head to next node, then free the temporary node.
  3. How do you traverse a linked list?
    Start at head, follow next pointers until reaching NULL.
  4. What's the efficient way to find the middle element?
    Use fast and slow pointers (Floyd's algorithm).
  5. How would you reverse a linked list?
    Iterate through the list, reversing pointers as you go.

📕 Advanced Topics

  1. How do you detect a cycle in a linked list?
    Use Floyd's cycle-finding algorithm with fast and slow pointers.
  2. What's the method to find the intersection of two lists?
    Traverse both lists and compare node addresses.
  3. How would you merge two sorted linked lists?
    Compare nodes and link them in order using a dummy node.
  4. What's an efficient way to remove Nth node from the end?
    Use two pointers with N nodes apart, then remove when first reaches end.
  5. How do you check if a linked list is a palindrome?
    Find middle, reverse second half, then compare both halves.

📔 Memory Management

  1. How do you properly free a linked list?
    Traverse the list while keeping track of next node before freeing current.
  2. What is a memory leak in linked lists?
    When nodes are removed but not freed, causing unreachable memory.
  3. What's the difference between shallow and deep copy?
    Shallow copies reference the same nodes, deep copies create new identical nodes.

📓 Problem Solving

  1. When would you use a dummy node?
    To simplify edge cases when modifying list head.
  2. What are common linked list pitfalls?
    Null pointer exceptions, incorrect pointer updates, and memory leaks.