Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Creating a node
3.
Insertion
3.1.
Insertion at the beginning of the list
3.1.1.
Algorithm
3.1.2.
Program
3.2.
Insertion at the end of the list
3.2.1.
Algorithm
3.2.2.
Program
3.3.
Insertion at a specific position
3.3.1.
Algorithm
3.3.2.
Program
4.
Deletion
4.1.
Algorithm
4.2.
Program
5.
5.1.
What is a linked list in C++?
5.2.
What are the applications of a linked list?
5.3.
How do you delete a node in a linked list?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Implementing a Linked List in Java Using Class

Ishita Chawla
0 upvote

## Introduction

Linked list is a hot-selling topic in terms of interview preparation and to have a solid grip on such a topic makes you the upper hand during an interview. Linked lists can be implemented using languages like C++ and Java

So, let us look at some crucial operations that are performed while implementing a linked list in Java using class.

## Creating a node

A linked list consists of a node, which contains 2 parts:

• Data →  Contains data to be stored in that particular node.
• Pointer to the next node → Contains address to the next node.

A linked list is a collection of such nodes. The first node is termed the HEAD node, and the last node is called the TAIL node of the linked list.

In Java, a node can be represented as a separate class as shown below:

``````// Linked list Node.
class Node {
public int data;
public Node next;

// Constructor to create a new node.
public Node(int data) {
this.data = data;
this.next = null;
}
}``````

## Insertion

There are three options for insertion in a linked list. They have been discussed below:

### Insertion at the beginning of the list

#### Algorithm

• First, create a new node, NEW_NODE that needs to be inserted at the beginning of the linked list.
• Then, we will make NEXT of NEW_NODE to point to the HEAD node.
• Since the new node will now become the first node, we will make HEAD point to the NEW_NODE.

#### Program

``````// Java program to insert a node at the end of the linked list.
// Linked list node.
class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

