Tuesday, May 9, 2023

How to find First and Last element in LinkedList Java? Doubly linked list Example

In this article, you will learn how to get the first and last element of a linked list with the help of getFirst() and getLast() of the LinkedList class. If you have programming or even gone to a computer science course you probably know what is a linked list? It's a data structure that allows you to store objects in such a way that you can don't need a big chunk of contiguous memory like another popular data structure array. It works perfectly even if you have a fragmented heap. LinkedList is Java's implementation of this fundamental data structure. 

There are two types of linked list, singly and doubly linked list, and Java's LinkedList is a doubly linked list. If you are wondering what is difference between a singly and doubly linked list, well in singly linked list you can traverse only in one direction from head to tail, or from first to last element because every node has address of only next node. 

While in a doubly linked list, every node has reference to both previous and next node, thus allows you to traverse in both directions, from head to tail and backward. You can verify this by yourself by looking at the code of java.util.LinkedList in Eclipse, just use shortcut Ctrl + T and type the name, if you have added Java source code in Eclipse, it will open the class. 

You will find that LinkedList class in Java has a private static class called Node, which has reference to both the previous and next node.

For those, who can't see the code of LinkedList, here is the snippet of the Node class.


private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

You can clearly see that Node has reference to two other nodes, which makes LinkedList a doubly linked list and allows you to traverse in both direction, from first to last and vice-versa.


Getting First and the Last Element of LinkedList in Java - Example

Here is our sample Java program to find the first and last object from LinkedList in Java. We will be using Java's Collection framework API to get our done. In this example, I have created a  linked list of String to store different programming languages.  You can store objects into LinkedList by calling add() method. 

This method encapsulates data into a private static nested class Node, which represent a node in a doubly linked list and keep reference of both previous and next node in linked list. Also this method adds the new element at the end of linked list i.e. on the tail, which means last method you add into linked list will be the last element in the LinkedList itself. 

The angle bracket you see while creating instance of LinkedList is known as diamond operator, added backed in Java 7 and help you to avoid declaring types on right hand side of assignment operator as well. The compiler can now infer it by looking at left-hand side. You should use it every time you are using JDK 1.7 to reduce at least a little bit of boiler plate coding.


Doubly linked list in Java



Now coming back to our task, how do we retrieve the first and last element from linked list? Of course we don't know which elements are added, unlike this example, where we know. 

Since a linked list is a sequential data structure, by looking at how you add elements you can guess which one is first and which one is last, but this example is more for situation, where you receive a linked list from other part of your application and need to find first and last element.

LinkedList has getFirst() and getLast() method to retrieve first and last element from LinkedList in Java. I would have liked just first() and last() method but anyway.

import java.util.LinkedList;

/**
 * Java program to find first and last element of linked list in Java.
 */
public class LinkedListDemo{

    public static void main(String args[]) {

        LinkedList programmingLanguages = new LinkedList<>();
        programmingLanguages.add("Java");
        programmingLanguages.add("Perl");
        programmingLanguages.add("Ruby");
        programmingLanguages.add("Python");
        programmingLanguages.add("C");
        programmingLanguages.add("C++");
        programmingLanguages.add("C#");
        programmingLanguages.add("Scala");
       
        // getting first element of linked list in Java
        String first = programmingLanguages.getFirst();
        System.out.printf("First element of LinkedList is : %s %n", first);
     
        // getting last element from linked list in Java
        String last = programmingLanguages.getLast();
        System.out.printf("Last element of LinkedList is  : %s %n", last);
    }
 
}

Output:
First element of LinkedList is : Java
Last element of LinkedList is  : Scala

That's all about how to find first and last node of a linked list in Java. Remember, Java's implementation of linked list data structure is a doubly linked list, which means each node has reference to both previous and next node. You can iterate over LinkedList but iterator doesn't guarantee any order, so beware of that as well.

If you are hungry to know more about linked list in Java, check out these amazing articles :
  • What is difference between LinkedList and ArrayList in Java? (answer)
  • How to find middle element of linked list in Java? (solution)
  • What is difference between array and linked list in data structure? (answer)
  • How to find if linked list has loop in it? (solution)
  • How to find length of singly linked list in Java? (solution)
  • Difference between List, Set and Map in Java? (answer)
  • When to use LinkedList over ArrayList in Java? (answer)

3 comments:

  1. What about:

    public E getFirst() {
    final Node f = first;
    if (f == null)
    throw new NoSuchElementException();
    return f.item;
    }

    why this line is needed:
    final Node f = first;
    ? This is taekn directly from JDK. What do you think?

    ReplyDelete
  2. Hi,

    What do you mean by the statement "You can iterate over LinkedList but iterator doesn't guarantee any order"?
    Does the next() method of iterator not iterate over the linked list sequentially?

    ReplyDelete
  3. Respected Sir,

    One Correction Please,

    LinkedList class does not contain any Node class. It is Entry class which you have pointed out.

    Thanks,
    Ravi

    ReplyDelete