Linked Lists

Questions about linked lists used to be extremely popular with interviewers because although they are simple to implement, they test very important programming concepts (notably pointers) and still allow room for challenging questions. However, with the growth of Java, these types of questions are a little less common, but if you are applying for a C/C++ position, this is still a perennial classic.

A linked list is a data structure composed of nodes. Each node is represented by a class or struct and contains at least a data payload of some type as well as a pointer to the next node. The first node in a linked list is called a head, and is often also referred to confusingly as the linked list. The last element is called the tail.

Three different kinds of linked lists exist:

  • Singly linked lists have a single pointer pointing to the next element in the list. The last pointer is empty or points to null, signaling the end of the list.
  • Doubly linked lists have two pointers, one pointing to the next element and one pointing to the previous element. The head node's previous pointer points to null and the tail node's next pointer points to null to signal the end of the list.
  • Circular linked lists usually represent buffers. They have no head or tail, and the primary issue is avoiding infinite traversals because of the cycle. These questions rarely come up in interview questions. Arrays are oftentimes a better substitute for a circular linked list, using the modulus operator to wrap around.

The most popular one by far is the singly linked list; when people refer to linked lists, you can assume they mean a singly linked list. Interview questions involving doubly linked lists are rare because many operations are trivial when dealing with them, plus the overhead of keeping twice as many pointers makes them less attractive in real life.

Practice Question: Implement a linked list in C using a struct. Have the data be integers.

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

Practice Question: Implement a linked list in Java. Have the data be of the class Object and include a default constructor.

public class Node {
    Node next;
    Object data;
    public Node(Object data) {
        this.data = data;
    }
}

Linked lists have a lot of potential hazards. Lists can only be traversed in one direction, so you will always need to keep track of the head element; otherwise you lose the ability to access all of the elements in the list since you'll be unable to traverse the full list. Also, remember to check for null pointers.

Tracking Head Element

You must make sure to keep a reference to the head of the linked list at all times or else lose the list. In Java, you can achieve this by having the method return the head element of the list.

For example, this function is not a good idea:

public static void insertInFront(Node head, Object data) {
    Node node = new Node(data);
    node.next = head;
}

because it fails to keep track of the head element.

Instead, make sure to return the new head element, which in this case is the newly created node, as in the following example.

public static Node insertInFront(Node head, Object data) {
    Node node = new Node(data);
    node.next = head;
    return node;
}

This way, you can assign the head element in the calling function to the return value.

Node head = new Node();
// some operations here...
Object data = new Object();
head = Node.insertInFront(head, data);

Traversing the Linked List

To access an element of the list other than the head, you'll need to traverse the list. When doing so, don't forget to check for the null pointer that designates the end of the list! You may want to throw an Exception instead of returning null depending on the business requirements of your search function.

public static Node search(Node head, Object data) {
    while (head != null && head.data != data) {
        head = head.next;
    }
 
    return head;
}

Inserting Elements

Inserting an element into a linked list requires at least two pointers; one holding the current node and the other holding the previous node.

Example: (1) -> (3) ==> (1) -> (2) -> (3)

Practice Question: Insert an element in order into a sorted linked list containing integer data.

With two pointers, this problem should boil down to finding the two nodes that the element to be inserted should go between. Two special cases are if the insertion node should be in the head or tail position, and also don’t forget to test for a null head and for the list’s end.

public Node insertInOrder(Node head, Node insert) {
    if (head == null)
        return null;
 
    Node previous = head;
    Node current = head.next;
 
    if (current == null) {
        if (previous.data < insert.data) {
            previous.next = insert;
            insert.next = null;
            return head;
        }
        else {
            insert.next = previous;
            return insert;
        }
    }
 
    while (current != null) {
        if (previous.data < insert.data && current.data >= insert.data) {
            previous.next = insert;
            insert.next = current;
            return head;
        }
        current = current.next;
        previous = previous.next;
    }
 
    current = insert;
    insert.next = null;
 
    return head;
}

Removing Elements

Removing an element from a linked list has the same requirements as inserting an element. Make sure to use two pointers and include a special case for the head element. If you’re using C/C++, don’t forget to free the memory used by the node to be removed.

Practice Question: Delete an element from a linked list containing integer data.

Node delete(Node head, int data) {
    if (head.data == data)
        return head.next;
 
    Node previous = null;
    Node current = head;
 
    while (current != null) {
        if (current.data == data) {
            previous.next = current.next;
            return head;
        }
	else {
	    previous = current;
	    current = current.next;
	}
    }
 
    return head;
}

Reversing a Linked List

