LinkedList in Java

Feb 21, 2020 · 11 mins read
  1. What is a Linked List?
    1. Linked Lists vs Arrays
  2. How to use Linked Lists in Java
    1. Create a Linked List in Java
    2. Add and Remove Nodes to a Linked List
    3. Print Linked Lists in Java
    4. Sort Linked Lists in Java
    5. Sort Linked Lists in Reverse Order
    6. Clear Linked Lists in Java
    7. Make a Copy of Linked Lists in Java

What is a Linked List?

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.

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

linked-list

To understand linked lists better, let’s contrast them with arrays that are a popular data structure for holding similar data or values.

Linked Lists vs Arrays

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. In other words, array memory is allocated at compile time on the Stack.
  • Inserting elements to a random index in array 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.) Compared to arrays,

  • Linked lists makes it easy to insert or removes nodes at arbitrary positions.
  • In linked lists, memory is allocated at run-time (on the Heap) and it only uses as much space as what is needed to store all the elements.
  • Random access of a data is slower in linked lists because the list must be scanned from the start to get to the required position. It’s done in O(n) time compared to O(1) of arrays.

How to use Linked Lists in Java

Java collections framework comes with a built-in implementation of the Linked List 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.

Create a Linked List in Java

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

Add and Remove Nodes to a Linked List

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 to add and remove nodes. We’ll also see how to add nodes to the start and end of the linked list.

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

We can traverse linked lists in Java and print its elements using a few different techniques.

1. Printing Linked Lists Using Simple for Loop

for (int i = 0; i < list.size(); i++)) {
    System.out.println(list.get(i));
}

2. Printing Linked Lists Using Enhanced for Loop

This should be the preferred way of printing linked lists in Java as it’s easier to read. It’s also less error prone than a simple for loop where you could run into IndexOutofBoundExceptions.

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

3. Printing Linked Lists Using Java 8 Streams

You can also print linked lists with Java 8 Streams using the forEach(...) method:

list.stream().forEach(System.out::println);

4. Using toString method of the LinkedList class

You can also print linked lists using its toString() method:

list.toString()

Sort Linked Lists in Java

To sort Linked Lists in Java, you can use the sort() method of the Collections class. For example the following example sorts the elements in ascending order:

LinkedList<Integer> list = new LinkedList<>();

list.add(10);
list.add(9);
list.add(1);
list.add(3);
list.add(2);

Collections.sort(list);

System.out.println(list) // Print list using its toString method

This will print:

[1, 2, 3, 9, 10]

You can compare using any method. For example, you may have a linked list containing a list of employees. You can choose to sort using their “First Names” or the “Date” they joined. You can do this by passing a custom comparator to the sort method.

Sort Linked Lists in Reverse Order

To sort Linked Lists in reverse order, you can use the sort() and reverse() methods of the Collections class. For example the following example sorts the elements in descending order:

LinkedList<Integer> list = new LinkedList<>();

list.add(10);
list.add(9);
list.add(1);
list.add(3);
list.add(2);

Collections.sort(list);
Collections.reverse(list); // reverse the sorted collection

System.out.println(list) // Print list using its toString method

This will print:

[10, 9, 3, 2, 1]

Clear Linked Lists in Java

To delete all elements in a linked lists and clear it, we can use the clear() method of the LinkedList class.

LinkedList<Integer> list = new LinkedList<>();

list.add(10);
list.add(9);
list.add(1);
list.add(3);
list.add(2);

System.out.println("Before clearing: " + list) // Print list using its toString method

list.clear()

System.out.println("After clearing: " + list) // Print list using its toString method

This outputs:

Before clearing: [10, 9, 1, 3, 2,]
After clearing: []

Make a Copy of Linked Lists in Java

To make a shallow copy of a linked list, you can use the clone() method of the LinkedList class. In shallow copy, the objects share the same references as those of the source list.

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

list.add("Java");
list.add("C++");
list.add("Python");
list.add("Golang");

LinkedList<String> clonedList = (LinkedList<String>)list.clone();

System.out.println(clonedList);

This prints:

[Java, C++, Python, Golang]

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.


You May Also Enjoy


If you like this post, please share using the buttons above. It will help CodeAhoy grow and add new content. Thank you!


Read free Software Algorithms and Computer Science Books by CodeAhoy Learn.

Introduction to Recursion and Backtracking

Sorting Algorithms

Introduction to C Programming Language

And More...