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 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

  • 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 have to allocate a node object for each element in the list

Declare a LinkedList

As a result from 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 an 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 contains 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 implement 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);
    }
}

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);
}

Learn more

Conclusion

In this tutorial, we learned about LinkedList features, class hierarchy and operations. You can find below the full source code