How to Implement Linked List in Java
In this article, we are going to cover in-depth how to implement Linked List in Java.
First, we will start with a little bit of theory about what a LinkedList data structure is.
Then, we are going to dig deep to see how to create a linked list implementation in Java using practical examples.
What is a Linked List?
A LinkedList, also called singly linked list, is a dynamic data structure that describes a collection of data where all elements are linked together.
Basically, each element of the list is linked to the next one, hence the name. Confused? Let me explain: Like a chain, each element is linked to its next neighbor.
Since a linked list is not an infinite loop, it must end somewhere. So, just after the last element, we find the null reference to indicate the end of the list.
Typically, each element of a linked list is called a node. Each node holds two items:
The data (the actual content)
A reference to the next node
The first node that defines the entry point into the list is called a head.
Please bear in mind that there are two types of linked lists: single and double linked lists. However, in this tutorial we will be concentrating on how to implement singly linked lists.
Our article on how to implement a doubly linked list in Java does a great job in covering this topic.
Linked List Implementation in Java
As we have mentioned earlier, a singly LinkedList is a dynamic list where its elements are chained together and 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.
Now, that we know what a linked list data structure is, let’s see how to implement it in Java.
Implement Linked List in Java From Scratch
Understanding how to implement a LinkedList from scratch will help us understand more complex data structures. So, let’s see how we can accomplish this in Java.
In short, to implement a linked list, we need to define its core components: the node and the head.
In Java, a linked list can be represented as a simple class that contains another separate Node class.
To define the head, our class should have a reference of Node type.
Now, let’s put all the pieces together and see how a linked list can be implemented 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;
}
}
}
As we can see, the Node class contains the data and a reference to the next node.
We call our implementation SinglyLinkedList because each node has only one reference to point to the next one.
Next, let’s see how to implement some basic operations.
Basic Operations
isEmpty(): to check if the linked list is empty
contains(T x): checks if the LinkedList contains the specified given element
toString(): returns the string representation of the linked list
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
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 a new item at the beginning of the list
addLast(T item): add a new item to the end of the list
insertAfter(T key, T toInsert): add a new element after the element containing the specified key
insertBefore(T key, T toInsert): add a new element before the element containing the given key
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
remove(): removes the first occurrence of the specified element
clear(): to clear the list and remove all elements
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, we have to change the current node’s next link to point to its previous element.
To do so, we 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 each item does not have a reference link to the previous node, then we must store the previous element somewhere.
We can achieve this using the following simple statement:
current.next = previous;
We need a third reference to store the next node before changing the references to keep track on the next elements.
The logic of reversing a linked list in Java can be described as follow:
Loop while
currentelement is not nullStore the next of the
currentelement inenextelementSet the next of the
currentnode to thepreviouselementSet
previoustocurrentSet the
currentelement toenextelement
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> reverseListAndReturnIt(){
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 to create a new copy that 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
call the addLast() method to insert each element into the cloned linked list
public SinglyLinkedList<T> clone(){
SinglyLinkedList<T> clonedLinkedList = new SinglyLinkedList<T>();
Node<T> tmp = head;
while(tmp != null) {
clonedLinkedList.addLast( tmp.data );
tmp = tmp.next;
}
return clonedLinkedList;
}
public SinglyLinkedList<T> cloneAndReturn(){
SinglyLinkedList<T> clonedLinkedList = new SinglyLinkedList<T>();
Node<T> tmp = head;
if(head == null) {
return null;
}
clonedLinkedList.head = new Node<T>(head.data, null);
Node<T> tmpTwin = clonedLinkedList.head;
while(tmp.next != null) {
tmp = tmp.next;
tmpTwin.next = new Node<T>(tmp.data, null);
tmpTwin = tmpTwin.next;
}
return clonedLinkedList;
}
Built-in Java Implementation Using LinkedList Class
The Collection API provides a convenient way to implement a linked list in Java. It comes with a ready-to-use class named LinkedList.
So, let’s see together how to use LinkedList and what feature brings in:
public static void main(String[] args) {
LinkedList languages = new LinkedList<>();
// add elements
languages.add("Java");
languages.addFirst("PHP");
languages.addLast("Python");
languages.add("C++");
languages.add("JavaScript");
languages.add("C#");
languages.add("Kotlin");
// get first element
System.out.println("First Language: " + languages.getFirst());
// get last element
System.out.println("Last Language: " + languages.getLast());
// remove elements
languages.removeFirst();
languages.removeLast();
// Loop through linked list in Java 8
languages.forEach(System.out::println);
}
### Output:
First Language: PHP
Last Language: Kotlin
Java
Python
C++
JavaScript
C#
As we can see, LinkedList offers a set of methods for adding, retrieving, and removing elements from a linked list.
Please feel free to check our tutorial on Java priority queue.
Conclusion
That’s all folks! we have explained how to implement linked list in Java and explored some of the most common operations.
We 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.