How To Create A Singly Linked List In Java

In this example, we shall discuss how to create a Singly Linked List in Java. We will also go through some live code demonstrating different operations on a Singly Linked List.

You can also check this tutorial in the following video:

Java LinkedList Tutorial – video

1. What is a Linked List?

A Linked List is a linear data structure consisting of a collection of Nodes that are not stored in contiguous but random memory locations. It is a commonly used data structure in Computer programs and helps us to build even more complex data structures like Stacks, Queues, Skip Lists, etc.

A Linked List has the following features:

Each node of the list contains a data field which can be a number, string, or any other type of data and a pointer/reference/link field which is actually the address in memory of the next node in the list.
There are three common types of Linked Lists:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

In this example we will be discussing only about Singly Linked Lists with live code.

2. What is a Singly Linked List?

A Singly Linked List is the most common form of a Linked List where each node contains a data field and a single pointer to the next node in the list.

Singly Linked List Java - Representation — Singly Linked List Representation

The reference to the first node in the list is called the HEAD of the list. The pointer/reference/link field contained in the node is used to traverse to the next node and to its next node and so on till we reach a node that points to NULL. This is the last node in the list. Also, a singly linked list can only be traversed in one and only one direction i.e. from head to the last node. There is no way to traverse from the last node back to the head. The following is an example of a singly linked list with 5 nodes.

Singly Linked List Java - with 5 nodes — A Singly Linked List with 5 nodes

2.1. Arrays v/s Singly Linked List ?

You must be wondering why do we need another data structure when we already have a powerful data structure Arrays, easy to create and simple to use. Let's discuss some limitations of arrays and how a Linked List overcomes these limitations.

2.1.1. Limitations Of Arrays

Fixed Size: Array elements are stored in contiguous memory locations. As a result, the size of the array needs to be known in advance at the time of its creation, and predicting this size can be a challenging task. Also, once created, the size of the array cannot be modified and declaring a large-sized array could result in a wastage of memory if we do not end up storing that many elements.
Performance: Since the size of the array cannot be modified dynamically, adding a new element to an array is another expensive operation. This involves allocating a location in the memory with the size of the new array, copying the elements of the old array to the new location, and finally adding the new element. Similarly deleting an element from an array is an expensive operation as all the elements after the deleted element must be shifted left.

2.1.2. Linked Lists – A solution

Dynamic Memory Allocation: As Linked Lists do not need contiguous memory locations to store their elements, memory is allocated dynamically at runtime whenever a new node is created. Therefore, knowing and predicting the size of the linked list in advance is not a necessary requirement.
Performance: Adding an element to a linked list does not require copying the list to a new memory location. Similarly, deleting an element does not require shifting of elements to the left. However, the previous node needs to be updated with the pointer/reference of the next correct node in the memory.

3. Custom Singly Linked List In Java

3.1. Creating a Singly Linked List

A singly linked list in java can be created by using a self-referential class. A self-referential class is one that holds a reference to itself. Below is a class SinglyLinkedList that encloses an inner self-referential class Node having two fields, a data field which is an integer and a "next" field which is of the type Node. The outer class also holds the reference/pointer/link to the HEAD of the list. SinglyLinkedList.java

public class SinglyLinkedList {  	// reference to head / first node of the Singly Linked List 	public Node head = null;  	// class Node that hold data and a reference/link 	// to the next Node in the list 	class Node { 		private int data; 		private Node next;  		public Node(int data) { 			this.data = data; 			this.next = null; 		} 	} }

3.2. Inserting Nodes Into a Singly Linked List

There are three cases to consider for inserting a node into a singly linked list. Adding a node to the :

Beginning of the list.
End of the list.
Specified position in the list.

3.2.1. Inserting a node at the beginning of the list

To insert a new node at the beginning of the list the following algorithm is used :

Assign the reference of the HEAD to the new node's next field.
Make the new node as the HEAD of the list.

Inserting a node with data N at the beginning of the list

Add a node to beginning of the list

          // Point the new node's next to head 			newNode.next = this.head;  			// Make the new node as head 			this.head = newNode;

3.2.2. Inserting a node at the end of the list

To insert a node at the end of the list the following algorithm is followed –

Traverse the list until we find the last node.
The new node's reference is assigned to the last node's next field.

Inserting a node with data N at the end of the list

Add a node to the end of the list

          Node cur = this.head; 			// traverse to the end of the list 			while (cur.next != null) { 				cur = cur.next; 			} 			cur.next = newNode;

3.2.3. Inserting a node at a specified position in the list

To insert a node at a specified position in the list the following algorithm is followed –

Traverse (position – 1) times or till the end of the list is reached and maintain previous and current references.
Assign the reference of the new node to the prev node's next field.
Assign the cur node's reference to the new node's next field.

Inserting a node with data N at position 3 in the list

At a node at a specified position in the list

          // traverse to the end of the list and check positions moved 		while (cur.next != null && --position > 0) { 			// update the prev and cur references 			prev = cur; 			cur = cur.next; 		}  		// update prev to point to new node 		prev.next = newNode;  		// & new node to point to current node 		newNode.next = cur;

The below code demonstrates the above three operations. about how to create a linked list in java. Click the play button to see the code in action and follow the comments to understand it better.

public class Main {  	// reference to head / first node of the Singly Linked List 	public Node head = null;  	// class Node that hold data and a reference/link 	// to the next Node in the list 	class Node { 		private int data; 		private Node next;  		public Node(int data) { 			this.data = data; 			this.next = null; 		} 	}        /* 	 * Method to add a node at the beginning of the list 	 */ 	public void addNodeAtTheBeginning(int data) {         System.out.println("Add a node with data " + data + " in the beginning."); 		// Create a new node 		Node newNode = new Node(data);  		// Check if the list is empty 		if (this.head == null) { 			// Make the new node as head 			this.head = newNode; 		} else { 			// Point the new node's next to head 			newNode.next = this.head;  			// Make the new node as head 			this.head = newNode; 		} 	}        /* 	 * Method to add a node at the end of the list 	 */ 	public void addNodeAtTheEnd(int data) {         System.out.println("Add a node with data " + data + " at the end."); 		// Create a new node 		Node newNode = new Node(data);  		// Check if the list is empty 		if (this.head == null) { 			// Make the new node as head 			this.head = newNode; 		} else { 			Node cur = this.head; 			// traverse to the end of the list 			while (cur.next != null) { 				cur = cur.next; 			} 			cur.next = newNode; 		} 	}       	/* 	 * Method to add a node at the specified position in the list 	 */ 	public void add(int position, int data) {         System.out.println("Add a node with data " + data + " at the position " + position); 		// Create a new node 		Node newNode = new Node(data);  		// Init the cur and prev nodes to the head 		Node cur = this.head, prev = this.head;  		if (position == 1) { 			// Point the new node's next to head 			newNode.next = head; 			// Make the new node as head 			this.head = newNode; 			return; 		}  		// traverse to the end of the list and check positions moved 		while (cur.next != null && --position > 0) { 			// update the prev and cur references 			prev = cur; 			cur = cur.next; 		}  		// update prev to point to new node 		prev.next = newNode;  		// & new node to point to current node 		newNode.next = cur; 	}    	public void print() { 		if (this.head == null) { 			System.out.println("The List is empty."); 		} else { 			System.out.println("The contents of the Singly Linked List are : "); 			Node cur = this.head; 			while (cur != null) { 				System.out.print(cur.data + " -> "); 				cur = cur.next; 			} 			System.out.println("NULL\n"); 		} 	}      	public static void main(String[] args) {         Main list = new Main();         System.out.println("Created a singly linked list ....."); 	    list.print(); 		list.addNodeAtTheBeginning(100); 	    list.print(); 		list.addNodeAtTheBeginning(200); 		list.print();       	list.addNodeAtTheEnd(900); 	    list.print(); 		list.addNodeAtTheEnd(800); 		list.print();         list.add(1,150);         list.print();         list.add(4,250);         list.print();         list.add(6,250);         list.print();     } }

3.3. Deleting Nodes From a Singly Linked List

Deleting a node from a singly linked list can be a little complex as the node to be deleted can be the first node, the last node, or a node in the middle of the list. Let us discuss each case.

First Node: If the node to be deleted is the first node itself, we assign the reference of the next of the HEAD node to the HEAD node.

Delete the first node

