Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList. If you're not sure — just start with ArrayList.
TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList.
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>
get(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use getFirst() and getLast()). One of the main benefits of LinkedList<E>add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use addFirst() and addLast()/add()). One of the main benefits of LinkedList<E>remove(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use removeFirst() and removeLast()). One of the main benefits of LinkedList<E>Iterator.remove() is O(1). One of the main benefits of LinkedList<E>ListIterator.add(E element) is O(1). One of the main benefits of LinkedList<E>
Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)
For ArrayList<E>
get(int index) is O(1). Main benefit of ArrayList<E>add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copiedadd(int index, E element) is O(n) (with n/2 steps on average)remove(int index) is O(n) (with n/2 steps on average)Iterator.remove() is O(n) (with n/2 steps on average)ListIterator.add(E element) is O(n) (with n/2 steps on average)
Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)
LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.
ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)
The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).
Another benefit of using a LinkedList arises when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.
Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.
If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.
An ArrayList, is a growable array. It is just like a regular array. Under the hood, when an element is added at index i, it creates another array with a size which is 1 greater than previous size (So in general, when n elements are to be added to an ArrayList, a new array of size previous size plus n is created). The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.
Since JSR 305 (whose goal was to standardize @NonNull and @Nullable) has been dormant for several years, I'm afraid there is no good answer. All we can do is to find a pragmatic solution and mine is as follows:
Syntax
From a purely stylistic standpoint I would like to avoid any reference to IDE, framework or any toolkit except Java itself.
This rules out:
android.support.annotationedu.umd.cs.findbugs.annotationsorg.eclipse.jdt.annotationorg.jetbrains.annotationsorg.checkerframework.checker.nullness.quallombok.NonNull
Which leaves us with either javax.validation.constraints or javax.annotation.
The former comes with JEE. If this is better than javax.annotation, which might come eventually with JSE or never at all, is a matter of debate.
I personally prefer javax.annotation because I wouldn't like the JEE dependency.
This leaves us with
javax.annotation
which is also the shortest one.
There is only one syntax which would even be better: java.annotation.Nullable. As other packages graduated
from javax to java in the past, the javax.annotation would
be a step in the right direction.
Implementation
I was hoping that they all have basically the same trivial implementation,
but a detailed analysis showed that this is not true.
First for the similarities:
The @NonNull annotations all have the line
public @interface NonNull {}
except for
org.jetbrains.annotations which calls it @NotNull and has a trivial implementationjavax.annotation which has a longer implementationjavax.validation.constraints which also calls it @NotNull and has an implementation
The @Nullableannotations all have the line
public @interface Nullable {}
except for (again) the org.jetbrains.annotations with their trivial implementation.
For the differences:
A striking one is that
javax.annotationjavax.validation.constraintsorg.checkerframework.checker.nullness.qual
all have runtime annotations (@Retention(RUNTIME)), while
android.support.annotationedu.umd.cs.findbugs.annotationsorg.eclipse.jdt.annotationorg.jetbrains.annotations
are only compile time (@Retention(CLASS)).
As described in this SO answer the impact of runtime annotations
is smaller than one might think, but they have the benefit
of enabling tools to do runtime checks in addition to the
compile time ones.
Another important difference is where in the code the annotations can be used.
There are two different approaches. Some packages use JLS 9.6.4.1 style contexts. The following table gives an overview:
FIELD METHOD PARAMETER LOCAL_VARIABLE
android.support.annotation X X X
edu.umd.cs.findbugs.annotations X X X X
org.jetbrains.annotation X X X X
lombok X X X X
javax.validation.constraints X X X
org.eclipse.jdt.annotation, javax.annotation and org.checkerframework.checker.nullness.qual use the contexts defined in
JLS 4.11, which is in my opinion the right way to do it.
This leaves us with
javax.annotationorg.checkerframework.checker.nullness.qual
in this round.
Code
To help you to compare further details yourself I list the code of every annotation below.
To make comparison easier I removed comments, imports and the @Documented annotation.
(they all had @Documented except for the classes from the Android package).
I reordered the lines and @Target fields and normalized the qualifications.
package android.support.annotation;
@Retention(CLASS)
@Target({FIELD, METHOD, PARAMETER})
public @interface NonNull {}
package edu.umd.cs.findbugs.annotations;
@Retention(CLASS)
@Target({FIELD, METHOD, PARAMETER, LOCAL_VARIABLE})
public @interface NonNull {}
package org.eclipse.jdt.annotation;
@Retention(CLASS)
@Target({ TYPE_USE })
public @interface NonNull {}
package org.jetbrains.annotations;
@Retention(CLASS)
@Target({FIELD, METHOD, PARAMETER, LOCAL_VARIABLE})
public @interface NotNull {String value() default "";}
package javax.annotation;
@TypeQualifier
@Retention(RUNTIME)
public @interface Nonnull {
When when() default When.ALWAYS;
static class Checker implements TypeQualifierValidator<Nonnull> {
public When forConstantValue(Nonnull qualifierqualifierArgument,
Object value) {
if (value == null)
return When.NEVER;
return When.ALWAYS;
}
}
}
package org.checkerframework.checker.nullness.qual;
@Retention(RUNTIME)
@Target({TYPE_USE, TYPE_PARAMETER})
@SubtypeOf(MonotonicNonNull.class)
@ImplicitFor(
types = {
TypeKind.PACKAGE,
TypeKind.INT,
TypeKind.BOOLEAN,
TypeKind.CHAR,
TypeKind.DOUBLE,
TypeKind.FLOAT,
TypeKind.LONG,
TypeKind.SHORT,
TypeKind.BYTE
},
literals = {LiteralKind.STRING}
)
@DefaultQualifierInHierarchy
@DefaultFor({TypeUseLocation.EXCEPTION_PARAMETER})
@DefaultInUncheckedCodeFor({TypeUseLocation.PARAMETER, TypeUseLocation.LOWER_BOUND})
public @interface NonNull {}
For completeness, here are the @Nullable implementations:
package android.support.annotation;
@Retention(CLASS)
@Target({METHOD, PARAMETER, FIELD})
public @interface Nullable {}
package edu.umd.cs.findbugs.annotations;
@Target({FIELD, METHOD, PARAMETER, LOCAL_VARIABLE})
@Retention(CLASS)
public @interface Nullable {}
package org.eclipse.jdt.annotation;
@Retention(CLASS)
@Target({ TYPE_USE })
public @interface Nullable {}
package org.jetbrains.annotations;
@Retention(CLASS)
@Target({FIELD, METHOD, PARAMETER, LOCAL_VARIABLE})
public @interface Nullable {String value() default "";}
package javax.annotation;
@TypeQualifierNickname
@Nonnull(when = When.UNKNOWN)
@Retention(RUNTIME)
public @interface Nullable {}
package org.checkerframework.checker.nullness.qual;
@Retention(RUNTIME)
@Target({TYPE_USE, TYPE_PARAMETER})
@SubtypeOf({})
@ImplicitFor(
literals = {LiteralKind.NULL},
typeNames = {java.lang.Void.class}
)
@DefaultInUncheckedCodeFor({TypeUseLocation.RETURN, TypeUseLocation.UPPER_BOUND})
public @interface Nullable {}
The following two packages have no @Nullable, so I list them separately; Lombok has a pretty boring @NonNull.
In javax.validation.constraints the @NonNull is actually a @NotNull
and it has a longish implementation.
package lombok;
@Retention(CLASS)
@Target({FIELD, METHOD, PARAMETER, LOCAL_VARIABLE})
public @interface NonNull {}
package javax.validation.constraints;
@Retention(RUNTIME)
@Target({ FIELD, METHOD, ANNOTATION_TYPE, CONSTRUCTOR, PARAMETER })
@Constraint(validatedBy = {})
public @interface NotNull {
String message() default "{javax.validation.constraints.NotNull.message}";
Class<?>[] groups() default { };
Class<? extends Payload>[] payload() default {};
@Target({ METHOD, FIELD, ANNOTATION_TYPE, CONSTRUCTOR, PARAMETER })
@Retention(RUNTIME)
@Documented
@interface List {
NotNull[] value();
}
}
Support
From my experience, javax.annotation is at least supported by Eclipse and the Checker Framework out of the box.
Summary
My ideal annotation would be the java.annotation syntax with the Checker Framework implementation.
If you don't intend to use the Checker Framework the javax.annotation (JSR-305) is still your best bet for the time being.
If you are willing to buy into the Checker Framework just use
their org.checkerframework.checker.nullness.qual.
Sources
android.support.annotation from android-5.1.1_r1.jaredu.umd.cs.findbugs.annotations from findbugs-annotations-1.0.0.jarorg.eclipse.jdt.annotation from org.eclipse.jdt.annotation_2.1.0.v20160418-1457.jarorg.jetbrains.annotations from jetbrains-annotations-13.0.jarjavax.annotation from gwt-dev-2.5.1-sources.jarorg.checkerframework.checker.nullness.qual from checker-framework-2.1.9.ziplombok from lombok commit f6da35e4c4f3305ecd1b415e2ab1b9ef8a9120b4javax.validation.constraints from validation-api-1.0.0.GA-sources.jar
Best Solution
Another possible answer:
This usually affects which version of GroupLayout is used (i.e. the 1.5 JDesktop version or the JDK 1.6 version). However, I have seen this affect other, non-layout options a few times.