LinkedList in Java with Examples

Feb 21, 2020 · 5 mins read

Linked list is a data structure that holds a sequential collection of elements (e.g. integers, strings, objects). It is one of the most fundamental data structures in computer science that is used to build other data structures such as stacks and queues.

To understand linked lists, it is helpful to review how arrays work because they are closely related. Arrays store elements in contiguous chunks of memory. That is to say that when an array is initialized, a block of memory is reserved for the entire array. Elements added to the array get their own space within the memory block allocated for the entire array. While arrays are very useful for many use cases, their nature presents us with some challenges:

  • Once an array has been initialized, its size cannot be changed.
  • Arrays reserve memory block upfront when we initialize them. If we don’t use all the space in the array, it’s wasted.
  • Inserting elements to a random index e.g. 3 is expensive because all existing elements need to be shifted over to make room.

Linked list provides an answer to these challenges. (It doesn’t mean they are better than arrays. They both have their advantages and disadvantages and which data structure to use depends on the requirements and use cases.)

Linked lists is a data structure made up of nodes chained together to form a sequence. Each node contains two things: element it is supposed to hold and a reference to the next node in the sequence.

linked-list

Compared to arrays, this structure makes it easy to insert or removes nodes at arbitrary positions. However, random access of nodes is slower than arrays because the list must be scanned from the start to get to the required position.

LinkedList class in Java

Java collections framework comes with a built-in implementation of the Stack data structure in the form of the java.util.LinkedList class. This class implements the List interface and supports all its methods. One interesting internal detail to note is that the java.util.LinkedList is a doubly-linked list implementation which contains an extra pointer pointing to its parent. This makes traversal efficient by allowing it in both forward and backward directions.

Let’s start with a simple example. We’ll create a linked list, add some elements to it and iterate over it.

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

public class LinkedListExample {
    public static void main(String[] args) {

        // Create a new list of type linkedlist
        LinkedList<String> list = new LinkedList<>();

        // Add 6 elements to the list
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);

        // Let's iterate over the list and print elements
        for (Integer element: list) {
            System.out.println(element);
        }
    }
}

}

This program will print:

1
2
3
4
5
6

In the example above, we created a List reference and treated linked list like any other regular list. In the next example, let’s create a linked list object so we can use methods of the LinkedList class.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {

        // Create a new linkedlist
        LinkedList<String> list = new LinkedList<>();

        // Add some elements

        list.add("B");
        list.add("C");
        list.add("D");

        // add element to the start of the list
        list.addFirst("A");

        // add element to the end of the list
        list.addLast("E");

        // print elements
        for (String element: list) {
            System.out.println(element);
        }

        // remove second element "B"
        list.remove(1);

        System.out.println("removed second element");
        for (String element: list) {
            System.out.println(element);
        }

        System.out.println("3rd element is" + list.get(2));
    }
}

It will print the following output:

A
B
C
D
E
removed second element
A
C
D
E
3rd element is D

Other notes:

  • Stacks and queues are implemented using linked lists. LinkedList class contains methods such as push and pop to make it easy to work with stacks.
  • LinkedList class implementes the Dequeue (pronounced ‘Deck’) interface which is double ended queue or last-in, first-out (LIFO) data structure and support all of its operations.
  • The LinkedList class is not synchronized and hence it is not safe for multithreading. Access to it by multiple threads must be synchronized or use the Collections.synchronizedList method.

That’s all. I hope you enjoyed. Please leave comments below if you have a question or even just a comment. Thanks for reading.



Join Newsletter
Enter your email address to receive a very occasional newsletter. I'll never spam or sell your email.