          // If the data is found at the first node 		if (this.head.data == data) { 			this.head = this.head.next; 			return; 		}

Last Node or Any Other Node: To delete any other node in the list, we traverse the list keeping track of the previous and current nodes in the list until we find the node to be deleted with the required data field or we reach the end of the list i.e. NULL without finding the data element in the list.
If the node is found, we assign the reference of the next field of the current node to the previous node's next.

Deleting any node from a singly Linked List

Delete any node

          // Traverse the list until it ends or you 		// find the node that holds the data 		while (cur != null && cur.data != data) {  			// update the prev and cur references 			prev = cur; 			cur = cur.next; 		}  		// If the node was found, adjust the prev node 		// to point to the next of the node to be deleted. 		if (cur != null) { 			prev.next = cur.next; 		} else { 			System.out.println("The data " + data + " could not be found in the List"); 		}

Note: Unlike C programming language, we do not have to worry about freeing up the memory used by a node which is getting deleted. This is the responsibility of Java's garbage collector which identifies the unreferenced objects and deletes them to free up the memory. For more details, check out this example on Java Garbage Collection.

The below code demonstrates the delete operations on a Singly Linked List. Click the play button to see the code in action.

public class Main {  	public Node head = null;  	// class Node that hold data and a reference/link 	// to the next Node in the list 	class Node { 		private int data; 		private Node next;  		public Node(int data) { 			this.data = data; 			this.next = null; 		} 	}  	/* 	 * Method to add a node at the end of the list 	 */ 	public void addNodeAtTheEnd(int data) { 		// Create a new node 		Node newNode = new Node(data);  		// Check if the list is empty 		if (this.head == null) { 			// Make the new node as head 			this.head = newNode; 		} else { 			Node cur = this.head; 			// traverse to the end of the list 			while (cur.next != null) { 				cur = cur.next; 			} 			cur.next = newNode; 		} 	}  	/* 	 * Method to delete the first occurrence of data in the list 	 */ 	public void deleteFirstOccurenceOfData(int data) {         System.out.println("Deleting First Occurance of data " + data + " from the list"); 		// Check if the list is empty 		if (this.head == null) { 			System.out.println("The List is empty.\n"); 			return; 		}  		// Init the cur and prev nodes to the head 		Node cur = this.head, prev = this.head;  		// If the data is found at the first node         // assign the reference of current head's next to head 		if (this.head.data == data) { 			this.head = this.head.next; 			return; 		}  		// Traverse the list until it ends or you 		// find the node that holds the data 		while (cur != null && cur.data != data) {  			// update the prev and cur references 			prev = cur; 			cur = cur.next; 		}  		// If the node was found, adjust the prev reference 		// to point to the next of the node to be deleted. 		if (cur != null) { 			prev.next = cur.next; 		} else { 			System.out.println("The data " + data + " could not be found in the List"); 		} 	}  	/* 	 * Method to display the nodes of the singly linked list 	 */ 	public void print() { 		if (this.head == null) { 			System.out.println("The List is empty."); 		} else { 			System.out.println("The contents of the Singly Linked List are : "); 			Node cur = this.head; 			while (cur != null) { 				System.out.print(cur.data + " -> "); 				cur = cur.next; 			} 			System.out.println("NULL\n"); 		} 	}  	public static void main(String[] args) { 		Main list = new Main();       	for (int i=1;i<=8;i++) { 			list.addNodeAtTheEnd(i); 		} 		list.print(); 		list.deleteFirstOccurenceOfData(1); 		list.print(); 		list.deleteFirstOccurenceOfData(8); 		list.print(); 		list.deleteFirstOccurenceOfData(4); 		list.print(); 	} }

4. Disadvantages Of Using a Singly Linked List

No direct access to individual elements is possible. The only way is to start from the HEAD and follow the references in each node to reach the desired node.
A singly linked list uses more memory as compared to an array to store the reference to the next node.

5. Applications of Singly Linked Lists

Some of the applications of Singly Linked Lists are :

To implement complex data structures i.e. Stacks , Queues and Skip Lists.
To implement the adjacency list representation of a Graph.

6. Download the source code

In this tutorial, we learned about how to create a Singly Linked List in Java with several cases of add and delete operations. Also, we saw the limitations of Arrays and the advantages, disadvantages, and applications of using a Singly Linked List.