Java Single Linkedlist
Like arrays, linked lists are a type of linear data structure. Unlike arrays, which store each element in the same location, linked lists employ pointers to connect the elements together.
In Java, a Node can be represented as a different class from a LinkedList. The LinkedList class has a reference to the Node class type.
Example:
class LL {
N head; // N stands node
// LL Node
class N {
int dt;
N next;
// function Object() { [native code] } for new node creation The default initialization of Next is null.
N(int d) { dt = d; }
}
}Creation and Insertion
In this article, the new node is added to the list after the last node in the given Linked List, which is done at the end. For instance, if 30 was to be added to the provided Linked List of 5->10->15->20->25, the Linked List would change to 5->10->15->20->25->30.
It is required to traverse the list until it reaches its last node since a linked list's head pointer often acts as its representation. Only then can the next-to-last node be switched to the new node.
Implementing:
import java.io.*;
// Singly Linked List demonstration in Java
public class LL {
N head; // head of list
// LL Node.To enable access from main(), this inner class has been made static.
static class N {
int dt;
N nt;
// Constructor
N(int d)
{
dt = d;
nt = null;
}
}
// The best way to add a new node
public static LL insert(LL l, int dt)
{
// Make a new node using the provided data.
N new_node = new N(dt);
// Make the new node the head if the L L is empty.
if (l.head == null) {
l.head = new_node;
}
else {
// traverse until the final node if not
Node last = l.head;
while (last.n != null) {
last = last.nt;
}
// Insert the new_node at last nodeas well as adding the new node there
last.nt = new_node;
}
// List retrieval by heading
return l;
}
// LinkedList printing technique.
public static void printList(LL list)
{
N currN = l.head;
System.out.print("LL: ");
// navigating the LinkedList
while (currN != null) {
// Dispatch the data at the current node.
System.out.print(currN.dt + " ");
// the subsequent node
currN = currN.next;
}
}
// Driver code
public static void main(String[] args)
{
// Begin with the bare list.
LL l = new LL();
// INSERTION
// Inserting the values
l = insert(l, 10);
l = insert(l, 20);
l = insert(l, 30);
l = insert(l, 40);
l = insert(l, 50);
l = insert(l, 60);
l = insert(l, 70);
l = insert(l, 80);
// Print the LinkedList
printList(l);
}
}Output:
LinkedList: 10 20 30 40 50 60 70 80
Traversal: Below is a general-purpose function called printList() that prints any list that is passed to it by traversing it from head node to last node.
Implementing:
import java.io.*;
// Singly Linked List demonstration in Java
public class LL {
N head; // head of list
// LL Node. Due of Node's static nature, main() can access it.
static class N {
int dt;
N nt;
// Constructor
N(int d)
{
dt = d;
nt = null;
}
}
// The best way to add a new node
public static LL insert(LL l,
int dt)
{
// Make a new node using the provided data.
N new_node = new N(dt);
new_node.next = null;
// Make the new node the head if the Linked List is empty.
if (l.head == null) {
l.head = new_node;
}
else {
//
N last = l.head;
while (last.nt != null) {
last = last.nt;
}
// Inserting the new_node at last node
last.nt = new_node;
}
// Return the l by head
return l;
}
// Method to print the LL.
public static void printList(LL l)
{
N currN = l.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currN != null) {
// Print the dt at current node
System.out.print(currN.dt + " ");
// Go to next node
currN = currN.nt;
}
}
// MAIN METHOD
// n node Singly linked list construction technique
public static void main(String[] args)
{
Start with the empty list.
LL l = new LL();
// INSERTION
// Inserting the values
l = insert(l, 10);
l = insert(l, 20);
l = insert(l, 30);
l = insert(l, 40);
l = insert(l, 50);
l = insert(l, 60);
l = insert(l, 70);
l = insert(l, 80);
// Print the LinkedList
printList(l);
}
}Output:
LinkedList: 10 20 30 40 50 60 70 80
Singly Linked List demonstration in Java
import java.io.*;
// Singly Linked List demonstration in Java
public class LL {
N head; // head of list
// L L N. Due of Node's static nature, main() can access it.
static class N {
int dt;
N nt;
// Constructor
N(int d)
{
dt = d;
nt = null;
}
}
// Method to insert a new node
public static LL insert(LL l,
int dt)
{
// Create a new node with given data
N new_node = new N(dt);
new_node.next = null;
// Make the new node the head if the Linked List is empty.
if (l.head == null) {
l.head = new_node;
}
else {
//Alternatively, traverse till the final node and place the new node there.
N last = l.head;
while (last.nt != null) {
last = last.nt;
}
// Insert the new_node at last node
last.nt = new_node;
}
// Return the l by head
return l;
}
// Method to print the LL.
public static void printList(LL l)
{
N currN = list.head;
System.out.print("LinkedList: ");
// Traverse through the LL
while (currN != null) {
// Print the data at current node
System.out.print(currN.dt + " ");
// Go to next node
currN = currN.next;
}
System.out.println();
}
// DELETION BY KEY
// How to remove a node from a linked list using a key
public static LL deleteByKey(LL l,
int key)
{
// Store head node
N currN = l.head, prev = null;
// CASE 1:
// If the key to be erased is stored in the head node itself
if (currN != null &&currN.dt == key) {
l.head = currN.nt; // Changed head
// Display the output
System.out.println(key + " found and deleted");
// Return the updated L
return l;
}
// CASE 2:
// If the key is not in the head, it may be elsewhere.
// Find the key that needs to be destroyed, and retain track of the prior node in case currN.next needs to be changed.
while (currN != null &&currN.dt != key) {
// Continue to the next node if currNode cannot retain the key
prev = currN;
currN = currN.nt;
}
//The key ought to be at currNode if it was present. The currN shall not be null as a result.
if (currN != null) {
// Since the key is at currN, remove currN from the linked list.
prev.nt = currN.nt;
// Display the output
System.out.println(key + " found and deleted");
}
// CASE 3: The key is not present
// If the key wasn't in the linked list, then currN should be empty.
if (currN == null) {
// Display the output
System.out.println(key + " not found");
}
// return the L
return l;
}
// MAIN METHOD
// n node Singly linked list construction technique
public static void main(String[] args)
{
Start with the empty list.
LL l = new LL();
// INSERTION
// Inserting the values
l = insert(l, 10);
l = insert(l, 20);
l = insert(l, 30);
l = insert(l, 40);
l = insert(l, 50);
l = insert(l, 60);
l = insert(l, 70);
l = insert(l, 80);
// Print the LinkedList
printList(l);
// DELETION BY KEY
// Remove the node with the value "1"; The head of the key in this instance
deleteByKey(l, 1);
// Print the LL
printList(l);
// Remove the node with the value 4; The key is present in this instance in the / middle.
deleteByKey(l, 4);
// Print the LL
printList(l);
// Remove the node with the value 10; The key is absent in this instance.
deleteByKey(l, 10);
// Print the LL
printList(l);
}
}Output:
LinkedList: 10 20 30 40 50 60 70 80
1 found and deleted
LL: 20 30 40 50 60 70 80
4 found and deleted
LL: 20 30 50 60 70 80
10 not found
LL: 20 30 50 60 70 80Steps to do it are as follows:
Follow the list by counting the nodes' indexes. Match the index to the place for each index. Now, any of the following 3 circumstances may exist: Case 1: The head should be removed because the position is 0. Change the node's head to the following node in this situation.
Remove the memory from the replacement head node.
import java.io.*;
// Singly Linked List demonstration in Java
public class LL {
N head; // head of list
// LL N.
// Node is a static nested class, which enables access via main().
static class N {
int dt;
Nnext;
// Constructor
N(int d)
{
dt = d;
next = null;
}
}
// Method to insert a new node
public static LL insert(LL l,
int dt)
{
// Create a new node with given data
N new_node = new N(dt);
new_node.next = null;
// The new node should be made the head if the Linked List is empty.
if (l.head == null) {
l.head = new_node;
}
else {
//Otherwise, traverse till the last node, then place the new node there.
N last = l.head;
while (last.next != null) {
last = last.next;
}
// Inserting the new_node at last node
last.next = new_node;
}
// Return the l by head
return l;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currN = l.head;
System.out.print("LinkedList: ");
// Traverse through the LL
while (currN != null) {
// Print the dt at current node
System.out.print(currN.dt + " ");
// Go to next node
currN = currN.next;
}
System.out.println();
}
// A technique for removing a node from the linked list by position
public static LL
deleteAtPosition(LL l, int index)
{
// Store head node
Node currN = l.head, prev = null;
// CASE 1:
//The head node itself must be deleted if the index is 0.
if (index == 0 &&currN != null) {
l.head = currN.next; // Changed head
// Display the message
System.out.println(
index + " position element deleted");
// Return the updated L
return l;
}
// CASE 2:
// Whenever the index is greater than 0 but smaller than the LinkedList's / size The counter
int counter = 0;
// Count the number of the deleted index, Keep track of the preceding node because currN.next has to be changed.
while (currN != null) {
if (counter == index) {
// Because the currN is a necessary component, remove it from the linked list.
prev.next = currN.next;
// Display the message
System.out.println(
index + " position element deleted");
break;
}
else {
// Continue to the next node if the current position is not the index.
prev = currN;
currN = currN.next;
counter++;
}
}
// It should be / at currNode if the position element was found. Consequently, the currNode must not be null.
// CASE 3: The index is greater than the size of theLL
//The currN should be null in this instance.
if (currN == null) {
// Display the output
System.out.println(
index + " position element not found");
}
// return the L
return l;
}
// MAIN METHOD
// n node Singly linked list construction technique
public static void main(String[] args)
{
Start with the empty list.
LL l = new LL();
// INSERTION
// Inserting the values
l = insert(l, 10);
l = insert(l, 20);
l = insert(l, 30);
l = insert(l, 40);
l = insert(l, 50);
l = insert(l, 60);
l = insert(l, 70);
l = insert(l, 80);
// Print the LinkedList
printList(l);
// DELETION AT POSITION
// Node deletion at position 0 The head of the key in this instance
deleteAtPosition(l, 0);
// Print the LL
printList(l);
// Remove node at position 2 because the key is in the centre in this instance.
deleteAtPosition(l, 20);
// Print the LL
printList(l);
// Node deletion at position 10 The key in this instance is not available.
deleteAtPosition(l, 10);
// Print the LL
printList(l);
}
}Output:
LinkedList: 10 20 30 40 50 60 70 80
0 position element deleted
LL: 20 30 40 50 60 70 80
2 position elements deleted
LL: 20 30 50 60 70 80
10 position elements not found
LL: 20 30 50 60 70 80Singly Linked List demonstration in Java
import java.io.*;
// Singly Linked List demonstration in Java
public class LL {
N head; // head of list
// Node in the linked list is a static nested class, which allows main() to access it.
static class N {
int dt;
N next;
// Constructor
N(int d)
{
dt = d;
next = null;
}
}
// INSERTION
// Method to insert a new node
public static LL insert(LL l,
int dt)
{
// Create a new node with given data
N new_node = new N(dt);
new_node.next = null;
// The new node should be made the head if the Linked List is empty.
if (l.head == null) {
l.head = new_node;
}
else {
// Otherwise, traverse till the last node, then place the new node there.
N last = l.head;
while (last.next != null) {
last = last.next;
}
// Place the new node at the final node.
last.next = new_node;
}
// Return the l by head
return l;
}
// TRAVERSAL
// Method to print the LL.
public static void printList(LL l)
{
Node currN = l.head;
System.out.print("\nLinkedList: ");
// Traverse through the LL
while (currN != null) {
// Dispatch the data at the current node.
System.out.print(currN.data + " ");
// Go to next node
currN = currN.next;
}
System.out.println("\n");
}
// DELETION BY KEY
// How to remove a node from a linked list using a key
public static LL deleteByKey(LL l,
int key)
{
// Store head node
N currN = l.head, prev = null;
// CASE 1:
// If the key to be erased is stored in the head node itself
if (currN != null &&currN.dt == key) {
l.head = currN.next; // Changed head
// Display the output
System.out.println(key + " found and deleted");
// Return the updated L
return l;
}
// CASE 2:
//If the key is not in the head, it may be elsewhere.
// Find the key that has to be erased, Keep track of the preceding node because currN.next has to be changed.
while (currN != null &&currN.dt != key) {
// Continue to the next node if currN does not hold the key
prev = currN;
currN = currN.next;
}
// The key should be at currN if it was present. The currN shall not be null as a result.
if (currN != null) {
// Since the key is located at currNode, remove currNode from the linked list.
prev.next = currN.next;
// The key should be at currNode if it was present. The currNode shall not be null as a result.
if (currN != null) {
// Since the key is located at currNode, remove currNode from the linked list.
prev.next = currN.next;
// Display the output
System.out.println(key + " found and deleted");
}
// CASE 3: The key is not present
// If the key wasn't in the linked list, then currNode should be empty.
if (currN == null) {
// Display the output
System.out.println(key + " not found");
}
// return the L
return l;
}
// DELETION AT A POSITION
// Method to delete a node in the LinkedList by POSITION
public static LL
deleteAtPosition(LL l, int index)
{
// Store head node
N currN = l.head, prev = null;
// CASE 1:
// The head node itself must be deleted if the index is 0.
if (index == 0 &&currN != null) {
l.head = currN.next; // Changed head
// Display the output
System.out.println(
index + " position element deleted");
// Return the updated L
return l;
}
// CASE 2:
//Whenever the index is greater than 0 but smaller than the LinkedList's sizethe counter
int counter = 0;
// Count the number of the deleted index, Keep track of the preceding node because currN.next has to be changed.
while (currN != null) {
if (counter == index) {
// Because the currNode is a necessary component, remove it from the linked list.
prev.next = currN.next;
// Display the message
System.out.println(
index + " position element deleted");
break;
}
else {
// If the current position is not the index, move on to the following node.
prev = currN;
currN = currN.next;
counter++;
}
}
// It should be / at currNode if the position element was found. Consequently, the currN must not be null.
// CASE 3: The index is bigger than the LinkedList's size.
// The currN should be null in this instance.
if (currN == null) {
// Display the message
System.out.println(
index + " position element not found");
}
// return the L
return l;
}
// MAIN METHOD
// n node Singly linked list construction technique
public static void main(String[] args)
{
// Start with the empty list.
LLl = new LL();
// INSERTION
// Inserting the values
l = insert(l, 10);
l = insert(l, 20);
l = insert(l, 30);
l = insert(l, 40);
l = insert(l, 50);
l = insert(l, 60);
l = insert(l, 70);
l = insert(l, 80);
// Print the LL
printList(l);
// DELETION BY KEY
// Remove the node with the value "1"; The key in this instance is at head.
deleteByKey(l, 1);
// Print the LL
printList(l);
// Remove the node with the value 4; In this instance, the key is situated in the middle.
deleteByKey(l, 4);
// Print the LL
printList(l);
// Remove the node with the value 10; The key in this instance is not available.
deleteByKey(l, 10);
// Print the LL
printList(l);
//DELETION AT POSITION
// Node deletion at position 0 / The head of the key in this instance
deleteAtPosition(l, 0);
// Print the LL
printList(l);
// Remove node at position 2 because the key is in the centre in this instance.
deleteAtPosition(l, 2);
// Print the LL
printList(l);
// Node deletion at position 10. The key is absent in this instance.
deleteAtPosition(l, 10);
// Print the LL
printList(l);
}
}Output:
LinkedList: 10 20 30 40 50 60 70 80
1 found and deleted
LL: 20 30 40 50 60 70 80
4 found and deleted
LL: 20 30 50 60 70 80
10 not found
LL: 20 30 50 60 70 80
0 position element deleted
LL: 30 50 60 70 80
2 position elements deleted
LL: 30 50 70 80
10 position elements not found
LL: 30 50 70 80