Singly Linked List in Java
Deep Dive into Singly linked list in Java
Singly Linked List in Java is one of the most powerful data structures there. Let us have a look on how we can write the Java Program for a singly linked List below
What is a Singly Linked List in Java?
A singly Linked List in Java is a collection of nodes that are connected in a chained sequence. Where each node has the following –
- Data Value
- Next Reference – Reference to the next node in the sequence
Unlike Arrays with are contiguously stored, Linked List is not contiguous and are scattered all over the memory but connected with one another using the next references.
Also, array size can not be dynamically increased however, in Linked List the size can be increased and decreased at any time dynamically.
Structure of singly linked list in Java
class LinkedList {
Node head; // head
// Linked list Node
class Node {
int data;
Node next;
// constructor to initialize
Node(int d) {
data = d;
next = null;
}
}
} 
Operation on singly linked list
- Deletion
- Insertion
- Traversals
Insertion of a node
Method 1
Method 2
Method 1
public Node insertNode (int data)
{
// Using constructor to create memory and value assignment
Node new_node = new Node (data);
// current head becomes this new_node's next
new_node.next = head;
// changing head to this newly created node
head = new_node;
return head;
}
Method 2
static Node insertStart(Node head, int data)
{
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
// assigning this newNode's next as current head node
newNode.next = head;
// re-assigning head to this newNode
head = newNode;
return head;
}
Deletion of a node
Method 1
Method 2
Method 1
public void delete ()
{
if (head == null)
{
System.out.println ("List is empty, not possible to delete");
return;
}
System.out.println ("Deleted: " + head.data);
// move head to next node
head = head.next;
}
Method 2
public static Node delete(Node head)
{
if (head == null){
System.out.println("List is empty, not possible to delete");
return head;
}
System.out.println("Deleted: " + head.data);
// move head to next node
head = head.next;
return head;
}
Traversal in a Singly Linked List
Method 1
Method 2
Method 1
public void display ()
{
Node node = head;
//as linked list will end when Node reaches Null
while (node != null)
{
System.out.print (node.data + " , ");
node = node.next;
}
System.out.println ();
}
Method 2
static void display (Node node)
{
//as linked list will end when Node is Null
while (node != null)
{
System.out.print (node.data + " ");
node = node.next;
}
System.out.println ("");
}
Code for Implementing Single Linked List in Java
Code (Method 1)
Code (Method 2)
Code (Method 1)
Run
// Linked in Java Program
import java.lang.*;
class LinkedList
{
Node head;
// not using parameterized constructor would by default
// force head instance to become null
// Node head = null; // can also do this, but not required
// Node Class
class Node
{
int data;
Node next;
Node (int x) // parameterized constructor
{
data = x;
next = null;
}
}
public Node insertNode (int data)
{
// Using constructor to create memory and value assignment
Node new_node = new Node (data);
// current head becomes this new_node's next
new_node.next = head;
// changing head to this newly created node
head = new_node;
return head;
}
public void delete ()
{
if (head == null)
{
System.out.println ("List is empty, not possible to delete");
return;
}
System.out.println ("Deleted: " + head.data);
// move head to next node
head = head.next;
}
public void display ()
{
Node node = head;
//as linked list will end when Node reaches Null
while (node != null)
{
System.out.print (node.data + " , ");
node = node.next;
}
System.out.println ();
}
}
class Main
{
public static void main (String args[])
{
LinkedList listObj = new LinkedList ();
listObj.insertNode (25);
listObj.insertNode (20);
listObj.insertNode (15);
listObj.insertNode (10);
listObj.insertNode (5);
listObj.display ();
listObj.delete ();
listObj.delete ();
listObj.delete ();
listObj.display ();
}
}
Output
5 , 10 , 15 , 20 , 25 , Deleted: 5 Deleted: 10 Deleted: 15 20 , 25
Code (Method 2)
Run
import java.lang.*;
// Node Class
class Node {
int data;
Node next;
Node(int x) // parameterized constructor
{
data = x;
next = null;
}
}
class Main
{
static Node insertStart(Node head, int data)
{
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
// assigning this newNode's next as current head node
newNode.next = head;
// re-assigning head to this newNode
head = newNode;
return head;
}
public static Node delete(Node head)
{
if (head == null){
System.out.println("List is empty, not possible to delete");
return head;
}
System.out.println("Deleted: " + head.data);
// move head to next node
head = head.next;
return head;
}
static void display(Node node) {
//as linked list will end when Node is Null
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println("");
}
public static void main(String args[])
{
Node head = null;
head = insertStart(head,6);
head = insertStart(head,5);
head = insertStart(head,4);
head = insertStart(head,3);
head = insertStart(head,2);
head = insertStart(head,1);
display(head);
head = delete(head);
head = delete(head);
head = delete(head);
display(head);
}
}
Output
1 2 3 4 5 6 Deleted: 1 Deleted: 2 Deleted: 3 4 5 6
WHY?
SINGLY LINKED LIST !!!
- Dynamic Data Structure
Linked list is a dynamic in nature so it can grow and shrink at runtime by allocating and deallocating memory.
- Insertion and Deletion
Insertion and Deletion becomes easy in linked list .
- Memory Wastage
As linked list is dynamic in nature we can increase as well as decrease the size of list thus memory is saved
- Implement
Linked list are widely used in programming of stacks and queues .
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Time Complexity
For Singly Linked List
Best
O(1)
Average
O(n)
Worst
O(n)
Average Comparisons
(n+1)/2
Time Complexity
For Singly Linked List
Best
O(1)
Average
O(n)
Worst
O(n)
Average Comparisons
(n+1)/2
Question 1. What is the time complexity for searching an element in a singly linked list, assuming the element is present in the list?
- O(1)
- O(log n)
- O(n)
- O(n^2)
The correct answer is c) O(n).
Searching for an element in a singly linked list requires traversing through each node until the desired element is found or the end of the list is reached.
In the worst case, when the element is at the end of the list or not present at all, the algorithm needs to visit every node, resulting in a linear time complexity, O(n).
Question 2. Which of the following operations has a time complexity of O(1) in a singly linked list?
- Insertion at the beginning
- Deletion at the end
- Traversal
- Searching for an element
The correct answer is a)
Insertion at the beginning. In a singly linked list, insertion at the beginning involves updating only a few pointers, irrespective of the size of the list.
Therefore, the time complexity of this operation is constant, O(1). The other options require traversing the list, which takes linear time, O(n).
Question 3. What is the time complexity to search for an element in a singly linked list of length ‘n’ in the worst case?
- O(1)
- O(log n)
- O(n)
- O(n^2)
Answer: c) Insertion in sorted order
Explanation: Insertion in sorted order can be performed efficiently on a sorted singly linked list. By traversing the list and finding the appropriate position for the new node, we can insert it in the correct place while maintaining the sorted order. This operation requires traversing the list in a manner similar to searching, resulting in a time complexity of O(n) in the worst case.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment