Top 10 DSA Questions on Linked Lists and Arrays for Interviews

Why System Design Interviews Are Challenging

01/02/2025

System Design Interview Questions in 2025

Our Top Selling Courses

Preparing for software development interviews? Mastering Data Structures and Algorithms (DSA) is essential, especially when it comes to topics like Linked Lists and Arrays. These are some of the most frequently asked questions during interviews, and understanding them can give you a significant edge. Whether you’re just starting or looking to sharpen your skills, we’ve compiled a list of the top 10 DSA questions you need to focus on for your upcoming interviews. As you dive into this crucial preparation, don’t miss out on our free course and get the latest course updates by signing up here: Free Course & Updates. Let’s get started on your path to interview success!

What is the Purpose of a Linked List?

While arrays are used to store linear data, they come with several limitations:

Fixed Size: The size of an array is determined at the time of its creation. This means you must know the maximum number of elements ahead of time. This can lead to wasted memory if the array isn’t filled to capacity.
Inflexibility: The memory in an array is allocated all at once, which may lead to inefficient use of space.
Costly Insertions and Deletions: In arrays, adding or removing elements is expensive since you may need to move elements to accommodate the new data.

On the other hand, a Linked List overcomes these challenges by offering a dynamic size. It allocates memory only as needed, ensuring there’s no wasted space. It also simplifies the process of inserting and deleting elements, making it an ideal choice for certain use cases.

Advantages of Linked Lists

Dynamic Size: Linked lists can grow or shrink in size during runtime, eliminating the need for pre-allocated space.
Efficient Insertions and Deletions: Linked lists make adding and removing elements much simpler, as only the pointers need to be updated.
No Memory Wastage: As memory is allocated as needed, there’s no unused or wasted memory.
Building Block for Other Structures: Linked lists are often used to build other data structures such as stacks and queues.

Recommended Topic: Top 10 Frontend Design Questions

Disadvantages of Linked Lists

Higher Memory Consumption: Linked lists consume more memory than arrays due to the additional storage required for pointers.
Slower Traversal: Unlike arrays, linked lists do not allow direct access to an element. You must traverse the list from the head node to reach any specific node, making them slower in some cases.
No Reverse Traversal (in Singly Linked Lists): In a singly linked list, reverse traversal isn’t possible. However, doubly linked lists overcome this by maintaining pointers to both the next and previous nodes, which increases memory usage.
Lack of Random Access: Due to dynamic memory allocation, accessing a specific element in a linked list is slower compared to arrays.

Representation of a Linked List

A linked list is represented using a pointer to the first node. The first node is called the head. If the list is empty, the head points to NULL.

Each node consists of two parts:

Data: The value or data held by the node.
Next Pointer: A pointer/reference to the next node in the list.

For example, in C, a node can be represented as:

struct Node {

int data;

struct Node* next;

};

In Java or C#, you can represent a linked list using classes, where the node itself can be a separate class, and the linked list class contains a reference to the node class.

Also Read: Top 15 DSA Questions on Arrays & Strings

Brief History of Linked Lists

Linked lists were first created by Allen Newell, Cliff Shaw, and Herbert A. Simon of RAND Corporation in the mid-1950s as part of their Information Processing Language (IPL). They used IPL to create early artificial intelligence programs like the Logic Theory Machine and the General Problem Solver. Linked lists were also advocated by Hans Peter Luhn in 1953 for applications such as chained hash tables.

2. Sort Linked List Based on Absolute Values

To sort the linked list based on actual values in O(n) time, use an efficient swapping mechanism that ensures that negative numbers are moved correctly.

Implementation

				
					void sortList(Node** head) {
   Node* previous = *head;
   Node* current = (*head)->next;
   
   while (current != NULL) {
       if (current->value < previous->value) {
           // Move current node to the front
       }
       previous = current;
       current = current->next;
   }
}

3. Sum of Last N Nodes in a Linked List

To find the sum of the last n nodes in a single traversal, use two pointers to keep track of the last n elements efficiently.

