Arrays are widely used in Java to store a fixed size collection of elements! However, they cannot be used to store dynamic or mixed (in term of data type) list of elements because they are static data structures and they are not dynamically resizable.

In this article, we will take a closer look at another data structure called Linked list that addresses some of the limitations and issues raised by arrays.

I think that understanding how linked lists work internally will help you understanding more complex data structures! So, how to implement a linked list in java ? Read all the details to find out :)

What is a linked list in Java ?

Without any doubt, Linked List is one of the most used data structure in computer programming. It is a dynamic data structure that describes a collection of data where all elements are linked together!

So basically, each element of the list is linked to the next one!

Confused? Let me explain: Like a chain, each element is linked to its neighbors. Since a linkedlist is not a loop, it must end somewhere! So, just after the last element, we find null reference to indicate the end of the list.

Linked list data structure

Each element of a linked list is called a node, it holds two items - the actual data and a reference to the next node! The head defines the entry point into the linked list!

Linked list implementation in Java

As I mentioned earlier, a linked list is a dynamic data structure where all the elements are organized linearly! Linked lists and arrays are similar since they both can be used to store linear data!

However, unlike arrays, linked list elements are not stored in sequential memory locations, they are all linked in a linear way!

How to create a linked list in Java?

There are several ways to represent a linkedlist in Java. The most basic idea is to use node chaining concept:

  • Each node contains an element of the list!

  • Each node contains data (ou can an int value to keep things simple).

  • Each node holds a reference to the next element, except the last one in the list (which contains a null reference).

  • The list gives access to the first node, the rest of elements are accessible by moving from one node to another, according to their sequence.

In Java, an object is represented by a reference to the memory area where its variables and methods are stored.

Since a linked list is defined by a reference to a node (the first one in the list), then the simplest solution to implement linked list in Java is by using the node class!

    
        public class MylinkedlistNode {
            private int value;
            private MylinkedlistNode next;
            public MylinkedlistNode(int value, MylinkedlistNode next) { 
                this.value = value;
                this.next = next;
            }
        }
    

However, this representation works only for non-empty lists (MylinkedlistNode must contain at least one value).

In Java, Linked lists are usually implemented using two classes: a class for the nodes, and a class for the list itself, which contains a reference of Node class type.

Node structure

Defining the node is the starting point to implement a linked list in java! You can imagine a node as a simple box that contain the actual data (int value in our example) and a link to another node! After all, a linked list is nothing but a group of nodes!

From technical point of view, you can use nested class concept to create your node inside your list class!

Java allows to define a class - inner class - within another class - outer class - , it is is a good practice to logically group classes that are only used in one place for the same purpose!

    
        // Linked list implementation 
        public class MylinkedlistImp {
            private Node node;
            // Node class 
            class Node { 
                private int value;  // data
                private Node next;  // link to next node
                public Node(int value) { 
                    this.value = value;
                    this.next = null; 
                }
                public Node(int value, Node next) { 
                    this.value = value;
                    this.next = next; 
                }
            }
        }
    

Singly linked lists

Singly linked list is the most basic form of a linked list where each node contains the content and a single reference to the next node. It does not have a reference link to the previous node.

How to implement singly linked list in java ?

In order to implement a single linked list in Java, you need two classes: a class to represent the nodes and a class which holds an instance of node class and other methods for data manipulation.

The example below shows how to create a singly linked list implementation in Java programming language:

    
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
        }
    

