Linked List Interview Questions and Answers

This section covers frequently asked linked list interview questions, focusing on different types of linked lists, their implementation, and common operations.

What is a Linked List?

A linked list is a linear data structure where elements (nodes) are not stored in contiguous memory locations. Each node contains data and a pointer (or link) to the next node in the sequence. The last node's pointer is typically NULL. Linked lists are flexible and are useful when the size of the data is unknown or changes frequently.

Graphical Representation of a Linked List

A linked list is depicted as a sequence of nodes. Each node contains data and a pointer to the next node. The last node's pointer points to NULL. The first node is accessed via a "head" pointer.

Types of Linked Lists

• Singly Linked List: Each node points to the next node.
• Doubly Linked List: Each node points to both the next and previous nodes.
• Multiply Linked List: Each node has multiple pointers, linking to the same data in different orders.
• Circular Linked List: The last node points back to the first node.

Singly Linked List

A singly linked list is a linear data structure where each node points to the next node in the sequence. The last node's pointer is NULL. Basic operations include insertion, deletion, and traversal.

Doubly Linked List

In a doubly linked list, each node contains pointers to both the next and previous nodes, allowing for traversal in both directions. XOR-linking is a technique to implement a doubly linked list using only one pointer per node (though it's less commonly used).

Multiply Linked List

A multiply linked list has nodes with more than one pointer. Each pointer can link to the same set of data, but organized differently (e.g., sorted by different fields).

Circular Linked List

In a circular linked list, the last node's pointer points back to the first node, creating a circular structure. A circular doubly linked list also has the first node point to the last.

Pointers in a Simple Linked List

• A head pointer points to the first node.
• A tail pointer points to the last node.
• Each node has a next pointer pointing to the subsequent node.

Representing a Linked List Node

A linked list node is often represented as a structure containing data and a pointer to the next node (and a previous node in a doubly linked list).

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Memory Allocation for Linked Lists

Linked lists use dynamic memory allocation (allocating memory as needed during runtime).

Traversal in Linked Lists

Traversal means iterating through each node in the list, processing the data in each node.

Linked List vs. Linear Array

Dummy Header

A dummy header is a node at the beginning of the list that doesn't contain actual data. It simplifies certain operations, like insertion at the beginning.

Applications of Linked Lists

• Implementing stacks and queues.
• Representing graphs and trees.
• Implementing hash tables.

Inserting a Node at the Beginning

To insert a node at the beginning of a singly linked list:

1. Create a new node.
2. Set the new node's next pointer to the current head.
3. Set the head pointer to point to the new node.

newNode->next = head;
head = newNode;

Applications Using Linked Lists

• Stacks
• Queues
• Binary trees
• Graphs

Singly vs. Doubly Linked Lists

A singly linked list allows traversal in one direction. A doubly linked list allows traversal in both directions.

Main Advantage of Linked Lists

Linked lists are dynamic; their size isn't fixed at compile time.

Adding an Item to the Beginning of a List

1. Create a new node.
2. Set its next pointer to the current head.
3. Update the head pointer to point to the new node.

Inserting a Node at the End

If you have a tail pointer, it's simple. Otherwise, you traverse to the end, create a new node, and update the last node's pointer to point to the new node.

// ... traverse to the last node ...
lastNode->next = newNode;

Inserting a Node at a Specific Position

1. Create a new node.
2. Traverse to the desired position.
3. Adjust pointers to insert the new node.

Deleting the First Node

To remove the first node from a singly linked list:

1. Store the address of the first node in a temporary variable.
2. Make the head pointer point to the second node.
3. Deallocate the memory used by the original first node.

Deleting a Specific Node

Deleting a node other than the first involves:

1. Traversing the list to find the node *before* the one to be deleted.
2. Updating the next pointer of the previous node to skip over the node being deleted.
3. Deallocating the memory for the deleted node.

Reversing a Singly Linked List

Reversing a singly linked list requires iterating through the list and changing the next pointers to reverse the direction of links. The last node becomes the new head.

One approach is to use iterative method, where we change the next pointer at every node. Another approach is a recursive method which is generally more elegant and often easier to understand but may use more stack space.

Detecting and Removing Loops (Floyd's Cycle-Finding Algorithm)

To detect a loop, use two pointers (slow and fast):

• The slow pointer moves one node at a time.
• The fast pointer moves two nodes at a time.

If a loop exists, the fast pointer will eventually catch up to the slow pointer. Once the loop is detected, you can find the starting point of the loop to remove it.

Singly vs. Doubly Linked Lists for Traversal

Doubly linked lists use more memory but allow for efficient traversal in both directions, making them better suited for certain traversal algorithms than singly linked lists.

Free Node Location During Insertion

When inserting a node, the memory for the new node comes from the system's free memory (or a free list if you are managing memory manually).

Null Pointer in Grounded Header Lists

In a grounded header list, the last node's next pointer is NULL.

Traversing a Linked List in Java

You can traverse a Java linked list using:

• Traditional loops (for, while).
• Enhanced for loop (Java 5 and later).
• Iterators.
• Streams (Java 8 and later).

Calculating Linked List Length in Java

Iterate through the list, incrementing a counter for each node until you reach the end (next is null).

Displaying a Singly Linked List

A singly linked list is a data structure where each node points to the next node in the sequence. To display the elements of a singly linked list, we traverse it from the head node to the tail, printing each element along the way.

Code Example

Below is a Java example that demonstrates how to display the elements of a singly linked list:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListDisplay {
    public static void displayList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        head.next = new ListNode(20);
        head.next.next = new ListNode(30);

        System.out.print("Linked List: ");
        displayList(head);
    }
}

Linked List: 10 -> 20 -> 30

Key Points

• Traversal: Start at the head node and follow the next references until reaching a null pointer.
• Time Complexity: O(n), where n is the number of nodes in the linked list.
• Space Complexity: O(1), as no additional data structures are used.

This approach ensures that all nodes in the linked list are displayed in sequence from head to tail.

Drawbacks of Linked Lists

• No random access (you must traverse sequentially).
• Higher memory overhead due to pointers.
• Slower indexed access (O(n) time complexity).
• Poor memory locality (nodes are scattered in memory).

Linked List Package in Java

The java.util package contains the LinkedList class.

Interfaces Implemented by LinkedList

• List
• Deque
• Queue
• Cloneable
• Serializable
• Iterable
• Collection

Summing Two Linked Lists Using Stacks

When two numbers are represented as linked lists, where each node contains a single digit, summing them can be a challenge due to differing lengths and carry values. Using stacks simplifies the process by allowing us to sum digits from the least significant to the most significant, handling carries effectively.

Algorithm Explanation

Here is a step-by-step breakdown of the algorithm:

1. Push the digits of both linked lists onto two separate stacks.
2. Initialize a variable for the carry and a dummy node to build the result linked list.
3. While either stack is not empty or there is a carry:
   • Pop the top elements from each stack (if available) and add them along with the carry.
   • Compute the new digit and update the carry.
   • Create a new node for the computed digit and add it to the front of the result list.
4. Return the result linked list.

Java Implementation

import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListSum {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        
        ListNode result = null;
        int carry = 0;
        
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int sum = carry;
            if (!stack1.isEmpty()) sum += stack1.pop();
            if (!stack2.isEmpty()) sum += stack2.pop();
            
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = result;
            result = newNode;
        }
        
        return result;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(9);
        l1.next = new ListNode(5);
        l1.next.next = new ListNode(7);

        ListNode l2 = new ListNode(4);
        l2.next = new ListNode(8);

        ListNode result = addTwoNumbers(l1, l2);
        System.out.print("Result: ");
        while (result != null) {
            System.out.print(result.val);
            if (result.next != null) System.out.print(" -> ");
            result = result.next;
        }
    }
}

Result: 1 -> 0 -> 4 -> 5

Key Points

• Time Complexity: O(n + m), where n and m are the lengths of the two linked lists.
• Space Complexity: O(n + m), due to the use of stacks.

By leveraging stacks, this algorithm simplifies handling carry propagation and different list lengths, ensuring an elegant and efficient solution.