A linked list is a linear data structure, containing a sequence of nodes. Each node consists of data and the link to the next node. It is a data structure that uses a recursive data type called Node.
The size of a linked list isn’t fixed. It can vary by adding new nodes or by deleting the existing nodes. This is an advantage over arrays.
Linked Lists are of two types:
- Singly Linked List: In this linked list, a given node can only point to the next node.
- Doubly Linked List: In this linked list, a given node can point to the previous node as well as the next node.
To create a node, dynamic memory allocation is needed. In Java, the new keyword is used to allocate dynamic memory from the space available in the heap memory.
In Java, occupied memory is deallocated automatically when an object in memory is not referred by a reference variable. This automatic deallocation of memory is known as garbage collection.
Following are the basic operations that can be performed in a linked list:
- Insert a node
- Delete a node
- Traversing a list
- Searching for a node
- Reverse a list
An attempt to delete a node from an empty linked list leads to underflow.
import java.util.Scanner;
class Node{
int data;
Node link;
public Node(){
data = 0;
link = null;
}
public Node(int d){
data = d;
link = null;
}
public Node(int d, Node l){
data = d;
link = l;
}
}
class LinkedList{
Node start;
public LinkedList(){
start = null;
}
public void insert(int d){
Node n = new Node(d, null);
if(start == null)
start = n;
else{
Node current = start;
Node next = start.link;
while(next != null){
current = next;
next = next.link;
}
current.link = n;
}
}
public void delete(int d){
if(start == null){
System.out.println("LINKED LIST IS EMPTY");
return;
}
if(start.data == d){
start = start.link;
return;
}
Node previous = null;
Node current = start;
while(current != null && current.data != d){
previous = current;
current = current.link;
}
if(current == null){
System.out.println(d + " NOT FOUND");
return;
}
previous.link = current.link;
}
public void display(){
if(start == null)
System.out.println("LINKED LIST IS EMPTY");
else{
Node current = start;
while(current != null){
System.out.print(current.data + " ");
current = current.link;
}
System.out.println();
}
}
public Node reverse(){
Node previous = null;
Node current = start;
while(current != null){
Node next = current.link;
current.link = previous;
previous = current;
current = next;
}
return previous;
}
public boolean search(int d){
if(start == null)
return false;
Node current = start;
while(current != null){
if(current.data == d)
return true;
current = current.link;
}
return false;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
LinkedList obj = new LinkedList();
while(true){
System.out.println("1. INSERT NODE");
System.out.println("2. DELETE NODE");
System.out.println("3. DISPLAY NODES");
System.out.println("4. REVERSE LIST");
System.out.println("5. SEARCH NODE");
System.out.print("ENTER YOUR CHOICE: ");
int choice = Integer.parseInt(in.nextLine());
switch(choice){
case 1:
System.out.print("DATA TO BE INSERTED: ");
int d = Integer.parseInt(in.nextLine());
obj.insert(d);
break;
case 2:
System.out.print("DATA TO BE DELETED: ");
d = Integer.parseInt(in.nextLine());
obj.delete(d);
break;
case 3:
obj.display();
break;
case 4:
obj.start = obj.reverse();
break;
case 5:
System.out.print("DATA TO BE SEARCHED: ");
d = Integer.parseInt(in.nextLine());
if(obj.search(d))
System.out.println(d + " IS AVAILABLE");
else
System.out.println(d + " IS UNAVAILABLE");
break;
default:
System.out.println("BYE");
return;
}
}
}
}Sample Question on Linked List
Write a Java program to create a linked list that contains one integer as data item in each of its nodes. The class details of each node are as follows:
class Node{
int item;
Node next;
}Perform following operations on the linked list:
1. Add nodes in ascending order of the elements.
2. Delete a node from the linked list.
3. Traverse the linked list.
4. Search for a particular item in the linked list and also display its position if found, otherwise display an appropriate message.
5. Reverse the linked list.
Write a menu-driven Java program to perform the operations mentioned above.
import java.util.Scanner;
class Node {
int item;
Node next;
Node(int item){
this.item = item;
this.next = null;
}
}
class LinkedList{
private Node head;
public void insert(int value){
Node newNode = new Node(value);
if(head == null || value < head.item){
newNode.next = head;
head = newNode;
return;
}
Node current = head;
while (current.next != null && current.next.item < value){
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
public void delete(int value){
if (head == null){
System.out.println("List is empty. Nothing to delete.");
return;
}
if (head.item == value){
head = head.next;
System.out.println(value + "deleted ");
return;
}
Node current = head;
while (current.next != null && current.next.item != value){
current = current.next;
}
if (current.next == null){
System.out.println("Item " + value + " not found.");
}
else{
current.next = current.next.next;
System.out.println("Deleted " + value);
}
}
public void traverse(){
if (head == null){
System.out.println("List is empty.");
return;
}
Node current = head;
while (current != null){
System.out.print(current.item + "-->");
current = current.next;
}
System.out.println("null");
}
public void search(int value){
Node current = head;
int pos = 1;
while (current != null){
if (current.item == value){
System.out.println("Item " + value + " found at position " + pos);
return;
}
current = current.next;
pos++;
}
System.out.println("Item " + value + " not found in the list.");
}
public void reverse(){
Node prev = null;
Node current = head;
Node next = null;
while (current != null){
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
System.out.println("Linked list reversed.");
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
LinkedList list = new LinkedList();
while(true){
System.out.println("1. Insert Node");
System.out.println("2. Delete Node");
System.out.println("3. Traverse List");
System.out.println("4. Search Node");
System.out.println("5. Reverse List");
System.out.print("Enter your choice: ");
int choice = Integer.parseInt(in.nextLine());
switch(choice){
case 1:
System.out.print("Item to be inserted: ");
int i = Integer.parseInt(in.nextLine());
list.insert(i);
break;
case 2:
System.out.print("Item to be deleted: ");
i = Integer.parseInt(in.nextLine());
list.delete(i);
break;
case 3:
list.traverse();
break;
case 4:
System.out.print("Item to be searched: ");
i = Integer.parseInt(in.nextLine());
list.search(i);
break;
case 5:
list.reverse();
break;
default:
System.out.println("Bye...");
return;
}
}
}
}Year 2020
A linked list is formed from the objects of the class Node. The class structure of the Node is given below:
class Node{
int n;
Node next;
}Write an algorithm OR a method to find the product of the integers from an existing linked list.
The method declaration is as follows:
void product_node(Node str)
void product_node(Node str){
if(str == null)
System.out.println("Product = 0");
else{
int p = 1;
while(str != null){
p *= str.n;
str = str.next;
}
System.out.println("Product = " + p);
}
}Year 2018
A linked list is formed from the objects of the class Node. The class structure of the Node is given below:
class Node{
int n;
Node link;
}Write an algorithm OR a method to search for a number from an existing linked list.
The method declaration is as follows:
void findNode(Node str, int b)
void findNode(Node str, int b){
if(str == null)
System.out.println("Not found!");
else{
boolean found = false;
while(str != null){
if(b == str.n){
found = true;
break;
}
str = str.link;
}
if(found)
System.out.println(b + " found!");
else
System.out.println("Not found!");
}
}Year 2016
A linked list is formed from the objects of the class Node. The class structure of the Node is given below:
class Node{
String name;
Node next;
}Write an algorithm OR a method to search for a a given name in the linked list.
The method declaration is given below:
boolean searchName(Node start, String v)
boolean searchName(Node start, String v){
if(start == null)
return false;
else{
while(start != null){
if(v.equalsIgnoreCase(start.name))
return true;
start = start.next;
}
return false;
}
}Year 2014
A linked list is formed from the objects of the class:
class Node{
int number;
Node nextNode;
}Write an algorithm or a method to add a node at the end of an existing linked list.
The method declaration is as follows:
void addnode(Node start, int num)void addnode(Node start, int num){
Node n = new Node(num);
if(start == null)
start = n;
else{
Node current = start;
Node next = start.nextNode;
while(next != null){
current = next;
next = next.nextNode;
}
current.nextNode = n;
}
}Year 2013
A linked list is formed from the objects of the class:
class Node{
int item;
Node next;
}Write an algorithm or a method to count the number of nodes in the linked list.
The method declaration is given below:
int count(Node ptr_start)int count(Node ptr_start){
if(ptr_start == null)
return 0;
return 1 + count(ptr_start.next);
}Year 2012
A linked list is formed from the objects of the class:
class node{
int p;
String n;
node next;
}Write an algorithm or a method to search for a name and display the contents of the node. The method declaration is given below:
void search(node start, String b)void search(node start, String b){
Node current = start;
while(current != null){
if(current.n.equals(b)){
System.out.println(b + " FOUND");
return;
}
current = current.next;
}
System.out.println(b + " NOT FOUND");
}Year 2011
A linked list is formed from the objects of the class:
class Node{
int info;
Node link;
}Write an algorithm or a method for deleting a node from a linked list.
The method declaration is given below:
void deletenode(Node start)public void deletenode(Node start){
Scanner in = new Scanner(System.in);
System.out.print("Enter node to be deleted: ");
int d = Integer.parseInt(in.nextLine());
if(start == null){
System.out.println("LINKED LIST IS EMPTY");
return;
}
if(start.info == d){
start = start.link;
return;
}
Node previous = null;
Node current = start;
while(current != null && current.info != d){
previous = current;
current = current.link;
}
if(current == null){
System.out.println(d + " NOT FOUND");
return;
}
previous.link = current.link;
}