Linked list basic operations

  • isEmpty: to check if the linked list is empty.

  • contains(T x): checks if the linkedlist contains the specified element.

  • toString: returns the string representation of the linked list.

    
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public boolean isEmpty(){
                return head == null;
            }
            public String toString(){
                StringBuffer result = new StringBuffer();
                for(Object x : this)
                    result.append(x + " ");
                return result.toString();
            }
            public boolean contains(T x){
                for(T tmp : this)
                    if(tmp.equals(x)) return true;
                return false;
            }
        }
    
  • get(int pos): returns the element at the specified position.

  • getFirst: returns the first element of the linked list.

  • getLast: returns the last element of the linkelist.

    
        //Example of linked list implementation in Java
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public T get(int pos){
                if (head == null) throw new IndexOutOfBoundsException();
                Node<T> tmp = head;
                for (int k = 0; k < pos; k++) tmp = tmp.next;
                if( tmp == null) throw new IndexOutOfBoundsException();
                return tmp.data;
            }
            public T getFirst(){
                if (head == null) throw new NoSuchElementException();
                return tmp.data;
            }
            public T getLast(){
                if (head == null) throw new NoSuchElementException();
                Node<T> tmp = head;
                while(tmp.next != null) tmp = tmp.next;
                return tmp.data;
            }
        }
    
  • addFirst(T item): add new node at the beginning of the list.

  • addLast(T item): add new node to the end of the list.

  • insertAfter(T key, T toInsert): add new element after the node containing the specified key.

  • insertBefore(T key, T toInsert): add new element before the node containing the specified key.

    
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public void addFirst(T item){
                head = new Node<T>(item, head);
            }
            public void addLast(T item){
                if( head == null)
                    addFirst(item);
                else{
                    Node<T> tmp = head;
                    while(tmp.next != null) tmp = tmp.next;
                    tmp.next = new Node<T>(item, null);
                }
            }
            public void insertAfter(T key, T toInsert){
                Node<T> tmp = head;
                while(tmp != null && !tmp.data.equals(key)) tmp = tmp.next;
                if(tmp != null)
                    tmp.next = new Node<T>(toInsert, tmp.next);
            }
            public void insertBefore(T key, T toInsert){
                if(head == null) return;
                if(head.data.equals(key)){
                    addFirst(toInsert);
                    return;
                }
                Node<T> prev = null;
                Node<T> cur = head;
                while(cur != null && !cur.data.equals(key))
                {
                    prev = cur;
                    cur = cur.next;
                }
                if(cur != null)
                    prev.next = new Node<T>(toInsert, cur);
            }
        }
    
  • removeFirst: to remove and return the first element in the list.

  • remove: removes the first occurrence of the specified element.

  • clear: to remove all elements from the linked list.

    
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public T removeFirst(){
                T tmp = getFirst();
                head = head.next;
                return tmp;
            }
            public void remove(T key){
                if(head == null)
                    throw new RuntimeException("cannot delete");
                if( head.data.equals(key) )
                {
                    head = head.next;
                    return;
                }
                Node<T> cur  = head;
                Node<T> prev = null;
                while(cur != null && !cur.data.equals(key) )
                {
                    prev = cur;
                    cur = cur.next;
                }
                if(cur == null)
                    throw new RuntimeException("cannot delete");
                prev.next = cur.next;
            }
            public void clear(){
                head = null;
            }
        }
    

Reversing a singly linked list

To reverse a singly linked list in java, you have to change the current node’s next link to point to its previous element. To do that you need 3 references.

  • previous (n-1): points to the previous element.

  • current (n): represents the current node.

  • next (n+1): points to the next element.

(n-1) –> (n) –> (n+1) –> …

Since a singly linkedlist’s node does not have a reference link to the previous node, then you must store its previous element somewhere. You can do that using this simple statement:

    
        current.next = previous;
    

You also need a third reference to store the next node before changing the references to keep track on next elements.

The logic of reversing a linked list in Java is very simple :

  • Loop while current element is NOT null.

  • Store the next of the current element in enext element.

  • Set the next of the current Node to the previous element.

  • Set previous to current.

  • Set the current element to enext element.

    
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public void reverseList(){
                Node<T> current = head;
                Node<T> previous = null;
                Node<T> enext = null;
                while(current != null) {
                   enext = current.next;
                   current.next = previous;
                   previous = current; 
                   current = enext;
                }
                head = previous;
            }
            public SinglyLinkedList<T> reverseList2(){
                LinkedList<T> list = new LinkedList<T>();
                Node<T> tmp = head;
                while(tmp != null){
                    list.addFirst( tmp.data );
                    tmp = tmp.next;
                }
                return list;
            }
        }
    

