Java LinkedList tutorial with example

Java LinkedList tutorial with example

Java LinkedList used underlying data structure doubly linked list implementation of Java’s List and Deque interfaces. It is part of Java’s collections framework. Here is the class hierarchy of LinkedList –

  • =LinkedList use the underlying data structure is doubly Linkedlist.
  • Java LinkedList is preserved insertion order of elements.
  • Java LinkedList allows duplicates and null values.
  • LinkedList support to store different types of object into list.
  • LinkedList implements Serializable and clonable interfaces  but not RandomAccess interface.
  • Linkedlist is best choice if our frequent operations are inseration and deletion in the middle.
  • LinkedList is the worst choice if our frequent operation is retrieval operation.
  • The LinkedList class implements Queue and Deque interfaces. Therefore, It can also be used as a QueueDeque or Stack.
  • Java LinkedList is not thread-safe. You must explicitly synchronize concurrent modifications to the LinkedList in a multi-threaded environment.

Difference between ArrayList and LinkdeList:

A doubly-linked list consists of a collection of nodes, where each node contains three fields –

  • The data at that node.
  • A pointer/reference to the next node in the list.
  • A pointer/reference to the previous node in the list.

Following is a visual of ArrayList and LinkedList data structures:

ArrayList LinkedList
It is the best choice if our frequent operation is retrieval It is the best choice if our
frequent operation is insertion and deletion
ArraList is the worst choice if our frequent operation is insertion or deletion. LinkedList is the worst choice if our frequent operation is retrieval.
Underlying data structure for ArrayList is resizabe or growable Array. Underlying data structure is Doubly-Linked List.
ArrayList implements RandomAccess interface LinkedList doesn’t implements RandomAccess interface.
ArrayList consumes less memory as compaire to LinkedList A LinkedList consumes more memory 
ArrayList stores the elements sequentially based on their index. LinkedList uses a doubly-linked list to store its elements.
   

Creating a LinkedList

      //create an empty LinkedList Object        
LinkedList  l=new LinkedList();

//Creates an equivalent LinkedList object for given collection.
LinkedList l=new LinkedList(Collection c);

LinkedList Methods :

Usually we can use Linkedlist to implement stacks and queues to provide support for this requirement Linkedlist class defines following specific methods.

  1. add(E e) – This method adds elements to the linked list one after the other
  2. add​(int index, E element)  – This method adds the specified element at the specified position in this list
  3. addFirst(E e) – This method adds the specified element at the beginning of this list
  4. addLast​(E e) –  This method adds the specified element to the end of this list
  5. get​(int index): This method returns the element at the specified position in this list
  6. set​(int index, E element): This method replaces the element at the specified position in this list with the specified element
  7. remove​(int index): This method removes the element at the specified position in this list
  8. removeFirst​(): This method removes and returns the first element from this list
  9. removeLast​(): This method removes and returns the last element from this list

Basically LinkedList is implented from List and collection interface so all methods of collection and List interface are present in LinkedList class.

Following program demonstrate use of addFirst() and addLast() along with addAll() methods in details.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CreateLinkedListDemo {
    public static void main(String[] args) {
        // Creating a LinkedList
        LinkedList<String> players = new LinkedList<>();

        // Adding new elements to the end of the LinkedList using add() method.
        players.add("Virat");
        players.add("Rohit");
        players.add("Rahul");
        players.add("Suresh");

        System.out.println("Initial LinkedList : " + players);
        // Adding an element at the specified position in the LinkedList
        players.add(3, "Manish");
        System.out.println("After add(3, \"Rohit\") : " + players);

        // Adding an element at the beginning of the LinkedList
        players.addFirst("Shikhar");
        System.out.println("After addFirst(\"shikhar\") : " + players);

        // Adding an element at the end of the LinkedList (This method is equivalent to the add() method)
        players.addLast("Ashish");
        System.out.println("After addLast(\"Ashish\") : " + players);

        // Adding all the elements from an existing collection to the end of the LinkedList
        List<String> retiredPlayers = new ArrayList<>();
        retiredPlayers.add("Ganguly");
        retiredPlayers.add("Laxman");

        players.addAll(retiredPlayers);
        System.out.println("After addAll(retiredPlayers) : " + players);
    }
}

output:

Initial LinkedList : [Virat, Rohit, Rahul, Suresh]                      After add(3, "Rohit") : [Virat, Rohit, Rahul, Manish, Suresh]          After addFirst("shikhar") : [Shikhar, Virat, Rohit, Rahul, Manish, Suresh] After addLast("Ashish") : [Shikhar, Virat, Rohit, Rahul, Manish, Suresh, Ashish]                                                                 After addAll(retiredPlayers) : [Shikhar, Virat, Rohit, Rahul, Manish, Suresh, Ashish, Ganguly, Laxman]

Retrieving elements from a LinkedList

The following example shows:

getFirst(): to get the first element in the LinkedList.

getLast(): to get the last element in the LinkedList.

get(int index): to get the element at a given index in the LinkedList.

The following program demonstrate the above methods in details.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CreateLinkedListDemo {
    public static void main(String[] args) {
        // Creating a LinkedList
        LinkedList<String> players = new LinkedList<>();

        // Adding new elements to the end of the LinkedList using add() method.
        players.add("Virat");
        players.add("Rohit");
        players.add("Rahul");
        players.add("Suresh");

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

        // Getting the last element in the LinkedList using getLast()
        // The getLast() method throws NoSuchElementException if the LinkedList is empty
        String lastElement = players.getLast();
        System.out.println("Last player in list : " + lastElement);
        // Getting the element at a given position in the LinkedList
        String thirdPlayer = players.get(2);
        System.out.println("Third player in the List : " + thirdPlayer);
      }
}

Output:

Initial LinkedList : [Virat, Rohit, Rahul, Suresh]                     First player in list : Virat                                             Last player in list : Suresh                                            Third player in the List: Rahul


Removing elements from a LinkedList

The example below shows:

removeFirst(): to remove the first element in the LinkedList.

removeLast() : to remove the last element in the LinkedList.

remove(Object): to remove the first occurrence of a given element in the LinkedList.

removeIf(): to remove all the elements that satisfy a given predicate from the LinkedList.

clear():How to clear the LinkedList completely

The following program shows use of above methods.

import java.util.ArrayList;
 import java.util.LinkedList;
 import java.util.List;
public class CreateLinkedListDemo {
     public static void main(String[] args) {
         // Creating a LinkedList
         LinkedList players = new LinkedList<>();   
 // Adding new elements to the end of the LinkedList using add() method.
    players.add("Virat");
    players.add("Rohit");
    players.add("Rahul");
    players.add("Ajinkya");
    players.add("Rishab");
    players.add("Manish");
    players.add("Suresh");
    players.add("Umesh");

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

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

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

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

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

output:

Initial LinkedList : [Virat, Rohit, Rahul, Ajinkya, Rishab, Manish, Suresh, Umesh]                                                               Removed the first element Virat => [Rohit, Rahul, Ajinkya, Rishab, Manish, Suresh, Umesh]                                                        Removed the last element Umesh => [Rohit, Rahul, Ajinkya, Rishab, Manish, Suresh]
Removed Suresh => [Rohit, Rahul, Ajinkya, Rishab, Manish]
Removed elements starting with R => [Ajinkya, Manish]
Cleared the LinkedList => []

Searching for elements in a LinkedList

The example below shows:

  • contains(): to check if an element exists in a LinkedList.
  • indexOf(): to find the index of the first occurrence of an element in the LinkedList.
  • lastIndexOf(): to find the index of the last occurrence of an element in the LinkedList.

following program demonstrate the above methods in details:

 import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class CreateLinkedListDemo {
public static void main(String[] args) {
// Creating a LinkedList
LinkedList players = new LinkedList<>();
// Adding new elements to the end of the LinkedList using add() method.
players.add("Virat");
players.add("Rohit");
players.add("Rahul");
players.add("Ajinkya");
players.add("Rishab");
players.add("Manish");
players.add("Suresh");
players.add("Umesh");
System.out.println("Initial LinkedList : " + players);
// Check if the LinkedList contains an element
System.out.println("Does Players LinkedList contain \"Rohit\"? :
" + players.contains("Rohit"));
// Find the index of the first occurrence of an element in the LinkedList
System.out.println("indexOf \"Manish\" : " + players.indexOf("Manish"));
System.out.println("indexOf \"Virat\" : " + players.indexOf("Virat"));
// Find the index of the last occurrence of an element in the LinkedList
System.out.println("lastIndexOf \"Rohit\" : " + players.lastIndexOf("Rohit"));
System.out.println("lastIndexOf \"Badani\" : " + players.lastIndexOf("Badani")); }
}

output:

Initial LinkedList : [Virat, Rohit, Rahul, Ajinkya, Rishab, Manish, Suresh, Umesh]
Does Players LinkedList contain "Rohit"? : true
indexOf "Manish" : 5
indexOf "Virat" : 0
lastIndexOf "Rohit" : 1
lastIndexOf "Badani" : -1

Iterating over a LinkedList

The following example shows how to iterate over a LinkedList using

  • Java 8 forEach() and lambda expression.
  • iterator()
  • iterator() and Java 8 forEachRemaining() method
  • descendingIterator()
  • listIterator()
  • simple for-each loop.
 import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
public class CreateLinkedListDemo {
public static void main(String[] args) {
// Creating a LinkedList
LinkedList players = new LinkedList<>();
// Adding new elements to the end of the LinkedList using add() method.
players.add("Virat");
players.add("Rohit");
players.add("Rahul");
players.add("Ajinkya");
players.add("Rishab");
players.add("Manish");
players.add("Suresh");
players.add("Umesh");
System.out.println("Initial LinkedList : " + players);
System.out.println("=== Iterate over a LinkedList using Java 8 forEach and lambda ===");

Players.forEach(name -> {
System.out.println(name);
});
System.out.println("\n=== Iterate over a LinkedList using iterator() ===");
Iterator<String> playersIterator = players.iterator();
while (playersIterator.hasNext()) {
String playerName = playersIterator.next();
System.out.println(playerName);
}
System.out.println("\n=== Iterate over a LinkedList using iterator() and Java 8 forEachRemaining() method ===");
playersIterator = players.iterator();
playersIterator.forEachRemaining(playerName -> {System.out.println(playerName); });
System.out.println("\n=== Iterate over a LinkedList using listIterator() ===");
// ListIterator can be used to iterate over the LinkedList in both forward and backward directions
// In this example, we start from the end of the list and traverse backwards
ListIterator<String> playersListIterator = players.listIterator(players.size());
while (playersListIterator.hasPrevious()) {
String playerName = playersListIterator.previous();
System.out.println(playerName);
}
System.out.println("\n=== Iterate over a LinkedList using simple for-each loop ===");
for(String playerName: players) { System.out.println(playerName);
} }
}

Output:

Initial LinkedList : [Virat, Rohit, Rahul, Ajinkya, Rishab, Manish, Suresh, Umesh]
=== Iterate over a LinkedList using Java 8 forEach and lambda ===
Virat
Rohit
Rahul
Ajinkya
Rishab
Manish
Suresh
Umesh
=== Iterate over a LinkedList using iterator() ===
Virat
Rohit
Rahul
Ajinkya
Rishab
Manish
Suresh
Umesh
=== Iterate over a LinkedList using iterator() and Java 8 forEachRemaining() method ===
Virat
Rohit
Rahul
Ajinkya
Rishab
Manish
Suresh
Umesh
=== Iterate over a LinkedList using listIterator() ===
Umesh
Suresh
Manish
Rishab
Ajinkya
Rahul
Rohit
Virat
=== Iterate over a LinkedList using simple for-each loop ===
Virat
Rohit
Rahul
Ajinkya
Rishab
Manish
Suresh
Umesh

Leave a Reply