Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java LinkedList addFirst: Usage and Performance

Learn how to use Java LinkedList addFirst to prepend elements, understand its O(1) performance, and see how it compares with addLast and ArrayDeque.

~4 min readJava
#Java#LinkedList#addFirst#Collections
Diagram showing a linked list with a new node being added at the head using addFirst method.

When you need to prepend an element to a Java LinkedList, addFirst(E e) is the direct way to do it. It inserts the element at the head of the list, making the previous head the second element. This article explains how addFirst behaves, why it runs in constant time, and the practical tradeoffs involved.

What addFirst Does

The addFirst(E e) method inserts the specified element at the front of the list. It is semantically equivalent to add(0, e), but it is clearer when the intent is to prepend. The method returns void, unlike offerFirst, which returns a boolean to indicate success. Since LinkedList allows null elements, addFirst(null) is valid and will insert a null reference at the head.

java
LinkedList<String> list = new LinkedList<>(); list.addFirst("first"); list.addFirst("new head"); System.out.println(list); // [new head, first]

After the second call, the list contains new head at index 0 and first at index 1. The order reflects the sequence of insertions at the head.

How addFirst Works Internally

LinkedList is a doubly-linked list. Each node holds references to the previous node, the next node, and the element itself. The list maintains references to the first node (first) and the last node (last). When you call addFirst, a new node is created and linked before the current first node; if the list is empty, the new node becomes both first and last. The operation updates a constant number of references and does not depend on the size of the list, so its time complexity is O(1).

This is a key advantage over ArrayList, where inserting at the beginning requires shifting all existing elements to the right, an O(n) operation.

Using addFirst in Code

addFirst is useful when you need stack-like behavior where the most recently added element is processed first. For example, an undo history could use addFirst to keep the latest action at the front.

java
LinkedList<String> undoHistory = new LinkedList<>(); undoHistory.addFirst("Open file"); undoHistory.addFirst("Edit line 3"); undoHistory.addFirst("Save file"); // The most recent action is at index 0 String lastAction = undoHistory.getFirst();

Because LinkedList implements Deque, you can also use push(), which is equivalent to addFirst. The choice is largely stylistic; push is more conventional when treating the list as a stack.

java
LinkedList<Integer> stack = new LinkedList<>(); stack.push(10); stack.push(20); int top = stack.pop(); // returns 20

addFirst vs addLast vs add

The add method, when called without an index, appends to the end of the list and is equivalent to addLast. The table below compares the insertion methods.

MethodPositionTime ComplexityReturn Value
addFirstHeadO(1)void
addLastTailO(1)void
add(index)Specified indexO(n)void

addFirst and addLast are O(1) because they only update the boundary nodes. add(index) must traverse the list to find a general insertion point, making it O(n) in the worst case; if it appends at the end, the implementation can link directly to the current tail. If you are frequently inserting at both ends, LinkedList is a candidate, but consider ArrayDeque as well. If you need random access by index, ArrayList is better despite its O(n) insertion at the head.

Performance and Memory Considerations

While addFirst is O(1), each node in a LinkedList carries two extra references compared with an array. This memory overhead is significant for large lists. Additionally, LinkedList has poor cache locality because nodes are scattered in memory, which can degrade iteration performance. In contrast, ArrayList stores elements contiguously, enabling faster iteration and random access.

For operations that only prepend elements, ArrayDeque is often a better choice than LinkedList. ArrayDeque also provides addFirst with O(1) amortized time and uses a resizable array, which has lower memory overhead and better cache behavior. However, ArrayDeque does not allow null elements, so if you need to store nulls, LinkedList is necessary.

Common Pitfalls and Edge Cases

One common mistake is assuming addFirst returns a boolean like offerFirst. It returns void. If you need to check whether an element was accepted, which only matters for capacity-restricted queues, use offerFirst instead.

Another edge case is inserting into an empty list. addFirst works correctly on an empty list and sets both first and last to the new node. There is no special handling required.

Null elements are allowed. If your application relies on null to represent an absence of value, addFirst(null) works. But be cautious when using getFirst() later: if the head element is null, it will be returned as null, which can be ambiguous if null is also used as a sentinel.

When to Choose LinkedList.addFirst

Use LinkedList.addFirst when you need a doubly-linked list with constant-time insertion at the head and also require the ability to insert at the tail or remove from either end. It is appropriate for implementing queues, stacks, or deques where null elements must be supported. If you only need a stack or queue and nulls are not required, prefer ArrayDeque for better performance and memory usage. If your primary need is random access, ArrayList is the right choice, even though prepending is O(n). The decision depends on the balance between insertion flexibility and access patterns in your specific use case.

When building a list where the most frequent operation is prepending and you do not need index-based access, LinkedList.addFirst provides a straightforward O(1) solution. Its main tradeoff is memory overhead and reduced cache efficiency, which becomes more pronounced as the list grows. For small lists, the difference is negligible; for large lists, measure and profile to confirm that the behavior meets your performance requirements.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.