Java comes with its own implementation of Linked List. The Java Linked List is actually a doubly-linked list implementation of the List and Dequeue interfaces.
1 – How to use the Java Linked List
1.1 – Create a Linked List
We can create a new Java Linked List as below:
LinkedList<Object> linkedList = new LinkedList<>();
As you can see, the Java Linked List has support for Generics. Therefore, we can create Linked List of any data type such as Integer, String or even another user-defined class.
1.2 – Add an Element
The Java Linked List implements List and Deque interfaces. As a result, we can use add() and addAll() methods along with addFirst() and addLast() as well.
linkedList.add(3);
linkedList.addFirst(4);
linkedList.addLast(5);
After the above operations, the linked list will have elements as [4, 3, 5].
The addAll() method takes as input another data structure that extends the Java Collection class. For example, we can create a second linked list and add it to the first linked list using addAll().
LinkedList<Object> linkedList2 = new LinkedList<>();
linkedList2.add(2);
linkedList2.add(6);
linkedList.addAll(linkedList2);
1.3 – Removing an Element
To remove an element, we can use removeFirst() and removeLast().
Also, there are convenient methods such as removeFirstOccurrence() and removeLastOccurrence() that return boolean as true if the collection contained the element.
2 – Important Features
Below are some of the most important features:
- While retrieving an element based on index, the operation will traverse through the list from head or tail depending on whichever side is closer to the index.
- The Java Linked List is not synchronized.
- Each element keeps a reference to the previous and the next node.
- It maintains the insertion order.
3 – Comparing Linked List with ArrayList
Both Linked List and ArrayList use the List interface. Though they might seem similar but there are many underlying differences:
- ArrayLists are index-based structures and are backed by an array. In other words, ArrayLists provide random access to its elements in constant time complexity i.e. O(1). On the other hand, a Linked List stores its data as elements where every element is linked to its next element. Hence, the search operation takes O(n) or linear time complexity.
- In terms of operations, insertion and removal of elements in a Linked List is faster because there is no need to resize the array or update the index. We only need to update the references to the surrounding elements.
- Linked Lists consume more memory than an Array List. This is because every node in Linked Lists stores references to its previous and next node.
4 – Queue Operations of Java Linked List
Since Java Linked List also extends the Deque interface, it also exhibits some queue operations.
linkedList.poll();
linkedList.pop();
The above methods retrieves and removes the first element from the Linked List. Pop throws NoSuchElementException in case the list is empty. Poll return null in such a case.
We can also push an element to the top of the list.
linkedList.push(8);
With this, we have successfully explored the features of Java Linked Lists. We have also compared the same with ArrayList which is another popular data structure. Ultimately, the question of which one to use depends on the use-case and time complexity requirements.
In case of any questions or queries, please feel free to write in the comment section below.
0 Comments