LinkedList in Java


Java Java ListViews 1561

LinkedList in Java is a linear data structure that is present in the java.util package. It is similar to ArrayList in Java and we can perform operations like adding an element, removing an element, etc. In this tutorial, we will understand about Java LinkedList.

Java LinkedList

Java LinkedList is a doubly-linked list that can store any type of data. It extends the AbstractList class and implements the List and Deque interfaces. It is called a doubly linked list since it contains a link to the previous node as well as the next successive node. LinkedList contains a collection of nodes and implements a linear data structure. We call each element in the list as a node. We name the first element in the list as head and the last element as a tail.

Features of LinkedList in Java

  • It can contain any type of elements
  • It allows storing duplicate values.
  • Maintains insertion order.
  • It is faster than arrays since there is no shifting of elements during insertion.

Working of a LinkedList in Java

As we discussed, LinkedList uses a double LinkedList. This means each node contains 3 parts: the first part has a reference to the previous node, the second part contains the value of the element and the third part contains the reference to the next node. You can understand this clearly from the pictorial representation.

Java LinkedList

The first element in the LinkedList will have null in the previous node reference and the last element in the LinkedList will have null in the next node reference.

Java LinkedList Hierarchy

Java LinkedList

 

Constructors in LinkedList

Below are the 2 constructors which we can use in Java LinkedList:

LinkedList ConstructorDescription
LinkedList()Creates an empty LinkedList
LinkedList(Collection c)Creates a LinkedList with all elements of the Collection c.

Java LinkedList Methods

Below is the list of commonly used methods for a Java LinkedList.

MethodDescriptionParameter
Boolean add(Element e)Adds the specified element to the end of list.e - the element to be added.
Return value - True
void add(int index, Element e)Adds the element to the specified index. If the index already contains an element, it is shifted to the rightindex- the index at which the element needs to be inserted
e - the element which needs to be inserted
Boolean addAll(Collection c)Adds a collection of specified elements to the list.c - collection of elements to be added
Return value - true
Boolean addAll(int index, Collection c)Adds a collection of elements at the specified index. If the index already contains element, it is subsequently shifted to the rightindex - index at which the elements needs to be added
c - collection of elements to be added
Return value - True
void addFirst(Element e)Inserts an element at the beginning of the linked liste - the element to be inserted
void addLast(Element e)Inserts an element at the end of the liste - the element to be inserted
void clear()Clears all the elements in the list.
Boolean contains(Object o)Checks if the list contains the specified elementReturn value - true if the list contains the element
Boolean containsAll(Collection c)Checks if the list contains all the elements in the collectionReturn value - true if the list contains all the elements
Object clone()Returns a shallow copy of the LinkedList
Iterator descendingIterator()Returns an iterator over elements in the deque in the reverse order
Object element()Returns the first element(head) in the list
Boolean equals(Object o)Compares if the list contains all the specified elements in the exact orderReturn value - true if object elements match with the list
Object getIndex(int index)Retrieves the element at the specified indexindex - the index at which the element that needs to be retrieved
Return value - The element at the specified index
Object getFirst()Returns the first element(head) in the list
Object getLast()Returns the last element(tail) in the list
int indexOf(Object o)Fetches the index of the first occurrence of the specified elemento - The element to be identified
Return value - index value
Boolean isEmpty()Checks if the list is empty or notReturn value - true if list contains no values
Iterator iterator()Retrieves the iterator of list in sequenceReturn value - Iterator
int lastIndexOf(Object o)Retrieves the last occurrence of the specified objecto - Element to be identified
Return value - index value
ListIterator listiterator()Returns an iterator over elements in the list
ListIterator listiterator(int index)Returns an iterator over elements in the list starting from the specified positionindex - start position from which it needs to return the iterator.
Boolean offer(Object e)Inserts the element as the taile - element to be added
Boolean offerFirst(Object e)Inserts the element at the front of the liste - element to be added
Boolean offerLast(Object e)Inserts the element at the end of the liste - element to be added
Object peek()Retrieves the first element of the list(head)Returns null if the list is empty
Object peekFirst()Retrieves the first element of the list(head)Returns null if the list is empty
Object peekLast()Retrieves the last element of the list(tail)Returns null if the list is empty
Object poll()Retrieves and removes the first element of the list(head)Returns null if the list is empty
Object pollFirst()Retrieves and removes the first element of the list(head)Returns null if the list is empty
Object pollLast()Retrieves and removes the last element of the list(tail)Returns null if the list is empty
Object pop()Retrieves or removes the first element from the stack of the list
void push(Object e)Inserts the element to the front of the liste - the element to be added
Object remove()Removes the first element from the list
Object remove(int index)Removes the element at the specified index and moves the remaining element subsequently to the leftindex - index position at which the element has to be removed
Return value - The element that is removed
Boolean remove(Object o)Removes the first occurrence of the specified object from the list if presento - The element that needs to be removed
Return value - true if list contains the element
Boolean removeAll(Collection c)Removes the first occurrence of all the elements in the collection from the list if presentc - collection of elements
Return value - true if the list contains the collection
Object removeFirst()Removes the first element of the list
Boolean removeFirstOccurence(Object e)Removes the first occurrence of the element specified in the liste - the element to be removed
Object removeLast()Removes the last element from the list
Boolean removeLastOccurence(Object e)Removes the last occurrence of the specified element from the liste - the element to be removed
Boolean retainAll(Collection c)Retains all the elements specified in collection in list. Other elements will be removedc - collection of elements that has to be retained
Return value - true if the list changed due to the method called
Object set(int index, Object o)Replaces the element at the specified index with the object passedo - the element to be replaced
index - index of the element
Return value - Returns the element which was previously at the specified index
int size()Fetches the size of the listReturn value - size of the list
List sublist(int fromIndex, int toIndex)Retrieves the part of the list based on start and endIndexfromIndex - position from which the sublist has to be retrieved (included)
toIndex - the index until which the sublist has to be retrieved (excluded)
void sort(Comparator c)Sorts the elements in the list based on the comparator argumentc - compartor which is used to compare the list elements
Object[] toArray()Returns an array of elements in proper sequenceReturn value - Array of all elements in the list in proper sequence
String toString()Returns a String representation of the elements collectionReturn value - String of array elements separated by comma and space and enclosed within []

