Linked List – addFirst and addLast methods in Java

addFirst method adds the elements at the beginning of the list, whereas the addLast method adds the elements at the end. In this post, we will learn about both methods in detail.

public void addFirst(E e)

What does it do? As the name suggests, it will insert the element at the beginning of the linked list.
What will it return? As the return type is void, it will not return anything to the function calling this method.

Let’s look at the program where we will use addFirst method to add at the start of the linked list.

public class Codekru {

	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>(); // making a linkedList object

		linkedList.add("Second");
		linkedList.add("Third");
		linkedList.add("Fourth");

		System.out.println("Current Linked List: " + linkedList);

		linkedList.addFirst("First"); // inserting at the starting of linked list using addFirst methods

		System.out.println("After using addFirst method: " + linkedList);

	}
}

Output –

Current Linked List: [Second, Third, Fourth]
After using addFirst method: [First, Second, Third, Fourth]

What if we try to use addFirst method on a null LinkedList?

This scenario will give NullPointerException as shown in the below code.

public class Codekru {

	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>(); // making a linkedList object

		linkedList = null;

		linkedList.addFirst("First");

		System.out.println("After using addFirst method: " + linkedList);

	}
}

Output –

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.LinkedList.addFirst(Object)" because "linkedList" is null

What is the time complexity of the addFirst method?

Remember that the inbuilt linked list in java is a doubly-linked list. So, adding a new element somewhere in the list would require the element to be connected with its previous and the next node. addFirst() method adds the element at the beginning of the list by changing the head of the list and connecting the previous head node to the new head node, and vice-versa. Thus, it’s an O(1) operation. So, the time complexity of the addFirst method is O(1).

Internal implementation of the addFirst method

    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

public void addLast(E e)

What does it do? As the name suggests, it will insert the element at the end of the linked list.
What will it return? As the return type of this is void, it will not return anything to the function calling this method.

Now, let’s make a program for this –

public class Codekru {

	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>(); // making a linkedList object

		linkedList.add("First");
		linkedList.add("Second");
		linkedList.add("Third");

		System.out.println("Current Linked List: " + linkedList);

		linkedList.addLast("Fourth"); // inserting at the end of linked list using addLast methods

		System.out.println("After using addLast method: " + linkedList);

	}
}

Output –

Current Linked List: [First, Second, Third]
After using addLast method: [First, Second, Third, Fourth]

What if we try to use the addLast method on a null linked list?

Yeah, you guessed it right. We will get the NullPointerException in this case too.

public class Codekru {

	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>(); // making a linkedList object

		linkedList = null;

		linkedList.addLast("First");

		System.out.println("After using addFirst method: " + linkedList);

	}
}

Output –

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.LinkedList.addLast(Object)" because "linkedList" is null

What is the time complexity of the addLast method?

The time complexity of the addLast method is also O(1). The linked list class in java keeps track of both the first and the last node. Let’s suppose, If it didn’t keep track of the last node, then the time complexity of the addLast() method would have been O(n), where n is the length of the list.

Internal implementation of the addLast method

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

What is the difference between add vs. addLast methods?

You must be thinking that add(E e) does essentially the same thing as addLast(E e). They both add elements at the end of the linked list. They both call the linkLast(E e) function internally to add elements at the end of the linked list. So, they don’t differ in implementation. Why was there a need for two functions to do the same thing?

• add(E e) return true to the calling function after successful execution, but addLast(E e) does not return anything.
• add(E e) is declared in the Collection interface, while addLast(E e) is declared in the Deque interface. LinkedList implements both, directly or indirectly, so LinkedList has to implement both methods. And that’s how we end up having two methods providing the same functionality.

We recommend reading this article to learn more about the linked list and its methods.

We hope that you find this helpful. Please feel free to write us in the comments or mail us at admin@codekru.com for any doubts or concerns.