Java LinkedList

Overview

Java LinkedList are linear data structures where every element is a separate object with data and address object rather than storing elements in contiguous locations. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays.
To store the elements in a linked list we use a doubly linked list which provides a linear data structure and also used to inherit an abstract class and implement list and deque interfaces.

For official documentation on LinkeList usage, Please refer here

LinkedList Representation

Each element in the LinkedList is called the Node. Each Node of the LinkedList contains two items:
1. Content of element.
2. Pointer/Address/Reference to the next node in the LinkedList

Internally Java Linkedlist is implemented using doubly linkedList. Left side node part is used to point to the previous node in the LinkedList. Rightside node part is used to point to next node (Or Element) in the LinkedList.

Constructors

List<String> linkedList1 = new LinkedList<String>();
List<String> linkedList2 = new LinkedList<String>(linkedList1);

Methods

LinkedList implements List and Deque interface, besides add() and addAll() methods you can find addFirst() and addLast(), which adds an element in the beginning or the end, respectively. The methods of LinkedList class are shown below

add​(int index, E element): This method Inserts the specified element at the specified position in this list.

add​(E e): This method Appends the specified element to the end of this list.

addAll​(int index, Collection c): This method Inserts all of the elements in the specified collection into this list, starting at the specified position.

addAll​(Collection c): This method Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.

addFirst​(E e): This method Inserts the specified element at the beginning of this list.

addLast​(E e): This method Appends the specified element to the end of this list.

clear​(): This method removes all of the elements from this list.

clone​(): This method returns a shallow copy of this LinkedList.

contains​(Object o): This method returns true if this list contains the specified element.

descendingIterator​(): This method returns an iterator over the elements in this deque in reverse sequential order.

element​(): This method retrieves, but does not remove, the head (first element) of this list.

get​(int index): This method returns the element at the specified position in this list.

getFirst​(): This method returns the first element in this list.

getLast​(): This method returns the last element in this list.

indexOf​(Object o): This method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

lastIndexOf​(Object o): This method returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.

listIterator​(int index): This method returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.

offer​(E e): This method Adds the specified element as the tail (last element) of this list.

offerFirst​(E e): This method Inserts the specified element at the front of this list.

offerLast​(E e): This method Inserts the specified element at the end of this list.

peek​(): This method retrieves, but does not remove, the head (first element) of this list.

peekFirst​(): This method retrieves, but does not remove, the first element of this list, or returns null if this list is empty.

peekLast​(): This method retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

poll​(): This method retrieves and removes the head (first element) of this list.

pollFirst​(): This method retrieves and removes the first element of this list, or returns null if this list is empty.

pollLast​(): This method retrieves and removes the last element of this list, or returns null if this list is empty.

pop​(): This method Pops an element from the stack represented by this list.

push​(E e): This method Pushes an element onto the stack represented by this list.

remove​(): This method retrieves and removes the head (first element) of this list.

remove​(int index): This method removes the element at the specified position in this list.

remove​(Object o): This method removes the first occurrence of the specified element from this list, if it is present.

removeFirst​(): This method removes and returns the first element from this list.

removeFirstOccurrence​(Object o): This method removes the first occurrence of the specified element in this list (when traversing the list from head to tail).

removeLast​(): This method removes and returns the last element from this list.

removeLastOccurrence​(Object o): This method removes the last occurrence of the specified element in this list (when traversing the list from head to tail).

set​(int index, E element): This method replaces the element at the specified position in this list with the specified element.

size​(): This method returns the number of elements in this list.

spliterator​(): This method Creates a late-binding and fail-fast Spliterator over the elements in this list.

toArray​(): This method returns an array containing all of the elements in this list in proper sequence (from first to last element).toArray​(T[] a): This method returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

LinkedList Add, Retrieve, Remove

public class LinkedListDemo {

	public static void main(String[] args) {
		// Creating a LinkedList
		LinkedList<String> collections = new LinkedList<>();
		// Adding new elements to the end of the LinkedList using add() method.
		collections.add("Linkedlist");
		collections.add("Arraylist");
		collections.add("Hashmap");
		System.out.println("Initial LinkedList : " + collections);
		// Adding an element at the specified position in the LinkedList
		collections.add(3, "Hashset");
		System.out.println("After add(3, \"Hashset\") : " + collections);
		// Adding an element at the beginning of the LinkedList
		collections.addFirst("Abstractlist");
		System.out.println("After addFirst(\"Abstractlist\") : " + collections);
		// Adding an element at the end of the LinkedList (This method is equivalent to
		// the add() method)
		collections.addLast("Linkedhashset");
		System.out.println("After addLast(\"Linkedhashset\") : " + collections);
		// Adding all the elements from an existing collection to the end of the
		// LinkedList
		List<String> collectionInterfaces = new LinkedList<>();
		collectionInterfaces.add("queue");
		collectionInterfaces.add("dequeue");
		collectionInterfaces.addAll(collectionInterfaces);

		// Getting the first element in the LinkedList using getFirst()
		// The getFirst() method throws NoSuchElementException if the LinkedList is
		// empty
		String firstElement = collections.getFirst();
		System.out.println("First element of list is : " + firstElement);

		// Getting the last element in the LinkedList using getLast()
		// The getLast() method throws NoSuchElementException if the LinkedList is empty
		String lastElement = collections.getLast();
		System.out.println("Last element of list is : " + lastElement);

		// Getting the element at a given position in the LinkedList
		String positionElement = collections.get(1);
		System.out.println("Element at position 1 of list : " + positionElement);

		// Remove the first element in the LinkedList
		// Throws NoSuchElementException if the LinkedList is empty
		String element = collections.removeFirst();
		System.out.println("Removed the first element " + element + " => " + collections);

		// Remove the last element in the LinkedList
		// Throws NoSuchElementException if the LinkedList is empty
		element = collections.removeLast();
		System.out.println("Removed the last element " + element + " => " + collections);

		// Remove the first occurrence of the specified element from the LinkedList
		boolean isRemoved = collections.remove("Hashset");
		if (isRemoved) {
			System.out.println("Removed Hashset => " + collections);
		}

		// Remove all the elements that satisfy the given predicate
		collections.removeIf(programmingLanguage -> programmingLanguage.startsWith("Array"));
		System.out.println("Removed elements starting with Array => " + collections);

		// Clear the LinkedList by removing all elements
		collections.clear();
		System.out.println("Cleared the LinkedList => " + collections);

	}

}


Output:
Initial LinkedList : [Linkedlist, Arraylist, Hashmap]
After add(3, "Hashset") : [Linkedlist, Arraylist, Hashmap, Hashset]
After addFirst("Abstractlist") : [Abstractlist, Linkedlist, Arraylist, Hashmap, Hashset]
After addLast("Linkedhashset") : [Abstractlist, Linkedlist, Arraylist, Hashmap, Hashset, Linkedhashset]
First element of list is : Abstractlist
Last element of list is : Linkedhashset
Element at position 1 of list : Linkedlist
Removed the first element Abstractlist => [Linkedlist, Arraylist, Hashmap, Hashset, Linkedhashset]
Removed the last element Linkedhashset => [Linkedlist, Arraylist, Hashmap, Hashset]
Removed Hashset => [Linkedlist, Arraylist, Hashmap]
Removed elements starting with Array => [Linkedlist, Hashmap]
Cleared the LinkedList => []

Important Points

• LinkedList is not synchronized. we can retrieve a synchronized version of it by calling the Collections.synchronizedList method.
  List list = new LinkedList();
list.add("A");
List synlist = Collections.synchronizedList(list);
• Its Iterator and ListIterator iterators are fail-fast (which means that after the iterator’s creation, if the list is modified, a ConcurrentModificationException will be thrown)
• The insertion, addition and removal operations of an item are faster in a LinkedList when compared to ArrayLIst because there is no need to resize an array or update the index when an element is added to some arbitrary position inside the collection, only references in surrounding elements will change.
• A LinkedList consumes more memory than an ArrayList because of every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index.
• The Last element of the LinkedList contains null in the pointer part of the node because it is the end of the List so it doesn’t point to anything.
• Linked list elements don’t need contiguous memory locations because elements are linked with each other using the reference part of the node that contains the address of the next node of the list.

When to use LinkedList over ArrayList in Java?

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.

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>

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 copied
• add(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)

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

Conclusion

ArrayList is usually the default List implementation. However, there are certain use cases where using LinkedList will be a better fit, such as preferences for constant insertion/deletion time (e.g., frequent insertions/deletions/updates), over constant access time and effective memory usage.

Thanks, Note

Thanks for spending your valuable time reading this post. Hope this post taught you something new today. Please share the post if you like it.