Linked List Interview Questions & Tips for Senior Engineers

Linked Lists Interview Questions & Tips

By Githire B. Wahome | Last updated: October 5, 2023

What is a Linked List?

A linked list is a data structure consisting of a sequence of nodes, where each node contains a reference to either the next node in the sequence, itself, or the node prior to it. They are designed to be efficient when performing insertions and deletions. The key to their efficiency is the use of pointers to capture the order of the nodes.

Types of Linked Lists

Singly-linked lists: each node has a link to the next node in the list, but not to the previous node.
Doubly linked lists: each node has links to both the next node and the previous node in the list.
Circular linked lists: the last node in the list points to the first node, creating a circular structure.
Self-referential linked lists (self-linked lists): each node contains a pointer or reference to itself.

Common Operations on Linked Lists

Linked List Traversal

Here is some pseudocode for forward and backward traversals of a linked list:

Forward Traversal

# class Node:
#     def __init__(self, data=None, next=None):
#         self.data = data
#         self.next = next

current_node = head
while current_node is not None:
    # Do something with the current node
    current_node = current_node.next

Backward Traversal

current_node = tail
while current_node is not None:
    # Do something with the current node
    current_node = current_node.prev

Insertion Into a Singly Linked List

Create a new node containing the value to be inserted.
Determine the position where the new node will be inserted.
If the insertion position is at the front of the list, set the next in the new node to the current head.
If the insertion position is in the middle, find the node immediately preceding the position and update links accordingly.
For tail insertion, set the link in the preceding node to the new node, pointing its next to None.

Head Insertion

Simply set the new node’s next pointer to the current head.

Tail Insertion

Point the next pointer of the last node to the new node, and point the new node to None.

Deletion from a Singly Linked List

Find the node to be deleted.
Update the preceding node's link to bypass the node to be deleted.
If the node to be deleted is the head or the tail, adjust the head or previous node accordingly.

Head Deletion

Make the new head the next node of the current head.

Tail Deletion

Make the next of the second to last node point to None.

Insertion into Doubly Linked Lists

Insertions into doubly linked lists involve updating both next and previous pointers during insertion.

Deletion from a Doubly Linked List

Deletion is more straightforward as it requires updating both next and previous pointers.

Insertion and Deletions into Circular and Self-Linked Lists

These operations generally resemble the singly and doubly linked lists but handle the circular aspects as necessary.

Linked List implementation strategies

Traditional Implementation (Using Nodes)

The classic way of implementing linked lists involves defining a Node class that contains a data attribute and a next attribute:

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

To create a linked list, we define a LinkedList class:

class LinkedList:
    def __init__(self):
        self.head = None

Array Implementation

Linked lists can be implemented using arrays where each element represents a node:

[(2, 1), (5, 2), (7, 3), (4, None)]

This structure allows for a direct representation of a linked list and can optimize memory locality and access speeds but also has downsides regarding resizing and memory allocation.

Floyd’s Algorithm (Tortoise and Hare)

Floyd's algorithm detects cycles in a linked list using two pointers moving at different speeds. If they meet, a cycle exists, and further traversal can find the starting node of that cycle.

# define a Node class
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# define a function to detect cycles in a linked list
def detect_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Common Linked List interview Questions

EASY

Reverse a Linked List

MEDIUM

HARD