Cloning singly linked lists

Cloning in java, refers to the process of creating an exact copy from an original object. The basic idea of cloning a linked list is to iterate through it in order to create a new copy which holds the same elements!

Let’s see together how to clone a linked list in Java:

  • Create a new instance of singly linked list implementation.

  • Loop through the original linked list.

  • Invoke addLast() method to add each element to the cloned linked list.

    
        //Example of Singly linked list implementation in Java
        public class SinglyLinkedList<T> implements Iterable<T>{
            private Node<T> head;
            public SinglyLinkedList() { 
                this.head = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                public Node(T data, Node<T> next){
                    this.data = data;
                    this.next = next;
                }
            }
            public  SinglyLinkedList<T> clone1(){
                SinglyLinkedList clonedlinkedlist = new SinglyLinkedList();
                Node tmp = head;
                while(tmp != null){
                    clonedlinkedlist.addLast( tmp.data );
                    tmp = tmp.next;
                }
                return clonedlinkedlist;
            }
            public  SinglyLinkedList<T> clone2(){
                SinglyLinkedList clonedlinkedlist2 = new SinglyLinkedList();
                Node tmp = head;
                if(head==null) return null;
                clonedlinkedlist2.head = new Node(head.data, null);
                Node tmpTwin = clonedlinkedlist2.head;
                while(tmp.next != null){
                    tmp = tmp.next;
                    tmpTwin.next = new Node(tmp.data, null);
                    tmpTwin = tmpTwin.next;
                }
                return clonedlinkedlist2;
            }
        }
    

Doubly linked list in java

Doubly linked lists are data structures similar to singly linked lists. However, compared to a singly linked list, a Doubly linked list contains an extra pointer! Each node has another reference to the previous node.

Doubly linked list data structure

Java doubly linked list implementation

As we saw in the previous section, a single linked list has only one reference link to the next node, so to implement a basic doubly linked list in Java, you need just to add another pointer to the previous node!

Each node of a doubly linked list holds three variables:

  • variable holding the data.

  • reference storing a link to the next node.

  • reference storing a link to the previous node.

    
        public class DoublyLinkedList<T>{
            private Node<T> head;
            private Node<T> tail;
            private static class Node<T>{
                private T data;
                private Node<T> next;
                private Node<T> previous;
            }
        }
    

As you can see, doubly linked list has one more extra link pointing to the previous node named in our example : previous.

Doubly linked list java add method

There are many approaches that you can use to add new nodes into a doubly linked list in java, let’s see together how to implement these different methods :

  • addFirst : This method inserts a new item to the head of the linkedlist! To achieve that, you need to set the previous node to null and make the new node the new head of the linked list.

  • addLast : This method inserts a new element at the end of the list! When you add a node to the tail, you need to shift everything to the left!

  • add : adds a new element at specific position in the linkedlist!

  • iterate : iterates forwards over the linked list.

  • size : used to get the size of the list.