Create a new LinkedList in Java

We can create a new LinkedList in Java as below:

LinkedList<Type> list_variable = new LinkedList<Type>();

Type – specifies the type of data that you want to store in the list. Eg: String, Integer, etc

list_variable – the variable name of the linked list

Now, let us see different examples of how to use the Java LinkedList methods that we discussed above.

Example: Create and Add elements to the list

Below is an example to create a new LinkedList called names and add elements to the list. We can add an element at a specified index using the add method and passing the index value, add an element at beginning of the list using the addFirst method, and add an element at the end of the list using the addLast method. We can also add a collection of elements to the LinkedList using the addAll method.

import java.util.LinkedList;

public class AddListElements {

  public static void main(String[] args) {
    
    //Create a linked list
    LinkedList<String> names = new LinkedList<String>();
    LinkedList<String> newnames = new LinkedList<String>();
    
    //Add elements to the list
    names.add("Ramesh");
    names.add("Suresh");
    names.add("Ganesh");
    
    System.out.println("List elements: " + names);
    
    //Add element to the specified index
    names.add(1, "Jayesh");
    
    System.out.println("List elements after add at specified index: " + names);
    
    //Add element at the beginning of the list
    names.addFirst("Rupesh");
    
    //Add element at the end of the list
    names.addLast("Mahesh");
    
    System.out.println("List elements after addFirst and addLast: " + names);
    
    //Create a new collection list
    newnames.add("Divya");
    newnames.add("Ramya");
    
    //Add collection to the existing linked list
    names.addAll(newnames);
    
    System.out.println("List elements after adding collection of elements: " + names);
  }

}
List elements: [Ramesh, Suresh, Ganesh]
List elements after add at specified index: [Ramesh, Jayesh, Suresh, Ganesh]
List elements after addFirst and addLast: [Rupesh, Ramesh, Jayesh, Suresh, Ganesh, Mahesh]
List elements after adding collection of elements: [Rupesh, Ramesh, Jayesh, Suresh, Ganesh, Mahesh, Divya, Ramya]

Example: Remove elements from the list

Below is an example to remove elements from the LinkedList. We can remove an element at the specified index, a first element, last element, and collection of elements from the list.

