Open in app

Sign in

Write

Sign in

👨‍💻 Implementing a Linked List in Java: A Step-by-Step Guide for Interview Preparation 📚

Sumeet Panchal
9 min readJan 13, 2025

--

In this blog post, we’ll dive deep into one of the most fundamental data structures in computer science: the linked list. Specifically, we’ll focus on implementing a singly linked list in Java, exploring its methods, and understanding the time and space complexities involved.

What is a Linked List?

A linked list is a linear data structure where elements, known as nodes, are linked using pointers. Each node contains the data and a reference (or a link) to the next node in the sequence.

Why Use a Linked List?

Linked lists are preferred over arrays in certain scenarios because:

  • They provide dynamic size flexibility.
  • They are efficient in inserting or deleting elements.

Implementation Details

Let’s break down the implementation of the singly linked list in Java:

The Node Class

A linked list is built from nodes, where each node contains:

  • A value (the data we store in the node)
  • A next pointer (which refers to the next node in the list)
class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

LinkedList Constructor

To initialize a new linked list, we create a constructor that sets the head, tail, and length of the list.

public LinkedList(int value) {
    Node newNode = new Node(value);
    head = newNode;
    tail = newNode;
    length = 1;
}
  • Explanation: This constructor initializes the list with a single node and sets both the head and tail to the new node.

Methods in the LinkedList

Let’s now look at the methods that manage our linked list.

1. printList()

public void printList() {
    Node temp = head;
    while (temp != null) {
        System.out.println(temp.value);
        temp = temp.next;
    }
}

Explanation: This method traverses through the linked list starting from the head and prints the value of each node. It stops when it reaches the end (when temp becomes null).

2. getHead()

public void getHead() {
    System.out.println("Head: " + head.value);
}

Explanation: This method prints the value of the head node. The head is the first node in the list.

3. getTail()

public void getTail() {
    System.out.println("Tail: " + tail.value);
}

Explanation: This method prints the value of the tail node. The tail is the last node in the list.

4. getLength()

public void getLength() {
    System.out.println("Length: " + length);
}

Explanation: This method prints the current number of nodes in the linked list, which is stored in the length variable.

5. append(int value)

public void append(int value) {
    Node newNode = new Node(value);
    if (length == 0) {
        head = newNode;
    } else {
        tail.next = newNode;
    }
    tail = newNode;
    length++;
}

Explanation: This method adds a new node with the given value to the end (tail) of the list:

  • If the list is empty, the new node becomes both the head and the tail.
  • Otherwise, the current tail’s next pointer is updated to point to the new node, and the tail is updated to the new node.
  • The length is incremented by 1.

6. prepend(int value)

public void prepend(int value) {
    Node newNode = new Node(value);
    if (length == 0) {
        tail = newNode;
    } else {
        newNode.next = head;
    }
    head = newNode;
    length++;
}

Explanation: This method adds a new node with the given value to the beginning (head) of the list:

  • If the list is empty, the new node becomes both the head and the tail.
  • Otherwise, the next pointer of the new node points to the current head and the head is updated to the new node.
  • The length is incremented by 1.

7. removeLast()

public Node removeLast() {
    if (length == 0) {
        return null;
    }
    Node current = head;
    Node prev = head;
    while (current.next != null) {
        prev = current;
        current = current.next;
    }

    tail = prev;
    tail.next = null;
    length--;

    if (length == 0) {
        head = null;
        tail = null;
    }

    return current;
}

Explanation: This method removes the last node from the list:

  • If the list is empty, it returns null.
  • It iterates through the list to find the last node and updates the tail pointer to the previous node.
  • The next pointer of the new tail is set to null, and the length is decremented by 1.
  • If the list becomes empty, both the head and tail pointers are set to null.

8. removeFirst()

public Node removeFirst() {
    if (length == 0) {
        return null;
    }
    Node current = head;
    head = head.next;
    current.next = null;
    length--;

    if (length == 0) {
        head = null;
        tail = null;
    }
    return current;
}

