Insertion at Beginning in a Linked List in Java
Insertion at Beginning in a Linked List using Java
In this article we will explore how to perform Insertion at Beginning in a Linked List using Java. We will walk through the concept, the algorithm, the step by step logic, Java implementation, and also cover frequently asked questions.
Linked Lists are one of the most fundamental data structures in computer science. Unlike arrays, linked lists allow efficient insertion and deletion of elements at any position. Among all operations, inserting a node at the beginning is one of the most commonly used and efficient ones.
1. Data: Stores the actual value.
2. Next: A reference (or link) to the next node in the list.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, they use pointers to connect elements, allowing dynamic memory allocation.
What is Singly Linked List ?
Singly linked list is a type of linked list where each node points to the next node in the sequence, and the last node points to null.
Example:
Head -> [10 | next] -> [20 | next] -> [30 | null]
What is Insertion at Beginning in Linked List in Java?
Futher we have mentioned necessary details for Performing Insertion at Beginning in a Linked List:
Insertion at the beginning means adding a new node as the first node of the linked list. The newly inserted node becomes the new head of the list.
For example:
1. Before Insertion:
Head -> [20 | next] -> [30 | null]
2. After Insertion
Head -> [10 | next] -> [20 | next] -> [30 | null]
2. It requires constant time: O(1) complexity.
3. Frequently used in stack implementations using linked lists.
Algorithm for Insertion at Beginning in a Linked List in Java
Step by step Breakdown:
- Create a new node with the given data.
- Set the next of the new node to point to the current head node.
- Make the new node the new head of the linked list.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Java Implementation for Insertion at beginning
Let’s implement this using a custom class for the linked list and its nodes.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
Complete Code:
public class LinkedList {
Node head;
// Insert a node at the beginning
public void insertAtBeginning(int newData) {
Node newNode = new Node(newData); // Step 1
newNode.next = head; // Step 2
head = newNode; // Step 3
}
// Utility method to print the linked list
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// Main method to test
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(30);
list.insertAtBeginning(20);
list.insertAtBeginning(10);
System.out.println("Linked List after insertions:");
list.printList();
}
}
Output:
Linked List after insertions: 10 -> 20 -> 30 -> null
Space Complexity: O(1)
Insertion is done in constant time because we only manipulate pointers, regardless of the list size.
Space remains constant per insertion since only one new node is created.
To wrap it up….
- Insertion at beginning of a linked list is a basic but powerful operation.
- It can be implemented with just a few lines of code in Java.
- It’s highly efficient with constant time complexity.
- Mastering this operation lays the foundation for more complex operations like insertions at specific positions, deletions, and reversals.
FAQ's related to Insertion at Beginning in a Linked List
Answer:
Time complexity is O(1) because the operation only involves updating pointers and does not depend on the size of the list.
Answer:
Create a new node, set its next pointer to the current head, and then update the head to this new node.
Answer:
Yes, insertion at beginning is faster because it doesn’t require traversal. Insertion at the end requires traversal unless a tail pointer is maintained.
Answer:
Yes, and it is also a constant time operation. However, in a doubly linked list, you also need to update the prev pointer of the existing head node.
Answer:
Stack implementation using linked list, undo operations in editors, and maintaining most recently used (MRU) elements in some algorithms.
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