Implementation:

				
					int getSum(Node* head, int n) {
   int sum1 = 0, sum2 = 0;
   Node* ptr1 = head, *ptr2 = head;
   
   for (int i = 0; i < n; i++) {
       sum1 += ptr1->value;
       ptr1 = ptr1->next;
   }
   
   while (ptr1 != NULL) {
       sum1 += ptr1->value;
       sum2 += ptr2->value;
       ptr1 = ptr1->next;
       ptr2 = ptr2->next;
   }

   return (sum1 - sum2);
}

Time Complexity: O(n)
Space Complexity: O(1)

4. Find the Middle Element of a Linked List

To find the middle element in a linked list with only one traversal, use a fast and slow pointer approach. The fast pointer moves two steps at a time, while the slow pointer moves one step. When the fast pointer reaches the end, the slow pointer will be at the middle.

Implementation:

				
					Node* getMiddle(Node *head) {
     Node *slow = head, *fast = head;
     while (fast != NULL && fast->next != NULL) {
         fast = fast->next->next;
         slow = slow->next;
     }
     return slow;
}

Time Complexity: O(n)
Space Complexity: O(1)

5. Removing Intermediate Points in a Linked List of Coordinates

Given a linked list of coordinates where neighboring points form either a vertical or horizontal line, the task is to remove intermediate points between the starting and ending points of a horizontal or vertical line.

Approach:

Track the current, next, and the node after that.
Delete nodes when the current node and next-next node share the same x or y value.
Handle pointer shifts and check for NULL values as part of the procedure.

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Implementation:

				
					void deleteNode(Node *head, Node *t) {
    head->next = t->next;
    t->next = NULL;
    free(t);
}

Node* deleteMiddleNodes(Node *head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL)
        return head;

    Node* t = head->next;
    Node *tt = t->next;

    if (t->y == head->y) {
        while (tt != NULL && t->y == tt->y) {
            deleteNode(head, t);
            t = tt;
            tt = tt->next;
        }
    } else if (t->x == head->x) {
        while (tt != NULL && t->x == tt->x) {
            deleteNode(head, t);
            t = tt;
            tt = tt->next;
        }
    } else {
        cout << "Given linked list is not valid";
        return NULL;
    }

    deleteMiddleNodes(head->next);
    return head;
}

6. Constructing a Doubly Linked List from a Ternary Tree

A ternary tree, with left, middle, and right child pointers, can be converted into a doubly linked list using a preorder traversal. Each node’s left pointer becomes the previous pointer in the DLL, and the right pointer becomes the next pointer.

Implementation:

				
					void push(Node** tail_reference, Node* n) {
    if (*tail_reference == NULL) {
        *tail_reference = n;
        n->left = NULL;
        n->middle = NULL;
        n->right = NULL;
        return;
    }

    (*tail_reference)->right = n;
    n->right = NULL;
    n->middle = NULL;
    n->left = (*tail_reference);
    (*tail_reference) = n;
}

Node* ternaryTreeToList(Node** head_reference, Node* root) {
    if (!root) return NULL;

    static Node* tail = NULL;

    if (*head_reference == NULL)
        *head_reference = root;

    push(&tail, root);

    ternaryTreeToList(head_reference, root->left);
    ternaryTreeToList(head_reference, root->middle);
    ternaryTreeToList(head_reference, root->right);
}

Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

7. Finding Pairs in a Sorted Doubly Linked List

To find pairs in a sorted doubly linked list that sum up to a given value val, two pointers can be used—one at the head and the other at the tail. Based on the sum, we either move the head pointer forward or the tail pointer backward.

Implementation:

				
					vector<pair<int, int>> sumPair(Node* head, int val) {
    Node* num1 = head;
    Node* num2 = head;
    while (num2->next != NULL) num2 = num2->next;
    
    vector<pair<int, int>> ans;
    
    while (num1 != num2 && num2->next != num1) {
        if ((num1->value + num2->value) == val) {
            ans.push_back(make_pair(num1->value, num2->value));
            num1 = num1->next;
            num2 = num2->prev;
        } else {
            if ((num1->value + num2->value) > val)
                num2 = num2->prev;
            else
                num1 = num1->next;
        }
    }

    return ans;
}

Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

