Core Java

LinkedList In Java

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:

LinkedListArrayList
Uses a doubly-linked list representationUses the concept of dynamic arrays
Implements both List

 

and Deque

interfaces

 

Only implements List

 

interface

Not suitable for random-accessGreat 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 linkedlistInsertion 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 nodeNo 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.

Shubhra Srivastava

Shubhra is a software professional and founder of ProgrammerGirl. She has a great experience with Java/J2EE technologies and frameworks. She loves the amalgam of programming and coffee :)
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button