Top Linked List data structure interview questions and answers

Linked List Data structure

A linked list is a linear data structure where each element is a separate object. Here is the top (most commonly) asked question in the Java interview. A linked list is one of the most favorite topics during the data structure and algorithms interview process.

We are starting  from basic  :

Here is the code of LinkedList, as you know java JDK already providing a Collection of data structure. So LinkedList class already provided in java.util. Here we share a basic level of knowledge of LinkedList. So start with the program how to create a simple LinkedList, then go to a deep level.

package in.eyehunt.data.struc;

public class LinkedList {
    Node head; // head of list
    // Linked list Node.  This inner class is made 
    // static so that main() can access it
    static class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // Method to print all nodes
    public void printList() {
        Node n = head;
        System.out.print(" head");
        while (n != null) {
            System.out.print(" -> " + n.data);
            n = n.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 5 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.head = new Node(2);
        Node second = new Node(4);
        Node third = new Node(5);
        Node fourth = new Node(2);
        Node fifth = new Node(1);

        linkedList.head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = null;// not needed to assign null
        linkedList.printList();
    }
}

Now, let’s start the Most common and top Linked List data structure interview questions in Java. It’s also an important question for Android app developers.

Question #1. How to Find Length of a Linked List (Iterative and Recursive)

Answer  : Iterative : The Iteration is applied to the set of instructions which we want to get repeatedly executed.

Recursive : Recursion is a process, where statement in a body of function calls the function itself.

Coding is here Find Length of a LinkedList

Question #2. How to Insert a new node in a linked list data structure

Answer : Inserting new node in linked list can do 3 ways.

• At the start of the Linked list
• In the middle of the Linked list
• At the end of the Linked list

Here is all 3 ways to inserting data in linked list with code : Insert a new node in a linked list

Question #3. In given a Linked List,  find the middle of the list and print the number.

Input : -> 4-> 2-> 7-> 9-> 1

Output : 7

#Single pointer approach

In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up-to that node.

#Using 2 pointers

With 2 pointers to traverse the list ,we can find the middle of list with only one scan on the Linked List.

• pointer1 travels one node at a time
• pointe2 travels two nodes a time.

Thus, when pointer2 reaches the end of the Linked List, pointer1 will point at the middle of the Linked List.

For more details and code : Find the middle of a given linked list

Question #4. Given a Linked List and a number n, write a program that finds the value at the nth node from the end of the Linked List.

Answer : You can find n’th node using length of linked list

• Calculate the length of Linked List. Follow this tutorial Find Length of a Linked List data
• Print the (len – n + 1)th node from the beginning of the Linked List.

Complete tutorial :Program for n’th node from the end of a Linked List

Question #5. Given the pointer to the head node of a linked list, the task is to reverse the linked list. You need to reverse the list by changing links between nodes.

Solutions : Iterative Method

1. Initialise three pointers

currentNode = head;  nextNode = null;  previousNode = null;

2. Iterate trough the linked list. In while loop, do following.
//store next node
currentNode = currentNode->nextNode

// Revers node pointers

currentNode -> next = previousNode 

// Move previous and current node one step forward
previousNode =currentNode
currentNode = nextNode

complete code example check this post : Reverse a Linked list data structure in java