import java.util.LinkedList;

public class RemoveListElements {

  public static void main(String[] args) {
    LinkedList<Integer> numbers = new LinkedList<Integer>();
    LinkedList<Integer> num = new LinkedList<Integer>();
    numbers.add(54);
    numbers.add(64);
    numbers.add(24);
    numbers.add(14);
    numbers.add(84);
    numbers.add(94);
    numbers.add(44);
    
    System.out.println("List elements: " + numbers);
    
    //Removes the head element
    numbers.remove();
    
    System.out.println("List elements after remove: " + numbers);
    
    //Removes the element at the specified index
    numbers.remove(2);
    
    System.out.println("List elements after removing element at specified index: " + numbers);
    
    //Removes the specified element
    numbers.removeFirst();	
    System.out.println("List elements after removing the first element: " + numbers);
    
    //Removes the last element
    numbers.removeLast();
    System.out.println("List elements after removing the last element: " + numbers);
    
    //Create a collection list
    num.add(12);
    num.add(22);
    
    numbers.addAll(num);
    System.out.println("List elements after adding collection: " + numbers);
    
    //Remove a collection from list
    numbers.removeAll(num);
    System.out.println("List elements after removeAll: " + numbers);

  }

}
List elements: [54, 64, 24, 14, 84, 94, 44]
List elements after remove: [64, 24, 14, 84, 94, 44]
List elements after removing element at specified index: [64, 24, 84, 94, 44]
List elements after removing the first element: [24, 84, 94, 44]
List elements after removing the last element: [24, 84, 94]
List elements after adding collection: [24, 84, 94, 12, 22]
List elements after removeAll: [24, 84, 94]

Example: Other methods of the LinkedList

Below is an example of other useful methods in the Java LinkedList. We can insert an element at the beginning of the list using the push method and retrieve the first element using the element method. We can get the element based on a specified index using the get method. To remove and retrieve the first element, we use the pop method. We can replace a specific value based on the index using the set method and get the size of the list using the size method. We can check if a list is empty or not using the isEmpty method.

import java.util.Deque;
import java.util.LinkedList;
public class LinkedListDemo {

  public static void main(String[] args) {
    LinkedList<String> cities = new LinkedList<String>();
    
    cities.add("Chennai");
    cities.add("Bangalore");
    
    //Inserts element at the beginning
    cities.push("Kolkata");
    
    System.out.println(cities);
    
    //Retrieves first element
    System.out.println("Output of element() method: " + cities.element());
    
    System.out.println("Out of get method at specified index 2: " + cities.get(2));
    
    //Retrieves and removes the first element
    System.out.println("Output of pop() method: " + cities.pop());
    System.out.println(cities);
    
    //Check if list is empty
    System.out.println("Is LinkedList empty: " + cities.isEmpty());
    
    //Replaces the element at index 1 with new value
    cities.set(1, "Goa");
    System.out.println("List elements after using set() method: " + cities);
    
    //List size
    System.out.println("Size of the LinkedList: " + cities.size());
  }

}
[Kolkata, Chennai, Bangalore]
Output of element() method: Kolkata
Out of get method at specified index 2: Bangalore
Output of pop() method: Kolkata
[Chennai, Bangalore]
Is LinkedList empty: false
List elements after using set() method: [Chennai, Goa]
Size of the LinkedList: 2

Example: Empty or clear the LinkedList in Java

Below is an example of clearing or emptying LinkedList using the clear() method. We can check if the list is empty using the isEmpty() method. If it returns true, it means the list is empty.

import java.util.LinkedList;

public class ClearLinkedList {

  public static void main(String[] args) {
    LinkedList<String> l = new LinkedList<String>();
    l.add("Java");
    l.add("C");
    l.add("C++");
    
    System.out.println("Contents in the List: " +l);
    
    //Clear the list
    l.clear();
    System.out.println("Is List empty: " + l.isEmpty());
    System.out.println("Contents in the List: " + l);
    
  }

}
Contents in the List: [Java, C, C++]
Is List empty: true
Contents in the List: []

Different ways to iterate through a LinkedList in Java

There are different ways to iterate through elements in a LinkedList. We can use for loop, for each loop, while loop or Iterator to traverse through elements in the list.

