LinkedList in Java is a doubly linked list data structure implementation of the List and Deque interfaces, a part of the Java Collections Framework
LinkedList has the following features
Provides insertion-ordered iteration
Provides element retrieving, adding and removing at both ends in a constant-time performance
Provides index-based operations in linear-time performance. They will traverse the list either from the beginning or the end, whichever is closer to the specified index
Allows null and duplicated elements
Elements are compared based on their equals method implementation
Can be used as a list, stack, queue or double-ended queue
LinkedList is not thread-safe as it is an unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally
Lets walk through this tutorial to explore LinkedList in more details
The LinkedList class hierarchy
LinkedList implements both List and Deque interfaces. List extends from Collection and Iterable interfaces hierarchically. Deque extends from Queue, Collection and Iterable hierarchically
LinkedList vs ArrayList and ArrayDeque
LinkedList is more flexible than ArrayList and ArrayDeque as it can act as both List and Deque
In terms of efficiency, LinkedList is slower than ArrayList on List based operations and slower than ArrayDeque on Deque based operations
LinkedList consumes a bit more memory than ArrayList and ArrayDeque as it has to allocate a node object for each element in the list
Declare a LinkedList
As a result of the above class hierarchy, a LinkedList can be declared and used as a list, stack, queue or double-ended queue
@Test
public void declare() {
List<Integer> list = new LinkedList<>();
assertThat(list).isInstanceOf(LinkedList.class);
Queue<Integer> queue = new LinkedList<>();
assertThat(queue).isInstanceOf(LinkedList.class);
Deque<Integer> stackOrDeque = new LinkedList<>();
assertThat(stackOrDeque).isInstanceOf(LinkedList.class);
LinkedList<Integer> linkedList = new LinkedList<>();
}
Create and Initialize
You can provide either List.of or Set.of factory methods, since Java 9, or Arrays.asList to the LinkedList(Collection) constructor to create and init a LinkedList in one line
The iteration order of the created LinkedList is defined by the given collection iterator
List.of permits duplicated elements while Set.of doesn't, it throws IllegalArgumentException. Both List.of and Set.of don't permit null element, they throw NullPointerException
Array.asList accepts duplicated and null elements
@Test
public void initWithFactoryMethodsInOneLine() {
LinkedList<Integer> linkedList1 = new LinkedList<>(List.of(3, 1, 2, 2));
assertThat(linkedList1).containsExactly(3, 1, 2, 2);
LinkedList<Integer> linkedList2 = new LinkedList<>(Set.of(1, 2, 3));
assertThat(linkedList2).contains(1, 2, 3);
LinkedList<Integer> linkedList3 = new LinkedList<>(Arrays.asList(3, 1, 2, 2, null));
assertThat(linkedList3).containsExactly(3, 1, 2, 2, null);
}
- Double brace initialization can cause a memory leak as it creates anonymous classes with a hidden reference to the owner instance object
@Test
public void initInOneLineWithDoubleBrace() {
LinkedList<Integer> linkedList = new LinkedList<>(){{
add(1);
add(2);
add(3);
}};
assertThat(linkedList).hasSize(3);
}
- Initialize after the creation time by using add and addAll methods
@Test
public void initWithAddAll() {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(2); // can add duplicated element
linkedList.add(null); // add null element
linkedList.addAll(List.of(4, 5, 6));
// The iteration order is same as the insertion order
assertThat(linkedList).containsExactly(1, 2, 2, null, 4, 5, 6);
}
Iterate a LinkedList
- You can iterate a LinkedList by using either forEach(Consumer), since Java 8, or for-each and other index-loops (while, do-while, for-index)
@Test
public void iterateWithForEachConsumer() {
List<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
linkedList.forEach(e -> System.out.printf("%d ", e));
}
- Iterator and ListIterator can also be used to iterate a LinkedList forward and backward respectively
@Test
public void iterateWithIteratorAndListIterator() {
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
// Iterate forward with Iterator
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()){
System.out.printf("%d ", iterator.next());
}
// Iterate backward with ListIterator
ListIterator<Integer> listIterator = linkedList.listIterator(linkedList.size());
while (listIterator.hasPrevious()){
System.out.printf("%d ", listIterator.previous());
}
}
Retrieve and Filter
- Retrieve the first and last element from a LinkedList by using getFirst() and getLast() methods in constant-time performance
@Test
public void retrieving() {
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
int firstElement = linkedList.getFirst();
assertThat(firstElement).isEqualTo(1);
int lastElement = linkedList.getLast();
assertThat(lastElement).isEqualTo(3);
}
You can also retrieve an element from a given index by using get(index) method and retrieve index of an element by using indexOf(Object) and lastIndexOf(Object), but in linear-time performance
Since Java 8, you can use Stream API to filter and retrieve elements from a LinkedList
The following example uses Stream API to get the first element with findFirst() and filter elements with filter(Predicate)
@Test
public void filterAndRetrieve() {
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
Integer firstElement = linkedList.stream().findFirst().orElse(null);
assertThat(firstElement).isEqualTo(1);
Integer[] arr = linkedList.stream().filter(e -> e >= 2).toArray(Integer[]::new);
assertThat(arr).contains(2, 3);
}
Examine, Add, Update and Remove
Add and remove an element at the first and last of a LinkedList by using add(Object), addFirst(Object), addLast(Object), remove(), removeFirst() and removeLast() methods in constant-time performance
add(Object) and remove() internally call addLast(Object) and removeFirst()
@Test
public void addAndRemove() {
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
linkedList.addFirst(0);
assertThat(linkedList).containsExactly(0, 1, 2, 3);
linkedList.addLast(4);
assertThat(linkedList).containsExactly(0, 1, 2, 3, 4);
linkedList.removeFirst();
assertThat(linkedList).containsExactly(1, 2, 3, 4);
linkedList.removeLast();
assertThat(linkedList).containsExactly(1, 2, 3);
}
You can also add and remove an element at the specified index by using add(index, Object) and remove(index) methods, but in linear-time performance
Examine if an element is existing in a LinkedList with contains(Object) method
Update an element at the specified index in a LinkedList to the given object with set(index, Object) method
Both contain and set methods run in linear-time performance
@Test
public void examineAndUpdate() {
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
boolean contained = linkedList.contains(1);
assertThat(contained).isTrue();
linkedList.set(1, 20);
assertThat(linkedList).containsExactly(1, 20 , 3);
}
Objects comparing in a LinkedList
Internally, operations such as contains(Object), add(Object) and remove(Object) compare objects based on their equals method implementation
In the following example,
linkedList.contains(new Book(1, "a"))should return true but false,linkedList.remove(new Book(1, "a"))should success but not due to lack of equals implementation on the user defined class
@Test
public void objectsComparingProblem(){
LinkedList<Book> linkedList = new LinkedList<>();
linkedList.add(new Book(1, "a"));
Boolean contained = linkedList.contains(new Book(1, "a"));
assertThat(contained).isFalse();
linkedList.remove(new Book(1, "a"));
assertThat(linkedList).hasSize(1);
}
static class Book {
int id;
String title;
Book(int id, String title) {
this.id = id;
this.title = title;
}
int getId() {
return id;
}
String getTitle() {
return title;
}
}
- You can fix the above problem by implementing the equals method to the custom class as the below example
@Test
public void objectsComparingFixed(){
LinkedList<BookFixed> linkedList = new LinkedList<>();
linkedList.add(new BookFixed(1, "a"));
Boolean contained = linkedList.contains(new BookFixed(1, "a"));
assertThat(contained).isTrue();
linkedList.remove(new BookFixed(1, "a"));
assertThat(linkedList).hasSize(0);
}
static class BookFixed {
int id;
String title;
BookFixed(int id, String title) {
this.id = id;
this.title = title;
}
int getId() {
return id;
}
String getTitle() {
return title;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BookFixed bookFixed = (BookFixed) o;
return id == bookFixed.id &&
Objects.equals(title, bookFixed.title);
}
}
In practice, consider to override hashCode when overriding equals as your defined classes may be used elsewhere in a hash table based collections such as HashSet and HashMap
Sort a LinkedList
Sort a LinkedList of objects by using its instance's sort(Comparator) method in conjunction with Comparable and Comparator interfaces to control over the sort order
@Test
public void sortMultipleFields() {
Book book1 = new Book(1, "b");
Book book2 = new Book(2, "c");
Book book3 = new Book(3, "c");
LinkedList<Book> list = new LinkedList<>(Arrays.asList(book1, book2, book3));
list.sort(Comparator
.comparing(Book::getTitle, Comparator.reverseOrder())
.thenComparing(Book::getId, Comparator.reverseOrder()));
assertThat(list).containsExactly(book3, book2, book1);
}
Conclusion
In this tutorial, we learned about LinkedList features, class hierarchy and operations. You can find below the full source code