Programs based on
linked list
Browser History (Back and Forward Navigation)
• Problem:Implement browser history where:User can visit new [Link] back to previous [Link] forward to next page.
class Page {
String url;
Page prev, next;
Page(String url) {
[Link] = url;
}
}
class Browser {
Page current;
void visit(String url) {
Page newPage = new Page(url);
if (current != null) {
[Link] = newPage;
[Link] = current;
}
void back() {
if (current != null && [Link] != null)
current = [Link];
}
void forward() {
if (current != null && [Link] != null)
current = [Link];
}
void printCurrent() {
[Link]("Current page: " + (current != null ? [Link] : "None"));
}
}
Call Center Queue (Customer Service Line)🔍 Problem:A call center handles calls one by one in the order received (FIFO). Implement this.
class Call {
String customerName;
Call next;
Call(String name) {
[Link] = name;
}
}
class CallQueue {
Call front, rear;
void enqueue(String name) {
Call newCall = new Call(name);
if (rear == null) {
front = rear = newCall;
} else {
[Link] = newCall;
rear = newCall;
}
void dequeue() {
if (front == null) return;
front = [Link];
if (front == null) rear = null;
}
void showFront() {
[Link]("Now serving: " + (front != null ?
[Link] : "None"));
}
}
M u s ic P la y lis t
• Model a playlist where:You can go to next or previous [Link] can add/remove songs dynamically. Doubly Linked List
class Song {
String name;
Song prev, next;
Song(String name) { [Link] = name; }
}
class Playlist {
Song current;
void addSong(String name) {
Song song = new Song(name);
if (current == null) current = song;
else {
[Link] = current;
[Link] = song;
current = song;
}
}
void nextSong() {
if (current != null && [Link] != null)
current = [Link];
void prevSong() {
if (current != null && [Link] != null)
current = [Link];
}
void play() {
[Link]("Playing: " + (current != null ? [Link] :
"None"));
}
}
Train Coach Management
• Each train coach is connected. You can add, remove, or rearrange
coaches
• Solution
• Each coach = Node in a Doubly Linked List.
• Example Actions
• Add a coach at the end
• Remove a coach by name
• Insert a coach before or after a specific coach
• Display coaches from front to end
• Display coaches from end to front
class Coach {
String name;
Coach prev, next;
Coach(String name) {
[Link] = name;
}
}
class Train {
Coach head = null, tail = null;
// Add coach at the end
void addCoach(String name) {
Coach newCoach = new Coach(name);
if (head == null) {
head = tail = newCoach;
} else {
[Link] = newCoach;
[Link] = tail;
tail = newCoach;
}
}
•
// Remove coach by name
void removeCoach(String name) {
Coach current = head;
while (current != null) {
if ([Link](name)) {
if ([Link] != null)
[Link] = [Link];
else
head = [Link];
if ([Link] != null)
[Link] = [Link];
else
tail = [Link];
[Link]("Removed coach: " + name);
return;
}
current = [Link];
}
[Link]("Coach " + name + " not found.");
}
// Insert a coach after a specific coach
void insertAfter(String afterCoach, String newCoachName) {
Coach current = head;
while (current != null) {
if ([Link](afterCoach)) {
Coach newCoach = new Coach(newCoachName);[Link] = [Link];
[Link] = current;
if ([Link] != null)
[Link] = newCoach;
else
tail = newCoach;
[Link] = newCoach;
[Link]("Inserted coach " + newCoachName + " after " + afterCoach);
return;
}
current = [Link];
}
[Link]("Coach " + afterCoach + " not found.");
}
// Print coaches from front to end
void printForward() {
[Link]("Train (front to end): ");
Coach current = head;
while (current != null) {
[Link]([Link] + " ");
current = [Link];
}
[Link]();
}
// Print coaches from end to front
void printBackward() {
[Link]("Train (end to front): ");
Coach current = tail;
while (current != null) {
[Link]([Link] + " ");
current = [Link];
}
[Link]();
}
Merge Product Listings from Two
VendorsTwo
• vendors list their products as arrays of product objects.
• Each product has:
• Product ID
• Name
• Price
• We will:
• Convert each vendor's array into a linked list of products.
• Merge both product lists into a single sorted linked list (by price).
• Display the final merged product catalog.
class Product {
int id;
String name;
double price;
Product(int id, String name, double price) {
[Link] = id;
[Link] = name;
[Link] = price;
}
}
class Node {
Product product;
Node next;
Node(Product product) {
[Link] = product;
[Link] = null;
}
public class MergeProductListings {
// Convert Product[] array to Linked List
public static Node arrayToLinkedList(Product[] products) {
if ([Link] == 0) return null;
Node head = new Node(products[0]);
Node current = head;
for (int i = 1; i < [Link]; i++) {
[Link] = new Node(products[i]);
current = [Link];
}
return head;
}
// Merge two sorted product lists by price
public static Node mergeSortedProductLists(Node list1, Node list2) {
Node dummy = new Node(null);
Node tail = dummy;
while (list1 != null && list2 != null) {
if ([Link] < [Link]) {
[Link] = list1;
list1 = [Link];
} else {
[Link] = list2;
list2 = [Link]; }
tail = [Link]; }
• [Link] = (list1 != null) ? list1 : list2;
• return [Link];
• }
• // Print the merged product catalog
• public static void printProductList(Node head) {
• [Link]("Product ID | Name | Price");
• [Link]("-------------------------------");
• while (head != null) {
• Product p = [Link];
• [Link]("%10d | %-10s | %.2f\n", [Link], [Link], [Link]);
• head = [Link];
• }
• }
• // Main method
• public static void main(String[] args) {
• Product[] vendorA = {
• new Product(101, "Shoes", 2999.00),
• new Product(102, "T-Shirt", 999.00),
• new Product(103, "Jeans", 1999.00)
• };
• Product[] vendorB = {
• new Product(201, "Cap", 499.00),
• new Product(202, "Bag", 1499.00),
• new Product(203, "Watch", 2499.00)
• };
• // Sort arrays by price (if not sorted already)
• [Link](vendorA, (a, b) -> [Link]([Link], [Link]));
• [Link](vendorB, (a, b) -> [Link]([Link], [Link]));
• // Convert arrays to linked lists
• Node listA = arrayToLinkedList(vendorA);
• Node listB = arrayToLinkedList(vendorB);
• // Merge sorted linked lists
• Node mergedCatalog = mergeSortedProductLists(listA, listB);
• // Display final product catalog
• [Link]("Merged E-commerce Product Catalog:");
• printProductList(mergedCatalog);