Using for loop

In the below example, we can iterate through every element in the list using the for loop. We can retrieve the value using the get method.

import java.util.LinkedList;

public class LinkedListForLoop {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    //Using for loop
    System.out.println("Iterate using for loop:");
    for(int i=0;i<list.size();i++)
      System.out.println(list.get(i));

    
  }

}
Iterate using for loop:
Apple
Banana
Grapes
Pear
Papaya

Using a for-each loop

Below is an example of iterating through LinkedList using for-each loop.

import java.util.LinkedList;

public class LinkedListForEach {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    //Using for each loop
    System.out.println("Iterate using for each loop:");
    for(String fruits : list)
      System.out.println(fruits);

  }

}
Iterate using for each loop:
Apple
Banana
Grapes
Pear
Papaya

Using while loop

We can also use a while loop to traverse through elements in the LinkedList as in the below example. Using the size method, we get the list size, and using the get method, we can retrieve individual elements.

import java.util.LinkedList;

public class LinkedListWhileLoop {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    System.out.println("Iterate using while loop:");
    
    int i=0;
    while(i<list.size())
    {
      System.out.println(list.get(i));
      i++;
    }

  }

}
Iterate using while loop:
Apple
Banana
Grapes
Pear
Papaya

Using iterator and listiterator

In the below example, we use iterator and ListIterator to navigate through individual elements in the list. Using the next method of the iterator, we can get the elements one by one until it reaches the end of the list. We use the hasNext method to check if there is the next element in the list.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListIterator {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    System.out.println("Iterate using iterator:");
    //Using iterator
    Iterator<String> i = list.iterator();
    while(i.hasNext())
      System.out.println(i.next());

    System.out.println("Iterate using listiterator:");
    ListIterator<String> li = list.listIterator();
    while(li.hasNext())
      System.out.println(li.next());
  }

}
Iterate using iterator:
Apple
Banana
Grapes
Pear
Papaya
Iterate using listiterator:
Apple
Banana
Grapes
Pear
Papaya

LinkedList as Deque and Queue

We can use the methods of the Deque and Queue interface since the LinkedList class implements both interfaces. To add elements to the beginning and end of the list, we use addFirst and addLast methods. We use getFirst and getLast methods to retrieve the first and last elements. To remove the first and last element, we use removeFirst and removeLast methods. We use the poll method to retrieve and remove the first element from the list.

import java.util.Deque;
import java.util.LinkedList;

public class DequeLinkedList {

  public static void main(String[] args) {
    Deque<String> lang = new LinkedList<>();
    lang.add("Python");
    lang.add("C");
    lang.add("HTML");
    lang.add("Ruby");
    lang.addFirst("Java");
    lang.addLast("C++");
    
    System.out.println("Elements in the list: " + lang);
    
    System.out.println("First element: " + lang.getFirst());
    System.out.println("Last element: " + lang.getLast());
    
    System.out.println("Remove first element: " + lang.removeFirst());
    System.out.println("Remove last element: " + lang.removeLast());
    
    System.out.println("List elements after removing first and last elements: " + lang);
  
    System.out.println("Head element: " + lang.peek());
    System.out.println("Retrieves the first element: " + lang.peekFirst());
    System.out.println("Retrieves the last element: " + lang.peekLast());
    System.out.println( "Remove and returns the first element: " + lang.poll());
    System.out.println("Remove and returns the first element: " + lang.pollFirst());
    System.out.println("Remove and returns the last element: " + lang.pollLast());
    
    System.out.println("List elements after poll method: " + lang);
    
    lang.offer("C#");
    lang.offerFirst("Java");
    lang.offerLast("C++");
    System.out.println("List elements: " + lang);
    
    
  }

}
Elements in the list: [Java, Python, C, HTML, Ruby, C++]
First element: Java
Last element: C++
Remove first element: Java
Remove last element: C++
List elements after removing first and last elements: [Python, C, HTML, Ruby]
Head element: Python
Retrieves the first element: Python
Retrieves the last element: Ruby
Remove and returns the first element: Python
Remove and returns the first element: C
Remove and returns the last element: Ruby
List elements after poll method: [HTML]
List elements: [Java, HTML, C#, C++]

 

Reference

Translate »