HelloKoding

Practical coding guides

LinkedList in Java

In Java Collections Framework, ArrayList and LinkedList are two different implementations of the List interface. While ArrayList is a dynamic array data structure, LinkedList is a doubly linked list data structure implementation. LinkedList is also implemented the double ended queue data structure of the Deque interface

List implementations in 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

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

Learn more about equals and hashCode

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

LinkedListTest.java

package com.hellokoding.java.collections;

import org.junit.Test;

import java.util.*;

import static org.assertj.core.api.Assertions.assertThat;

public class LinkedListTest {
    @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<>();
    }

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

    @Test
    public void initInOneLineWithDoubleBrace() {
        LinkedList<Integer> linkedList = new LinkedList<>(){{
            add(1);
            add(2);
            add(3);
        }};

        assertThat(linkedList).hasSize(3);
    }

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

    @Test
    public void iterateWithForEachConsumer() {
        LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
        linkedList.forEach(e -> System.out.printf("%d ", e));
    }

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

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

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

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

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

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

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

    @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);
    }
}
Follow HelloKoding