Introduction:
A LinkedList is a linear data-structure composed of nodes. In a singly linked list, each node contains data and a reference. Here, the reference-part refers to the next node in the linked list.
In a doubly linked list, on the other hand, we have data and references to both previous and next nodes. Java provides a LinkedList implementation – java.util.LinkedList<T>, which works with a doubly linked list. This class inherits from the AbstractList class and implements the List<T> and Deque<T> interfaces. In this quick tutorial, we’ll learn to work with the LinkedList class in Java.
Construct a LinkedList:
We can instantiate a linked list in Java in one of the following ways:
Java
LinkedList<Integer> intList = new LinkedList<>(); LinkedList<Integer> intList1 = new LinkedList<>(intList);
i.e. this class provides two constructors:
- LinkedList(): creates an empty linked list
- LinkedList(Collection c): creates a linked list and initializes it with the contents of c as its elements
Adding Elements:
To add elements to a LinkedList, we can use the of the flavors of the add() method from the List<T> interface. We can also use addFirst() or the addLast() which adds an element to the beginning or to the end respectively.
Java
intList.add(1); // [1] intList.addFirst(2); // [2, 1] intList.addLast(3); // [2, 1, 3]
Removing Elements:
On the similar lines, to remove an item, we can use remove(index), remove(obj) methods from the List interface. Or else, we can also opt for removeFirst() or a removeLast() method:
Java
int firstElement = intList.removeFirst(); int lastElement = intList.removeLast();
These methods both removes as well as returns the removed value.
Java LinkedList class also provides removeFirstOccurrence(Object obj) and removeLastOccurrence(Object obj) methods to remove the first and last occurrence of a given value respectively. These methods return false if no such value exists in our list.
boolean removed = intList.removeFirstOccurrence(1);
Querying Elements:
We have getFirst() and getLast() methods in LinkedList class, to query the first or the last element of our linked list:
Java
int firstElement = intList.getFirst(); int lastElement = intList.getLast();
Since it’s a doubly-linked list implementation, both getFirst() and getLast() are constant-time operations.
If we know the index of the element to be retrieved, we can also use the get(int index) method of the List interface:
Java
int elementAtIndex1 = intList.get(1);
Iterating over a LinkedList:
We’ll iterate over a linked list, just like any other form of a list:
Java
//Using a for loop
for(int num : intList) {
System.out.println(num);
}
//Using iterator
ListIterator itr = intList.listIterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
//Using forEach construct
intList.forEach( value -> System.out.println(value); );
LinkedList vs ArrayList:
Let’s outline the differences between the Java LinkedList and ArrayList classes:
| LinkedList | ArrayList |
|---|---|
| Uses a doubly-linked list representation | Uses the concept of dynamic arrays |
| Implements both List
and Deque interfaces
|
Only implements List
interface |
| Not suitable for random-access | Great for random-access. If we know the index, it takes only O(1) time for retrieval |
| O(1) insertions/removals at the beginning and end of a java linkedlist | Insertion of elements in an ArrayList might lead to resizing of the backing array, and so has an amortized cost of O(n). Also, insertion at the beginning of an ArrayList will need us shift all elements to the right by one position. |
| Memory overhead of storing references to the previous and the next node | No additional information needs to be stored |
Feel free to learn more about ArrayList in this article. All the methods in the ArrayList class inherited from the List<T> interface are also available in the Java LinkedList.
Conclusion:
In this quick tutorial, we explored some of the most popular methods of Java LinkedList class. We also covered the difference between a Java ArrayList and LinkedList.
Be the First to comment.
|
Published on Java Code Geeks with permission by Shubhra Srivastava, partner at our JCG program. See the original article here: LinkedList In Java Opinions expressed by Java Code Geeks contributors are their own. |