Explanation: This method removes the first node (head) from the list:

  • If the list is empty, it returns null.
  • It updates the head pointer to the next node and sets the next pointer of the removed node to null.
  • If the list becomes empty, both the head and tail pointers are set to null.

9. get(int index)

public Node get(int index) {
    if (index < 0 || index >= length) {
        return null;
    }
    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current;
}

Explanation: This method retrieves the node at a specific index:

  • It checks if the index is valid (within the range of the list).
  • It then iterates through the list to reach the node at the given index and returns it.

10. set(int index, int value)

public boolean set(int index, int value) {
    Node current = get(index);
    if (current != null) {
        current.value = value;
        return true;
    }
    return false;
}

Explanation: This method sets the value of the node at the specified index:

  • It retrieves the node at the given index using the get() method.
  • If the node exists, it updates its value and returns true.
  • If the node does not exist, it returns false.

11. insert(int index, int value)

public boolean insert(int index, int value) {
    if (index < 0 || index > length) {
        return false;
    }
    if (index == 0) {
        prepend(value);
    } else if (index == length) {
        append(value);
    } else {
        Node newNode = new Node(value);
        Node prev = get(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
        length++;
    }

    return true;
}

Explanation: This method inserts a new node at a specific index:

  • It checks if the index is valid.
  • If the index is 0, it prepends the node.
  • If the index is equal to the length, it appends the node.
  • Otherwise, it inserts the new node between two existing nodes by updating the next pointers.

12. remove(int index)

public Node remove(int index) {
    if (index < 0 || index >= length) {
        return null;
    }
    if (index == 0) {
        return removeFirst();
    } else if (index == length - 1) {
        return removeLast();
    }

    Node prev = get(index - 1);
    Node current = prev.next;
    prev.next = current.next;
    current.next = null;
    length--;
    return current;
}

Explanation: This method removes a node at a specific index:

  • It checks if the index is valid.
  • If the index is 0, it removes the first node.
  • If the index is the last one, it removes the last node.
  • Otherwise, it removes a node from the middle by updating the next pointers.

13. reverse()

public void reverse() {
    Node current = head;
    head = tail;
    tail = current;

    Node before = null;
    Node after;

    for (int i = 0; i < length; i++) {
        after = current.next;
        current.next = before;
        before = current;
        current = after;
    }
}

Explanation: This method reverses the order of nodes in the list:

  • It swaps the head and tail.
  • It iterates through the list, changing the direction of each node’s next pointer to reverse the order of nodes.

Conclusion

By implementing these methods, we can perform various operations on a linked list, such as adding, removing, retrieving, and modifying nodes at any position. Linked lists are particularly useful when we need efficient insertion and deletion operations without worrying about shifting elements like in arrays.

Entire class

package datastructures.linkedList;

public class LinkedList {
    private Node head;
    private Node tail;
    private int length;

    /**
     * A node class
     */
    static class Node {

        int value;
        Node next;

        /**
         * Constructor
         *
         * @param value - value for a node
         */
        Node(int value) {
            this.value = value;
        }
    }

    /**
     * Constructor to build a new linked list instance
     *
     * @param value - the first value to be inserted into the linked list
     */
    public LinkedList(int value) {
        Node newNode = new Node(value);
        head = newNode;
        tail = newNode;
        length = 1;
    }

    /**
     * Prints the node values within a linked list
     */
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.value);
            temp = temp.next;
        }
    }

    /**
     * Utility method to return the head value for a linked list
     */
    public void getHead() {
        System.out.println("Head: " + head.value);
    }

    /**
     * Utility method to return the tail value for a linked list
     */
    public void getTail() {
        System.out.println("Tail: " + tail.value);
    }

    /**
     * Utility method to return the length of a linked list
     */
    public void getLength() {
        System.out.println("Length: " + length);
    }

    /**
     * Add a node to the end of the LinkedList
     * This operation is O(1) which is constant in nature
     *
     * @param value - the value to be added
     */
    public void append(int value) {
        Node newNode = new Node(value);
        if (length == 0) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        length++;
    }

    /**
     * Add a node to the start of the LinkedList
     * This operation is O(1) which is constant in nature
     *
     * @param value - the value to be added
     */
    public void prepend(int value) {
        Node newNode = new Node(value);
        if (length == 0) {
            tail = newNode;
        } else {
            newNode.next = head;
        }
        head = newNode;
        length++;
    }

    /**
     * removes last item from the LinkedList
     * This operation is O(n) since we need to iterate
     * through all the items within the linked list
     *
     * @return Node
     */
    public Node removeLast() {
        if (length == 0) {
            return null;
        }
        Node current = head;
        Node prev = head;
        while (current.next != null) {
            prev = current;
            current = current.next;
        }

        tail = prev;
        tail.next = null;
        length--;

        if (length == 0) {
            head = null;
            tail = null;
        }

        return current;
    }

    /**
     * removes first item from the LinkedList
     * This operation is O(1) which is constant in nature
     *
     * @return Node
     */
    public Node removeFirst() {
        if (length == 0) {
            return null;
        }
        Node current = head;
        head = head.next;
        current.next = null;
        length--;

        if (length == 0) {
            head = null;
            tail = null;
        }
        return current;
    }

    /**
     * Returns a node at the specified index within the LinkedList
     * This operation is O(n) since we need to iterate
     * through 'n' number the items within the linked list
     *
     * @param index - the index to get the value from
     * @return Node
     */
    public Node get(int index) {
        if (index < 0 || index >= length) {
            return null;
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    /**
     * Replaces the value at a specified index within the LinkedList
     * This operation is O(n) since we need to iterate
     * through 'n' number the items within the linked list to change its value
     *
     * @param index - the index to change
     * @param value - the new value to be added at that index
     * @return Node
     */
    public boolean set(int index, int value) {
        Node current = get(index);
        if (current != null) {
            current.value = value;
            return true;
        }
        return false;
    }

    /**
     * Inserts a node at a specified index within the LinkedList
     * This operation is O(n).
     *
     * @param index - the index to insert at
     * @param value - the new value to be inserted at that index
     * @return boolean
     */
    public boolean insert(int index, int value) {
        if (index < 0 || index > length) {
            return false;
        }
        if (index == 0) {
            prepend(value);
        } else if (index == length) {
            append(value);
        } else {
            Node newNode = new Node(value);
            Node prev = get(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
            length++;
        }

        return true;
    }

    /**
     * Removes a node at a specified index within the LinkedList
     *
     * @param index - the index at which the value needs to be removed
     * @return Node
     */
    public Node remove(int index) {
        if (index < 0 || index >= length) {
            return null;
        }
        if (index == 0) {
            return removeFirst();
        } else if (index == length - 1) {
            return removeLast();
        }

        Node prev = get(index - 1);
        Node current = prev.next;
        prev.next = current.next;
        current.next = null;
        length--;
        return current;
    }

    /**
     * Reverses the LinkedList
     */
    public void reverse() {
        Node current = head;
        head = tail;
        tail = current;

        Node before = null;
        Node after;

        for (int i = 0; i < length; i++) {
            after = current.next;
            current.next = before;
            before = current;
            current = after;
        }
    }
}

For further learning and practice with Java Data Structures and Algorithms, feel free to check out my GitHub repository:

DSA in Java

This blog covers the core functionality and implementation of a singly linked list in Java, which is an essential concept for coding interviews and understanding fundamental data structures!

Interview Preparation
Datastrucutre
Linked Lists
Java
Implementation

--

--

Sumeet Panchal
Sumeet Panchal

Written by Sumeet Panchal

121 Followers
12 Following

Programming enthusiast specializing in Android and React Native, passionate about crafting intuitive mobile experiences and exploring innovative solutions.

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams