LinkedList in Java

LinkedList in Java is a doubly-linked list implementation of the List and Deque interfaces and it is a part of the Collection framework.

Java LinkedList is a class that extends AbstractSequentialList and implements List and Deque interface.

Let’ see the implementation in Java:

  public class LinkedList<E> extends AbstractSequentialList<E>
      implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

  }

Java LinkedList can also be used as List, Queue, or Deque because it implements these interfaces.

List<String> ex = new LinkedList<>();

Queue<String> ex1 = new LinkedList<>();

Deque<String> ex2 = new LinkedList<>();

1. LinkedList Features:

  • It is a doubly-linked list implementation.
  • It maintains insertion order.
  • It is non-synchronized i.e fast and not thread-safe.
  • It allows NULL as well as duplicates elements.
  • Elements can be added dynamically at run time.
  • It contains the address of the next and previous node.
  • Elements are not stored in a contiguous manner.

2. LinkedList Working:

LinkedList is a linear data structure where elements are connected one after another.

Each Element inside LinkedList is known as a node. Each node contains the actual value and memory address of another node.

Because elements are not inserted in a contiguous location like an array, they’re separated in the memory and connected with each other using pointers (memory address).

This way every node can connect to other nodes using the memory reference.

Java LinkedList is of three types:

  1. Singly LinkedList
  2. Doubly LinkedList
  3. Circular LinkedList

2.1 Singly LinkedList

In singly LinkedList, the next node reference is stored that means only forward navigation is possible.

2.2 Doubly LinkedList

In doubly LinkedList, along with value, reference is stored for the previous node, and the next node that means forward & backward navigation is possible.

2.3 Circular LinkedList

In the circular LinkedList, the previous and next node reference is stored. Additionally, the last node contains the address of the first node that makes it a circular linked list.

3. Why To Use LinkedList in Java?

As you all know, arrays are of fixed size and we also need to define size while declaring an array that means we should be confident enough about our data set and its quantity.

Think of a scenario where you don’t know the size of the data you’re going to store. Then What?

Then you must use classes from Collection interface such as LinkedList as your data structure.

LinkedList provides you many benefits such as singly, doubly, and circular LinkedList but it also has a memory overhead because each node contains the actual value and addresses of previous and next node.

Suppose, if you want to add some value in the middle of your array then it’s a pretty expensive operation because it’s of fixed size and you need to shift all the elements.

But in the case of LinkedList, you can easily insert your data and point the memory reference from the newly inserted node.

LinkedList is also performance-wise optimized in front of ArrayList because while doing any modification you just need to update the memory reference instead of copying the whole object into another and modifying it.

4. Java LinkedList Methods:

Here, I have mentioned a brief description of LinkedList methods in Java. Examples of all methods will be covered in a separate tutorial.

NameDescription
boolean add(E e)It is used to append the specified element to the end of a list.
void add(int index, E element)It is used to insert the specified element at the specified index in a list.
boolean addAll(Collection<? extends E> c)It is used to append all of the elements to the end of this list.
void addFirst(E e)It is used to insert the given element at the beginning of a list.
void addLast(E e)It is used to append the given element to the end of a list.
void clear()It is used to remove all the elements from a list.
Object clone()It is used to return a shallow copy of an ArrayList.
boolean contains(Object o)It is used to return true if a list contains a specified element.
E element()It is used to retrieve the first element of a list.
E get(int index)It is used to return the element at the specified position in a list.
E getFirst()It is used to return the first element in a list.
E getLast()It is used to return the last element in a list.
int indexOf(Object o)It is used to return the index in a list of the first occurrence of the specified element, or -1 if the list does not contain any element.
int lastIndexOf(Object o)It is used to return the index in a list of the last occurrence of the specified element, or -1 if the list does not contain any element.
ListIterator<E> listIterator(int index)It is used to return a list-iterator of the elements in proper sequence, starting at the specified position in the list.
boolean offer(E e)It is used to add the specified element as the last element of a list.
boolean offerFirst(E e)It inserts the specified element at the front of a list.
boolean offerLast(E e)It inserts the specified element at the end of a list.
E peek()It retrieves the first element of a list
E peekFirst()It retrieves the first element of a list or returns null if a list is empty.
E peekLast()It retrieves the last element of a list or returns null if a list is empty.
E poll()It retrieves and removes the first element of a list.
E pollFirst()It retrieves and removes the first element of a list, or returns null if a list is empty.
E pollLast()It retrieves and removes the last element of a list, or returns null if a list is empty.
E pop()It pops an element from the stack represented by a list.
void push(E e)It pushes an element onto the stack represented by a list.
E remove()It is used to retrieve and removes the first element of a list.
E remove(int index)It is used to remove the element at the specified position in a list.
boolean remove(Object o)It is used to remove the first occurrence of the specified element in a list.
E removeFirst()It removes and returns the first element from a list.
boolean removeFirstOccurrence(Object o)It is used to remove the first occurrence of the specified element in a list.
E removeLast()It removes and returns the last element from a list.
boolean removeLastOccurrence(Object o)It removes the last occurrence of the specified element in a list.
E set(int index, E element)It replaces the element at the specified position in a list with the specified element.
Object[] toArray()It is used to return an array containing all the elements.
int size()It is used to return the number of elements in a list.

5. Examples:

Let’s see some linkedlist programs of above mentioned methods:

5.1 Adding and Printing Elements:

public class JavaCollectionExample {

  public static void main(String[] args) {

    LinkedList<String> listObj = new LinkedList<>();

    // adding elements
    listObj.add("A");
    listObj.add("B");
    listObj.add("C");
    listObj.add("D");
    listObj.add("E");

    // printing list using forEach loop + Java 8
    listObj.forEach(System.out::println);

  }

}

5.2 Remove Elements:

Let’s see how to remove elements from list using removeFirst(), removeLast(), removeFirstOccurrence(), and removeIf() methods.

import java.util.LinkedList;

public class JavaCollectionExample {

  public static void main(String[] args) {

    LinkedList<String> listObj = new LinkedList<>();

    // adding elements
    listObj.add("A");
    listObj.add("B");
    listObj.add("C");
    listObj.add("D");
    listObj.add("D");
    listObj.add("E");

    // removing first element
    listObj.removeFirst();
    System.out.println("After removeFirst() method " + listObj);

    // removing first occurrence of the element
    listObj.removeFirstOccurrence("D");
    System.out.println("After removeFirstOccurrence() method " + listObj);

    // removing last element
    listObj.removeLast();
    System.out.println("After removeLast() method " + listObj);

    // removing element if condition matches
    listObj.removeIf(x -> x.equals("B"));
    System.out.println("After removeIf() method " + listObj);

  }

}

Output:

After removeFirst() method [B, C, D, D, E]
After removeFirstOccurrence() method [B, C, D, E]
After removeLast() method [B, C, D]
After removeIf() method [C, D]

5.3 Using peekFirst(), peekLast(), pollFirst(), pollLast():

import java.util.LinkedList;

public class JavaCollectionExample {

  public static void main(String[] args) {

    LinkedList<String> listObj = new LinkedList<>();

    // adding elements
    listObj.add("A");
    listObj.add("B");
    listObj.add("C");
    listObj.add("D");
    listObj.add("E");

    // printing first element
    System.out.println("First Element of List " + listObj.peekFirst());

    // printing last element
    System.out.println("Last Element of List " + listObj.peekLast());

    // retrieving and removing the first element
    System.out.println("Removing " + listObj.pollFirst() + " Final Result " + listObj);

    // retrieving and removing the last element
    System.out.println("Removing " + listObj.pollLast() + " Final Result " + listObj);

  }

}

Output:

First Element of List A
Last Element of List E
Removing A Final Result [B, C, D, E]
Removing E Final Result [B, C, D]

I hope you’ve learned What is LinkedList in Java? Ask your questions in comment section.

Happy Learning!

ArrayList in Java

Map Interface In Java