// Linked List Class.
public class LinkedList {
public Node head = null;
public Node tail = null;

// Function for inserting a new node at the end of the linked list.
public void insertAtBeginning(int data) {
System.out.println("Inserting a new node having value " + data + " at the beginning of the linked list.");

// Creation of a new node.
Node newNode = new Node(data);

// If this is the first node, set it as 'TAIL' node.
if (head == null) {
tail = newNode;
}

// Changing 'NEXT' of 'NEW_NODE' to point to 'HEAD'.

}

// Function to print the linked list.
public void printList() {

Node current = head;
if (current == null) {
System.out.println("Linked List is empty");
return;
}
while (current != null) {
// Pointer will be incremented subsequently.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public static void main(String[] args)
{
// Creating a linked list (20 -> 60 -> 10 -> 80).

// Adding element 50 at the beginning of the list.
list.insertAtBeginning(50);
list.printList();

// Adding element 40 at the beginning of the list.
list.insertAtBeginning(40);
list.printList();

// Adding element 30 at the beginning of the list.
list.insertAtBeginning(30);
list.printList();

// Adding element 20 at the beginning of the list.
list.insertAtBeginning(20);
list.printList();
}
}``````

Output

``````Inserting a new node having value 50 at the beginning of the linked list.
50
Inserting a new node having value 40 at the beginning of the linked list.
40 50
Inserting a new node having value 30 at the beginning of the linked list.
30 40 50
Inserting a new node having value 20 at the beginning of the linked list.
20 30 40 50``````

Time Complexity

O(1)

### Insertion at the end of the list

#### Algorithm

• We will keep track of the last node with the help of a pointer, say TAIL, for inserting a node at the end of a linked list.
• First, create a new node that needs to be inserted at the end of the linked list.
• Then, we will check if the linked list is already empty or not by checking if HEAD points to NULL or not.
• In case the linked list is empty, the new node will become the first node of our linked list.
• Otherwise, the tail node that initially points to NULL will now point to this newly created node which will now point to NULL.

#### Program

``````// Java program to insert a node at the end of the linked list.
// Linked list node.
class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

// Linked List Class.
public class LinkedList {
public Node head = null;
public Node tail = null;

// Function for inserting a new node at the end of the linked list.
public void insertAtEnd(int data) {
System.out.println("Inserting a new node having value " + data + " at the end of the linked list.");

// Creation of a new node.
Node newNode = new Node(data);

// Checking whether this list is empty or not.
if (head == null) {
// In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
tail = newNode;
} else {
// The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
tail.next = newNode;

// This 'NEW_NODE' will become the 'TAIL' of the linked list.
tail = newNode;
}
}

// Function to print the linked list.
public void printList() {

Node current = head;
if (current == null) {
System.out.println("Linked List is empty");
return;
}
while (current != null) {
// Pointer will be incremented subsequently.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public static void main(String[] args)
{
// Creating a Linked List object.

// Adding element 50 at the end of the list.
list.insertAtEnd(50);
list.printList();

// Adding element 40 at the end of the list.
list.insertAtEnd(40);
list.printList();

// Adding element 30 at the end of the list.
list.insertAtEnd(30);
list.printList();

// Adding element 20 at the end of the list.
list.insertAtEnd(20);
list.printList();
}
}``````

Output

``````Inserting a new node having value 50 at the end of the linked list.
50
Inserting a new node having value 40 at the end of the linked list.
50 40
Inserting a new node having value 30 at the end of the linked list.
50 40 30
Inserting a new node having value 20 at the end of the linked list.
50 40 30 20 ``````

Time Complexity

O(N), where is the number of nodes in the linked list.

### Insertion at a specific position

#### Algorithm

• First, create a node that needs to be inserted in the linked list.
• If the specified position of insertion is 1, this new node is added before the HEAD node.
• Otherwise, iterate up to the specified position and insert this new node at that position.

#### Program

``````// Java program to insert a node at the end of the linked list.

// Linked list node.
class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

// Linked List Class.
public class LinkedList {
public Node head = null;
public Node tail = null;

// Function for inserting a new node at the end of the linked list.
public void insertAtEnd(int data) {
// Creation of a new node.
Node newNode = new Node(data);

// Checking whether this list is empty or not.
if (head == null) {
// In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
tail = newNode;
} else {
// The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
tail.next = newNode;

// This 'NEW_NODE' will become the 'TAIL' of the linked list.
tail = newNode;
}
}

// To insert a node at a given position.
void insertAtPos(int data, int pos) {
Node current = head;
if (pos < 1) {
System.out.print("Invalid position");
return;
}

if (pos == 1) {
Node newNode = new Node(data);
} else {
while (pos-- != 0) {
if (pos == 1) {
Node newNode = new Node(data);
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}
if (pos != 1)
System.out.print("Position out of bound");
}
}

// Function to print the linked list.
public void printList() {

Node current = head;
if (current == null) {
System.out.println("Linked List is empty");
return;
}
while (current != null) {
// Pointer will be incremented subsequently.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public static void main(String[] args) {
// Creating a linked list (10 -> 20 -> 30 -> 40).
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);

System.out.print("Linked List before operations: ");
list.printList();

// Insert a new node at the fifth position.
int data = 48, pos = 5;
list.insertAtPos(data, pos);
System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
list.printList();

// Inserting a new node at the third position.
data = 29;
pos = 3;
list.insertAtPos(data, pos);
System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
list.printList();

// Insert a new node at the sixth position.
data = 44;
pos = 6;
list.insertAtPos(data, pos);
System.out.print("Linked list after adding a new node having value " + data + " at the position " + pos + " is: ");
list.printList();
}
}``````

Output

``````Linked List before operations: 10 20 30 40

Linked list after adding a new node having value 48 at the position 5 is: 10 20 30 40 48

Linked list after adding a new node having value 29 at the position 3 is: 10 20 29 30 40 48

Linked list after adding a new node having value 44 at the position 6 is: 10 20 29 30 40 44 48``````

Time Complexity

O(N), where is the number of nodes in the linked list.

Recommended Topic, Floyds Algorithm

## Deletion

### Algorithm

• First, we will find the node for the key which has to be deleted.
• There can be 3 conditions for this node:
• HEAD node - In this case, the HEAD node will be deleted, and the next node will become the HEAD node.
• Any other node - The previous node of the node to be deleted, will now point to the next node of the deleted node.
• Key is not present in this linked list.

### Program

``````// Java program to insert a node at the end of the linked list.

// Linked list node.
class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

// Linked List Class.
public class LinkedList {
public Node head = null;
public Node tail = null;

// Function for inserting a new node at the end of the linked list.
public void insertAtEnd(int data) {
// Creation of a new node.
Node newNode = new Node(data);

// Checking whether this list is empty or not.
if (head == null) {
// In case the list is empty, the 'HEAD' and 'TAIL' pointers will point to the 'NEW_NODE'.
tail = newNode;
} else {
// The 'NEW_NODE' will be added after the 'TAIL' such that TAIL's next will point to this 'NEW_NODE'.
tail.next = newNode;

// This 'NEW_NODE' will become the 'TAIL' of the linked list.
tail = newNode;
}
}

// Method to delete the node according to the given key.
void deleteNode(int key)
{
// If list is empty.
if (head == null) {
}

// If the key is found at the 'HEAD' of the list.
if (head != null && head.data == key)
{
System.out.println(key + " is deleted");
return;
}

Node current = head, prev = null;

// If the key is not found at the head node.
while (current != null && current.data != key)
{
prev = current;
current = current.next;
}

// If the linked list does not contain the key.
if (current == null)
{
}

// If the linked list contains the key.
if (current != null)
{
prev.next = current.next;
System.out.println(key + " is deleted");
}
}

// Function to print the linked list.
public void printList() {

Node current = head;
if (current == null) {
System.out.println("Linked List is empty");
return;
}
while (current != null) {
// Pointer will be incremented subsequently.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public static void main(String[] args)
{
// Creating a linked list (20 -> 60 -> 10 -> 80 -> 90 -> 0 -> 30 -> 50).

// Inserting values into an empty list.
list.insertAtEnd(20);
list.insertAtEnd(60);
list.insertAtEnd(10);
list.insertAtEnd(80);
list.insertAtEnd(90);
list.insertAtEnd(0);
list.insertAtEnd(30);
list.insertAtEnd(50);

// Printing linked list before deletion.
System.out.print("Linked list before deletion: ");
list.printList();
System.out.println();

// Deleting some keys and printing the list accordingly.
System.out.print("Linked list after deleting element 20: ");
list.deleteNode(20);
list.printList();
System.out.println();

System.out.print("Linked list after deleting element 80: ");
list.deleteNode(80);
list.printList();
System.out.println();

System.out.print("Linked list after deleting element 20: ");
list.deleteNode(20);
list.printList();
System.out.println();
}
}``````

Output

``````Linked list before deletion: 20 60 10 80 90 0 30 50

Linked list after deleting element 20: 20 is deleted

60 10 80 90 0 30 50

Linked list after deleting element 80: 80 is deleted

60 10 90 0 30 50

60 10 90 0 30 50``````

Time Complexity

O(N), where is the number of nodes in the linked list.

Must Read: Java System Out Println

## Frequently Asked Questions

### What is a linked list in C++?

A linked list is a linear data structure that instead of storing data at contiguous memory locations, stores data at random locations, and each node is linked to the other by the use of pointers.

### What are the applications of a linked list?

1. A linked list is used to implement Stack and Queues.
2. A linked list is used to implement hashing(open chain hashing).
3. A linked list is used to implement graphs(Adjacency list representation of graphs)

### How do you delete a node in a linked list?

To delete a node from a linked list, we need to do the following steps.

1. Find the previous node of the node to be deleted.
2. Change the next pointer of the previous node.
3. Free memory for the node to be deleted.

## Conclusion

So, this blog discussed the implementation of a linked list in Java using class. To learn more, head over to Coding Ninjas Studio to practice problems on topics like Linked List, and Graphs, and crack your interviews like a Ninja!