DSA Assignment - 2
1Q . Write a Program to implement single linked list and its
opera ons.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
class Sllst {
Node head;
public void insatbeg(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
public void insatend(int data) {
ti
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
temp.next = newNode;
public void delatbeg() {
if (head != null) {
head = head.next;
public void delatend() {
if (head == null) {
return;
if (head.next == null) {
head = null;
return;
Node temp = head;
while (temp.next.next != null) {
temp = temp.next;
temp.next = null;
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
System.out.println("null");
public boolean search(int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) {
return true;
temp = temp.next;
return false;
}
public class Llst {
public static void main(String[] args) {
Sllst list = new Sllst();
list.insatbeg(10);
list.insatbeg(20);
list.insatend(30);
list.insatend(40);
list.display();
list.delatbeg();
list.display();
list.delatend();
list.display();
System.out.println(list.search(30));
System.out.println(list.search(50));
2Q.Write a Program to implement doubly
linked list and its operations
class Node {
int data;
Node prev, next;
Node(int data) {
this.data = data;
this.prev = this.next = null;
class DoublyLinkedList {
Node head;
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head != null) {
head.prev = newNode;
newNode.next = head;
head = newNode;
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
public void deleteAtBeginning() {
if (head == null) return;
if (head.next == null) {
head = null;
return;
head = head.next;
head.prev = null;
public void deleteAtEnd() {
if (head == null) return;
if (head.next == null) {
head = null;
return;
Node temp = head;
while (temp.next != null) {
temp = temp.next;
temp.prev.next = null;
}
public void displayForward() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.next;
System.out.println("null");
public void displayBackward() {
if (head == null) return;
Node temp = head;
while (temp.next != null) {
temp = temp.next;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.prev;
System.out.println("null");
public boolean search(int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) {
return true;
}
temp = temp.next;
return false;
public class DoublyLinkedListDemo {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.displayForward();
list.deleteAtBeginning();
list.displayForward();
list.deleteAtEnd();
list.displayForward();
list.displayBackward();
System.out.println(list.search(30));
System.out.println(list.search(50));
3Q.A train is travelling from new Delhi to
Trivandrum, initially it started with 20
compartments, after some hours of journey
(at Bhopal) delinked 9 and 12 compartments,
at Nagpur link some more compartments at the
end of train. Each compartment will have 60
members, store 60 member’s details for each
compartments.
import java.util.ArrayList;
import java.util.List;
class Passenger {
String name;
int age;
String seatnum;
Passenger(String name, int age, String seatnum) {
this.name = name;
this.age = age;
this.seatnum = seatnum;
public String toString() {
return "Name: " + name + ", Age: " + age + ", Seat: "
+ seatnum;
}
class Compartment {
int compnum;
List<Passenger> passengers;
Compartment(int compnum) {
this.compnum = compnum;
this.passengers = new ArrayList<>();
public void addPassenger(String name, int age, String
seatnum) {
passengers.add(new Passenger(name, age, seatnum));
public void displayPassengers() {
System.out.println("Compartment " + compnum + ":");
for (Passenger passenger : passengers) {
System.out.println(passenger);
class Train {
List<Compartment> compartments;
Train(int initialCompartmentCount) {
compartments = new ArrayList<>();
for (int i = 1; i <= initialCompartmentCount; i++) {
compartments.add(new Compartment(i));
public void delinkCompartment(int... compnum) {
for (int compnum : compnum) {
compartments.removeIf(c -> c.compnum == compnum);
public void linkCompartment(int numofnewcomp) {
int currentSize = compartments.size();
for (int i = 1; i <= numofnewcomp; i++) {
compartments.add(new Compartment(currentSize +
i));
public void displayTrainDetails() {
for (Compartment compartment : compartments) {
compartment.displayPassengers();
public class TrainJourney {
public static void main(String[] args) {
Train train = new Train(20);
for (Compartment compartment : train.compartments) {
for (int i = 1; i <= 60; i++) {
compartment.addPassenger("Passenger" + i, 30,
"Seat" + i);
train.delinkCompartment(9, 12);
train.linkCompartment(3);
train.displayTrainDetails();