Below example shows how to add a new element to a java doubly linked list implementation:

    
        //Example of how to implement linked list in Java
        public class DoublyLinkedList<T>{
            private Node<T> head;
            private Node<T> tail;
            public DoublyLinkedList() { 
                this.head = null;
                this.tail = null;
            }
            private static class Node<T>{
                private T data;
                private Node<T> next;
                private Node<T> previous;
                public Node(T data, Node<T> next, Node<T> previous){
                    this.data = data;
                    this.next = next;
                    this.previous = previous;
                }
                public Node(T data){
                    this.data = data;
                }
            }
            // add new element at the beginning of the list
            public void addFirst(T data) {
                Node<T> tmp = new Node<T>(data, head, null);
                if(head != null ) {
                    head.previous = tmp;
                }
                head = tmp;
                if(tail == null) { 
                    tail = tmp;
                }
            }
            // add new element at the end of the doubly linked list
            public void addLast(T data) {
                Node<T> tmp = new Node<T>(data, null, tail);
                if(tail != null) {
                    tail.next = tmp;
                }
                tail = tmp;
                if(head == null) { 
                    head = tmp;
                }
            }
            public void add(int index, T data) {
                if (index < 0 || index > this.size()) 
                    throw new IllegalArgumentException();
                Node<T> newNode = new Node<T>(data);
                if (head == null) {
                    head = newNode;
                    tail = newNode;
                }
                else if (index == 0) {
                    this.addFirst(data);
                }
                else if (index == this.size()) {
                    this.addLast(data);
                }
                else {
                    Node<T> nodeRef = head;
                    for (int i = 1; i < index; i++) 
                        nodeRef = nodeRef.next;
                    newNode.next = nodeRef.next;
                    nodeRef.next = newNode;
                    newNode.previous = nodeRef;
                    newNode.next.previous = newNode;
                }
            }
            public void iterate(){
                Node<T> tmp = head;
                while(tmp != null){
                    System.out.print(tmp.data+" ");
                    tmp = tmp.next;
                }
            }
            public int size(){
                int lsize = 0;
                Node<T> tmp = head;
                while(tmp != null){
                    lsize++;
                    tmp = tmp.next;
                }
                return lsize;
            }
            public static void main(String[] args) {
                DoublyLinkedList<String> doublylinkedlistimp = new DoublyLinkedList<String>();
                doublylinkedlistimp.addFirst("Doubly");
                doublylinkedlistimp.addFirst("Hello");
                doublylinkedlistimp.iterate();
                System.out.println("");
                doublylinkedlistimp.addLast("Linked");
                doublylinkedlistimp.addLast("List");
                doublylinkedlistimp.iterate();
                System.out.println("");
                doublylinkedlistimp.add(4,"Implementation");
                doublylinkedlistimp.iterate();
            }
        }
    

For the above example, the output will be:

Hello Doubly 
Hello Doubly Linked List 
Hello Doubly Linked List Implementation 

Java LinkedList class

LinkedList class is a doubly linked list implementation of List and Deque interfaces. It belongs to Java’s collection api.

It extends AbstractSequentialList class and implements all methods of List interface! It implements also Deque interface from Java 6.

Here is the hierarchy of LinkedList class in Java :

Linkedlist java class diagram

The LinkedList class has several constructors:

Constructor Function
LinkedList() Create a new empty LinkedList instance
LinkedList(Collection<? extends E> c) Create a new instance containing the elements of the collection provided as parameter sorted in the order obtained by its Iterator

Following are some important key points to note about LinkedList in Java:

  • Java LinkedList maintains the insertion order of the elements.

  • LinkedList is a List, so it can have duplicate values.

  • Linked list accepts all elements including NULL value.

  • LinkedList class implements also Deque interface. So, it can also be used as a Queue.

  • LinkedList is not thread-safe.

LinkedList vs ArrayList

They both implement List interface. They are very similar as they both can store data and maintain insertion order!

The main difference between LinkedList and ArrayList lies in the way they are implemented: ArrayList is implemented as a resizable array, however LinkedList is implemented as a double linked list.

Following are some other differences between LinkedList and ArrayList classes:

  • Insertion and removal are faster and easier with LinkedList than ArrayList.

  • ArrayList class is a list only, however LinkedList can act as a list and a queue.

  • You can access an element in an ArrayList faster than in a LinkedList.

  • Memory consumption is high when using LinkedList compared to ArrayList.

LinkedList vs ArrayList

How to add new element to LinkedList in Java ?

