Java LinkedList is an ordered collection aka sequence, implementation of java.util.List and java.util.Deque interfaces. LinkedList has the following attributes

  • Backed by doubly linked list data structure, support element insertion and removal at both ends

  • Support index based operations. They will traverse the list from the beginning or the end, whichever is closer to the specified index

  • Elements are positioned as their insertion order

  • Allow null and duplicate elements

  • Can be used as a queue or double-ended queue

  • Unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally

LinkedList declaration and initialization

  • In one line with Arrays.asList
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
  • In one line with List.of since Java 9+
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));  
  • In one line with Double brace initialization (should not be used)
LinkedList<Integer> lst = new LinkedList<Integer>(){{  
    add(1);
    add(2);
    add(3);
}};

Double brace initialization can lead to memory leaks as it creates an anonymous class with a reference to the owner object

  • In multiple lines
LinkedList<Integer> lst = new LinkedList<>();  
lst.add(1);  
lst.add(2);  
lst.add(3);  

CRUD operations of LinkedList elements

All index based operations throw IndexOutOfBoundsException if the index is out of range

  • Appends an element at the end of the list, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.add(4); // the list now is {1, 2, 3, 4}  
lst.addLast(5); // the list now is {1, 2, 3, 4, 5}  

LinkedList's add is equivalent to addLast

  • Inserts an element at the beginning of the list, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.addFirst(4); // the list now is {4, 1, 2, 3}  
  • Inserts an element at a specific index of the list, O(n/2)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.add(0, 4); // the list now is {4, 1, 2, 3}  
lst.add(5, 5); // throws IndexOutOfBoundsException  
  • Gets the first element in the list + throws NoSuchElementException if the list is empty, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer ele = lst.getFirst(); // return 1

LinkedList<Integer> emptyLst = new LinkedList<>();  
Integer invalidEle = emptyLst.getFirst(); // throws NoSuchElementException  
  • Gets the last element in the list + throws NoSuchElementException if the list is empty, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer ele = lst.getLast(); // return 3

LinkedList<Integer> emptyLst = new LinkedList<>();  
Integer invalidEle = emptyLst.getLast(); // throws NoSuchElementException  
  • Gets an element at a specified index in the list, O(n/2)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer ele = lst.get(0); // gets element at index 0, returns 1  
Integer invalidEle = lst.get(3); // throws IndexOutOfBoundsException  
  • Replaces an element at a specified index in the list, O(n/2)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.set(0, 10); // replace element at index 0 with 10, the list now is {10, 2, 3}  
lst.set(3, 10); // throws IndexOutOfBoundsException
  • Removes and returns the first element in the list + throws NoSuchElementException if the list is empty, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer ele = lst.removeFirst(); // return 1, the list now is {2, 3}  
Integer ele = lst.remove(); // return 2, the list now is {3}

LinkedList<Integer> emptyLst = new LinkedList<>();  
Integer invalidEle = emptyLst.removeFirst(); // throws NoSuchElementException  

LinkedList's remove is equivalent to removeFirst

  • Removes and returns the last element in the list + throws NoSuchElementException if the list is empty, O(1)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer ele = lst.removeLast(); // return 3, the list now is {1, 2}

LinkedList<Integer> emptyLst = new LinkedList<>();  
Integer invalidEle = emptyLst.removeLast(); // throws NoSuchElementException  
  • Removes an element at a specified location in the list and shifts any subsequent elements to the left, O(n/2)
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.remove(0); // remove element at index 0 from the list, the list now is {2, 3}  
lst.remove(3); // throws IndexOutOfBoundsException

LinkedList traversal, sorting and conversion

LinkedList traversal

for-each loop a LinkedList aka Enhanced for loop, O(n)

LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
for (Integer ele : lst) {  
    System.out.println(ele);
}

for-index loop a LinkedList, O(n2)

LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
for (int i = 0; i < lst.size(); i++) {  
    Integer ele = lst.get(i);
    System.out.println(ele);
}

LinkedList sorting

  • Sort a list in ascending order
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.sort(Comparator.naturalOrder());  
  • Sort a list in descending order
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
lst.sort(Comparator.reverseOrder());  

Conversion

  • Convert LinkedList<Integer> to Integer[] array
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
Integer[] arr = lst.toArray(new Integer[lst.size()]);  
  • Convert LinkedList<Integer> to int[] array
LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));  
int[] arr = lst.stream().mapToInt(Integer::intValue).toArray();  
  • Convert int[] array to LinkedList<Integer>
int[] arr = {1, 2, 3};  
LinkedList<Integer> lst = new LinkedList<>(Arrays.stream(arr).boxed().collect(Collectors.toList()));  
  • String join LinkedList<String>
LinkedList<String> lst = new LinkedList<>(Arrays.asList("ABC", "ACB"));  
String str = lst.stream().collect(Collectors.joining(", "));  

Notes

  • Collection.stream, Comparator.naturalOrder and Comparator.reverseOrder methods are defined in java.util package and available since Java 8