This requires three pointers. You should be able to do this in linear time and without allocating additional memory other than pointers.

Practice Question: Write a method to reverse a linked list.

Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node forward;
 
    while (current != null) {
        forward = current.next;
        current.next = previous;
        previous = current;
        current = forward;
    }
 
    return previous;
}

Practice Question: Write an implementation of a stack that holds integers using a linked list. Assume you’re given the linked list class definition from before.

This question tests your understanding of the abstract stack data structure as well as linked list implementations and performance.

A stack is an abstract data structure which follows a last in, first out (LIFO) ordering. They are useful for representing recursive calls iteratively. Every stack needs at least two basic operations: push, which adds an element onto the stack, and pop, which removes the top element on the stack and returns it. Some stacks have an additional operation called peek which allows the user to view the top element without removing it.

Since we’re using a linked list to implement a stack, it makes sense for the head of the list to represent the top of the stack because adding and removing elements at the head of a linked list is O(1) time, whereas the same operations at the end of the list takes O(n) time.

Don’t forget error handling! Popping or peeking an element off of an empty stack should not be allowed; in Java, you would raise an exception.

class IntStack {
    Node stack;
 
    IntStack() {
        this.stack = null;
    }
 
    public void push(int val) {
	Node value = new Node(val);
	value.next = this.stack;
	this.stack = value;
    }
 
    public int pop() {
	if (stack == null) {
	    return ERROR;
	}
	else {
	    Node value = this.stack;
	    this.stack = this.stack.next;
	    return value.data;
	}
    }
 
    public int peek() {
	if (stack == null)
	    return ERROR;
	else
	    return this.stack.data;
    }
}

Practice Question: Find a function that finds the nth to last element of a linked list, where 0 is the last element (tail) of the list.

Finding the nth element in a linked list is easy by just traversing the list and keeping a running count of how many nodes you’ve seen, but finding the nth from last is tricky because you don’t know how long the list is.

Therefore, the naïve solution is to go through the entire linked list first, tallying the number of nodes so that you get the total, and then find nth to last by subtracting n from total. Then, traverse starting from the head again, counting until you reach nth to last.

However, this algorithm requires 2 passes through the linked list – can we do it in less? Another idea might be to store the last n nodes seen, but this requires extra memory especially as n gets large. We can combine the two ideas to achieve the solution in one linear pass of the linked list while using only one additional pointer.

Since you’re only interested in the nth from last element, we can create another pointer to the head after the original pointer has traversed n nodes. Then, increment both pointers until the current pointer reaches the end of the list – at that time the behind pointer will be pointing to the nth from last node!

Are there any special cases to be aware of? As always, be aware of the possibilities of null pointers; you should account for the case where n is greater than the length of the list.

Node nthToLast(Node head, int n) {
    Node lead = head;
    Node chase = head;
 
    for (int i = 0; i < n; i++) {
	if (lead == null)
	    return null;
	else
	    lead = lead.next;
    }
 
    while (lead.next != null) {
        lead = lead.next;
        chase = chase.next;
    }
 
    return chase;
}

Practice Question: Determine whether a linked list contains a cycle.

Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track of what nodes have been encountered.

One idea is to mark nodes that have been seen, either by adding a flag to the node itself or storing information about the node in a separate data structure. Unfortunately, this method requires modification of the node and/or additional space.

With linked list problems, the solution usually takes advantage of multiple pointers. How can we use another pointer to help us out? The previous problem advanced two pointers at a fixed interval between each other, but that doesn’t seem to help. A better idea is to advance the pointers at two different speeds.

One pointer will travel at twice the speed of the other, so in an acyclic list, the fast one will reach the end. However, in a cyclic list, both pointers loop endlessly, but the faster pointer will lap the slower pointer at some point, so if the faster pointer ever catches up to the slower pointer, the list has a cycle.

To make one pointer “faster” than the other, just advance it two nodes instead of one. However, be aware of null pointers.

The running time for this algorithm is O(n). For the acyclic case, the faster pointer will reach the last node after traversing the entire list. For the cyclic case, the slower pointer will only go around a loop at most once, and the faster pointer will only go through a loop at most twice, so in the worst case 3n nodes are examined, which is still an O(n) algorithm.

public static boolean hasCycle(Node head) {
    Node fast = head;
    Node slow = head;
 
    while (fast != null && slow != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
 
        if (slow == fast) {
            return true;
        }
    }
 
    return false;
}

Webfaction is the ULTIMATE hosting platform for any serious developer.
SSH, WordPress, Rails, Django, cronjobs, compile and execute anything.
ProgrammingInterview.com is proudly powered by Webfaction.