Linked lists are dynamic data structures that consist of nodes, each containing data and a reference to the next node. They are particularly useful when frequent insertions and deletions are required. Today's challenges covered foundational concepts and problems with linked lists.
1. Implement a Singly Linked List with Insertion, Deletion, and Traversal
Create a singly linked list that supports the basic operations:
Insertion: Add a node at the beginning, end, or any position.
Deletion: Remove a node by value or position.
Traversal: Print all the nodes in the list sequentially.
import java.util.Scanner;
class Node{
protected int data = 0;
protected Node next = null;
public Node(int data, Node next){
this.data = data;
this.next = next;
}
}
class LinkedList{
private static Node start = null;
public static void InsertAtBeginning(int data){
Node temp = new Node(data, start);
start = temp;
Display();
}
public static void InsertAtEnd(int data){
Node temp = start;
while(temp.next!=null)
temp = temp.next;
Node node = new Node(data, null);
temp.next = node;
Display();
}
public static void InsertAfterAnElement(int data1, int data2){
Node temp = start;
while(temp.data!=data2)
temp = temp.next;
Node node = new Node(data1, temp.next);
temp.next = node;
Display();
}
public static void InsertBeforeAnElement(int data1, int data2){
Node temp = start;
while(temp.next.data!=data2)
temp = temp.next;
Node node = new Node(data1, temp.next);
temp.next = node;
Display();
}
public static void DeleteAtBeginning(){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else
start = start.next;
Display();
}
public static void DeleteAtEnd(){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.next!=null)
temp = temp.next;
temp.next = null;
}
Display();
}
public static void DeleteAfterAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void DeleteBeforeAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.next.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void DeleteAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void Display(){
if(start == null){
System.out.println("LinkedList is empty!!!");
return;
}
Node temp = start;
while(temp!=null){
System.out.print(" --> "+temp.data);
temp = temp.next;
}
System.out.println();
}
}
public class SingleLinkedList {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("What action would you like to perform:\n1. Insertion\n2. Deletion\n3. Display");
switch(sc.nextInt()){
case 1:
System.out.println("Where would you like to insert:\n1. Beginning\n2. End\n3. After an element\n4. Before an element");
switch(sc.nextInt()){
case 1:
System.out.print("Emter the data: ");
LinkedList.InsertAtBeginning(sc.nextInt());
break;
case 2:
System.out.print("Enter the data: ");
LinkedList.InsertAtEnd(sc.nextInt());
break;
case 3:
System.out.print("Enter the data of the node after which you want to Insert your Node: ");
int data = sc.nextInt();
System.out.println("Enter the data: ");
LinkedList.InsertAfterAnElement(sc.nextInt(), data);
break;
case 4:
System.out.print("Enter the data of the node before which you want to Insert your Node: ");
data = sc.nextInt();
System.out.println("Enter the data: ");
LinkedList.InsertBeforeAnElement(sc.nextInt(), data);
break;
default:
System.out.println("Invalid Input!!!");
break;
}
break;
case 2:
System.out.println("Which element would you like to delete:\n1. First\n2. Last\n3. After an element\n4. Before an element\n5. Giving its data");
switch(sc.nextInt()){
case 1:
LinkedList.DeleteAtBeginning();
break;
case 2:
LinkedList.DeleteAtEnd();
break;
case 3:
System.out.println("Enter the element whose next element you want to delete");
LinkedList.DeleteAfterAnElement(sc.nextInt());
break;
case 4:
System.out.println("Enter the element whose previous element you want to delete");
LinkedList.DeleteBeforeAnElement(sc.nextInt());
break;
case 5:
System.out.print("Enter the data of the Node you want ot delete: ");
LinkedList.DeleteAnElement(sc.nextInt());
break;
default:
System.out.println("Invalid Input!!!");
break;
}
break;
case 3:
LinkedList.Display();
break;
case 4:
System.out.println("Invalid Input!!!");
break;
}
}
}
}
2. Reverse a Linked List
Reverse the order of nodes in a singly linked list, such that the first node becomes the last and vice versa.
import java.util.LinkedList;
public class ReverseLinkedList {
public static LinkedList Reverse(LinkedList ll){
LinkedList<Integer> ans = new LinkedList<>();
for(int i = ll.size()-1; i>=0; i--){
ans.add((Integer) ll.get(i));
}
return ans;
}
public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(3);
ll.add(4);
ll.add(5);
System.out.println("Linked List: ".concat(ll.toString()));
LinkedList<Integer> revll = Reverse(ll);
System.out.println("Reversed Linked List: ".concat(revll.toString()));
}
}
3. Detect a Cycle in a Linked List
Using Floyd’s Cycle Detection algorithm, determine if a linked list contains a cycle by employing two pointers moving at different speeds.
import java.util.Scanner;
class Node{
protected int data = 0;
protected Node next = null;
public Node(int data, Node next){
this.data = data;
this.next = next;
}
}
class LinkedList{
private static Node start = null;
public static void InsertAtBeginning(int data){
Node temp = new Node(data, start);
start = temp;
Display();
}
public static void InsertAtEnd(int data){
if(start == null){
start = new Node(data, null);
return;
}
Node temp = start;
while(temp.next!=null)
temp = temp.next;
Node node = new Node(data, null);
temp.next = node;
//Display();
}
public static void InsertAfterAnElement(int data1, int data2){
Node temp = start;
while(temp.data!=data2)
temp = temp.next;
Node node = new Node(data1, temp.next);
temp.next = node;
Display();
}
public static void InsertBeforeAnElement(int data1, int data2){
Node temp = start;
while(temp.next.data!=data2)
temp = temp.next;
Node node = new Node(data1, temp.next);
temp.next = node;
Display();
}
public static void DeleteAtBeginning(){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else
start = start.next;
Display();
}
public static void DeleteAtEnd(){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.next!=null)
temp = temp.next;
temp.next = null;
}
Display();
}
public static void DeleteAfterAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void DeleteBeforeAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.next.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void DeleteAnElement(int data){
if(start == null)
System.out.println("LinkedList is already Empty!!!");
else{
Node temp = start;
while(temp.next.data!=0)
temp = temp.next;
temp.next = temp.next.next;
}
Display();
}
public static void Display(){
if(start == null){
System.out.println("LinkedList is empty!!!");
return;
}
Node temp = start;
while(temp!=null){
System.out.print(" --> "+temp.data);
temp = temp.next;
}
System.out.println();
}
public static void CycleFormation(){
Node temp = start;
while(temp.next!=null)
temp = temp.next;
temp.next = start;
}
public static boolean CycleDetection(){
Node tortoise = start;
Node rabbit = start;
while(rabbit.next!=null){
if(rabbit == tortoise)
return true;
else{
rabbit = rabbit.next.next;
tortoise = tortoise.next;
}
}
return false;
}
}
public class LoopDetection {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
LinkedList.InsertAtEnd(1);
LinkedList.InsertAtEnd(2);
LinkedList.InsertAtEnd(3);
LinkedList.InsertAtEnd(4);
System.out.println("LinkedList before Cycle Formation: ");
LinkedList.Display();
LinkedList.CycleFormation();
if(LinkedList.CycleDetection())
System.out.println("Cycle Exists");
else
System.out.println("Cycle doesn't exist");
}
}
4. Merge Two Sorted Linked Lists
Merge two sorted linked lists into a single sorted linked list by comparing nodes from each list sequentially.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class MergeSortedLinkedLists {
public static Node mergeTwoLists(Node l1, Node l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.data < l2.data) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
public static void display(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node l1 = new Node(1);
l1.next = new Node(3);
l1.next.next = new Node(5);
Node l2 = new Node(2);
l2.next = new Node(4);
l2.next.next = new Node(6);
Node merged = mergeTwoLists(l1, l2);
display(merged);
}
}
5. Find the Middle Element of a Linked List
Using the two-pointer technique, find the middle node of the linked list in a single traversal.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class FindMiddle {
public static Node findMiddle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
Node middle = findMiddle(head);
System.out.println("Middle Element: " + middle.data);
}
}
Reflection
Day 10 introduced essential problems that are commonly encountered in technical interviews. Implementing linked list operations and solving related problems solidified my understanding of their structure and applications. Looking forward to tackling more advanced concepts next! 🚀