The following example shows how to add new elements to a linkedlist using addFirst() and addLast() methods of the Deque interface.

    
        import java.util.LinkedList;
        public class AddToLinkedList {
            public static void main(String[] args) {
                LinkedList<String> languages = new LinkedList<String>();
                languages.add("PHP");
                languages.add("Java");
                languages.add("C++");
                languages.add("Python");
                // Adding an element at the specified position in the LinkedList
                languages.add(3, "Kotlin");
                // Adding an element at the beginning of the LinkedList
                languages.addFirst("GoLang");
                // Adding an element at the end of the LinkedList
                languages.addLast("Ruby");
                System.out.println("Programing Language List  : " + languages);
            }
        }
    

How to retrieve element from a LinkedList ?

To retrieve an element from a linkedlist, you can use one of the following methods:

  • getFirst(): returns the first element in the LinkedList.

  • getLast() : gets the last element in the LinkedList.

  • get(int index) : retrieves the element at a given index.

    
        import java.util.LinkedList;
        public class GetElementsFromLinkedList {
            public static void main(String[] args) {
                LinkedList<String> names = new LinkedList<String>();
                names.add("Emma");
                names.add("Isabella");
                names.add("Amelia");
                names.add("Richard");
                names.add("James");
                names.add("Robert");
                names.add("Christopher");
                //returning the first element in the LinkedList
                String firstName = names.getFirst();
                System.out.println("First Name is : " + firstName);
                //returning the last element in the LinkedList
                String lastName = names.getLast();
                System.out.println("Last Name is : " + lastName);
                //returning the element at a given position in the LinkedList
                String randomName = names.get(4);
                System.out.println("Random Name is : " + randomName);
            }
        }
    

How to remove element from a LinkedList ?

There are serveral methods that you can use to remove elements from your linkedlist!

  • removeFirst(): removes the first element from the LinkedList.

  • removeLast() : removes the last element from the LinkedList.

  • remove(Object o) : Removes the first occurrence of the specified element from the LinkedList

    
        import java.util.LinkedList;
        public class RemoveFromLinkedList {
            public static void main(String[] args) {
                LinkedList<String> frameworks = new LinkedList<String>();
                frameworks.add("Spring");
                frameworks.add("Hibernate");
                frameworks.add("Angular");
                frameworks.add("Struts");
                frameworks.add("Symfony");
                frameworks.add("JSF");
                // Remove the first element from the LinkedList
                String removedfirstelement = frameworks.removeFirst(); 
                System.out.println("Removing first element : " + removedfirstelement);
                // Remove the first element from the LinkedList
                String removedlastelement = frameworks.removeLast(); 
                System.out.println("Removing last element : " + removedlastelement);
                // Remove a specified element from the LinkedList
                boolean isRemoved = frameworks.remove("Angular");
                if(isRemoved) {
                    System.out.println("We removed an element from LinkedList : " + frameworks);
                }
            }
        }
    

How to Iterate through a LinkedList in Java?

There are multiple ways to iterate over a Linked List in Java:

    
        import java.util.LinkedList;
        import java.util.Iterator;
        public class IterateThroughLinkedList {
            public static void main(String[] args) {
                LinkedList<String> cars = new LinkedList<String>();
                cars.add("Chevrolet");
                cars.add("Audi");
                cars.add("Ford");
                cars.add("Ferrari");
                cars.add("Mercedes");
                cars.add("Honda");
                // Iterating over a LinkedList using Java 8 forEach
                cars.forEach(name -> {
                    System.out.println("Car name : "+ name);
                });
                // Iterating over a LinkedList in Java using iterator()
                System.out.println("--------------------");
                Iterator<String> carsIterator = cars.iterator();
                while (carsIterator.hasNext()) {
                    String car = carsIterator.next();
                    System.out.println("Car name : "+ car);
                }
                // Iterating over a LinkedList using for loop
                System.out.println("--------------------");
                for(String car: cars) {
                    System.out.println("Car name : "+ car);
                }
            }
        }
    

Conclusion:

That’s all folks! You have learned how to implement a linked list in Java and explored some of the most common operations. I hope this article will help you in getting started with LinkedList in Java programming.

Thank you for reading. Please drop me a comment on what you think about this topic or if you like to add something.