A Guide to the Java LinkedList

1. Introduction

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It implements all optional list operations and permits all elements (including null).

2. Features

Below you can find the most important properties of the LinkedList:

  • Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index
  • It is not synchronized
  • Its Iterator and ListIterator iterators are fail-fast (which means that after the iterator’s creation, if the list is modified, a ConcurrentModificationException will be thrown)
  • Every element is a node, which keeps a reference to the next and previous ones
  • It maintains insertion order

Although LinkedList is not synchronized, we can retrieve a synchronized version of it by calling the Collections.synchronizedList method, like:

List list = Collections.synchronizedList(new LinkedList(...));

3. Comparison to ArrayList

Although both of them implement the List interface, they have different semantics – which will definitely affect the decision of which one to use.

3.1. Structure

An ArrayList is an index based data structure backed by an Array. It provides random access to its elements with a performance equal to O(1).

On the other hand, a LinkedList stores its data as a list of elements and every element is linked to its previous and next element. In this case, the search operation for an item has execution time equal to O(n).

3.2. Operations

The insertion, addition and removal operations of an item are faster in a LinkedList because there is no need to resize an array or update the index when an element is added to some arbitrary position inside the collection, only references in surrounding elements will change.

3.3. Memory Usage

LinkedList consumes more memory than an ArrayList because of every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index.

4. Usage

Here are some code samples that show how you can use LinkedList:

4.1. Creation

LinkedList<Object> linkedList = new LinkedList<>();

4.2. Adding Element

LinkedList implements List and Deque interface, besides standard add() and addAll() methods you can find addFirst() and addLast(), which adds an element in the beginning or the end, respectively.

4.3. Removing Element

Similarly to element addition this list implementation offers removeFirst() and removeLast().

Also, there is convenient method removeFirstOccurence() and removeLastOccurence() which returns boolean (true if collection contained specified element).

4.4. Queue Operations

Deque interface provides queue-like behaviors (actually Deque extends Queue interface):

linkedList.poll();
linkedList.pop();

Those methods retrieve the first element and remove it from the list.

The difference between poll() and pop() is that pop will throw NoSuchElementException() on empty list, whereas poll returns null. The APIs pollFirst() and pollLast() are also available.

Here’s for example how the push API works:

linkedList.push(Object o);

Which inserts the element as the head of the collection.

LinkedList has many other methods, most of which should be familiar to a user who already used Lists. Others that are provided by Deque might be a convenient alternative to “standard” methods.

The full documentation can be found here.

5. Conclusion

ArrayList is usually the default List implementation.

However, there are certain use cases where using LinkedList will be a better fit, such as preferences for constant insertion/deletion time (e.g., frequent insertions/deletions/updates), over constant access time and effective memory usage.

Code samples can be found over on GitHub.

Related posts:

Giới thiệu Google Guice – Dependency injection (DI) framework
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
A Quick JUnit vs TestNG Comparison
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Remove HTML tags from a file to extract only the TEXT
File Upload with Spring MVC
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
StringBuilder vs StringBuffer in Java
Creating a Custom Starter with Spring Boot
Java Program to Solve TSP Using Minimum Spanning Trees
Java Program to Implement Strassen Algorithm
Anonymous Classes in Java
Spring Security Remember Me
Java Program to Implement Fermat Factorization Algorithm
Testing an OAuth Secured API with Spring MVC
Java Program to Generate a Random Subset by Coin Flipping
Jackson – Decide What Fields Get Serialized/Deserialized
Servlet 3 Async Support with Spring MVC and Spring Security
Calling Stored Procedures from Spring Data JPA Repositories
Retrieve User Information in Spring Security
Biểu thức Lambda trong Java 8 – Lambda Expressions
Spring MVC Setup with Kotlin
Using a Spring Cloud App Starter
Guide to Java Instrumentation
Converting a Stack Trace to a String in Java
Getting Started with Stream Processing with Spring Cloud Data Flow
Command-Line Arguments in Java
Java Program to Find Hamiltonian Cycle in an UnWeighted Graph
Spring Cloud AWS – S3
Java Program to Implement Queue
Converting a Stack Trace to a String in Java
Java Program to Give an Implementation of the Traditional Chinese Postman Problem