8. Converting a 2-D Matrix to a Linked List

For a 2-D matrix, each node is created for every element, and the right and down nodes are recursively allocated.

Implementation:

				
					Node* construct(int A[][3], int m, int n, int i, int j) {
    if (i > n - 1 || j > m - 1)
        return NULL;

    Node* t = new Node();
    t->value = A[i][j];
    t->right = construct(A, m, n, i, j + 1);
    t->down = construct(A, m, n, i + 1, j);
    return t;
}

void printData(Node* head) {
    Node* d;
    Node* r;

    for (d = head; d != NULL; d = d->down) {
        for (r = d; r != NULL; r = r->right) {
            cout << r->value << " ";
        }
        cout << endl;
    }
}

Complexity:
Time Complexity: O(m * n)
Space Complexity: O(1) (ignoring space for the result)

9. Extracting Leaves from a Binary Tree into a Doubly Linked List

Extract all leaves from a binary tree and insert them into a doubly linked list. The left pointer of the tree node becomes the previous pointer in the DLL, and the right pointer becomes the next pointer.

Implementation:

				
					Node* extractLeaf(Node** head_reference, Node* root) {
    if (!root) return NULL;

    if (root->right == NULL && root->left == NULL) {
        root->right = *head_reference;

        if (*head_reference) 
            (*head_reference)->left = root;

        *head_reference = root;
        return NULL;
    }

    root->right = extractLeaf(&head_reference, root->right);
    root->left = extractLeaf(&head_reference, root->left);
    
    return root;
}

Complexity:
Time Complexity: O(n)
Space Complexity: O(1) (ignoring recursion stack)

10. Deleting Odd Positioned Nodes in a Circular Linked List

For a circular linked list, the task is to delete all odd-positioned nodes. The approach uses a count variable to keep track of the node’s position and deletes nodes at odd positions.

Implementation:

				
					void DeleteAllOddNodes(Node** head_reference, int l) {
    int cnt = 0;
    Node* prev = *head_reference, *next = *head_reference;

    if (*head_reference == NULL) return;

    if (l == 1) {
        *head_reference = NULL;
        return;
    }

    while (l > 0) {
        if (cnt == 0) {
            Node* t1 = *head_reference, *t2 = *head_reference;
            if (t1->next == t1) {
                *head_reference = NULL;
            }
            while(t1->next != *head_reference) {
                t1 = t1->next;
                t2 = t1->next;
            }
            t1->next = t2->next;
            *head_reference = t1->next;
            free(t2);
        }
    }
}

FAQs:

1. What is the importance of mastering DSA for interviews?

Data Structures and Algorithms (DSA) form the backbone of technical interviews. They test problem-solving and coding efficiency, and mastering them is crucial for clearing interviews in top tech companies. For a deeper dive into DSA, check out our course offerings here.

2. How can I improve my skills in Linked Lists and Arrays?

Practice is key! By solving various problems on Linked Lists and Arrays, you’ll get better at recognizing patterns and optimizing solutions. We offer specialized courses on DSA, including Linked Lists and Arrays topics, to help you excel. Explore them here.

3. Can I learn both DSA and Web Development together?

Absolutely! Our combined course covering DSA and Web Development ensures that you get a well-rounded knowledge base for both backend algorithms and front-end development. Find more details here.

4. Is there a course for mastering System Design along with DSA?

Yes, we offer a comprehensive course that covers both DSA and System Design. This will help you ace both coding and design interviews. Get started with our Master DSA & Web Development course here.

5. Can I specialize in Data Science with DSA knowledge?

Definitely! Understanding DSA can greatly enhance your data science skills, as it helps in efficiently manipulating and analyzing large datasets. Check out our specialized Data Science

Accelerate your Path to a Product based Career

Boost your career or get hired at top product-based companies by joining our expertly crafted courses. Gain practical skills and real-world knowledge to help you succeed.