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.
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.
3is 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
Print Linked Lists in Java
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.
LinkedListclass contains methods such as push and pop to make it easy to work with stacks. LinkedListclass 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
LinkedListclass 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.
