Question

I RE: Singly Linked List, Stack, and Queue Implementation Suppose, you have the following Node clas. public class Node ! int id; Node next: public Node (int id) ( this.id id: Write program codes for the traditional: 1) append int id), prepend(int id), removeFirstNodeO. displayAlINodesO, and findById(int id) operations for a singly linked list 2) pushint id), pop), peek0, displayAllNodes0 operations for a stack 3) enQueue(int id), deQueuel), displayAINodes() operations for a gueue Please make sure that you declare separate and appropriate classes for the singly Linked List, Stack, and Queue that you are going to implement.

Answer 1

Using Java to solve the question :

Head -> A -> B -> C -> Null

The above is a single linked list with 3 nodes A,B,C.We will consider this example for reference throughout this answer

1. Singly Linked List :

append(int id) : In the append operation , the linked list is first traversed till the last and the new node is inserted at the end of linked list

Ex: append(D) implies that , we traverse the link list till C and point C to the newly formed node D

append(int id){
Node newNode = new Node(id);
newNode.next = null;
if(head == null){
head = newNode;
return;
}
Node temp = head;
while(head.next!=null){
temp = temp.next;
}
temp.next = newNode;
return;
}

Prepend : It means that we insert the node at the beginning of the linked list. Point the new node to head and head to new node.
prepend(int id){
Node newNode = new Node(id);
newNode.next = head;
head = newNode;
return;
}

RemoveFirstNode : SInce the head is pointing to the first node , In order to delete the first node , make head point to the second node.In C++ before traversing save the reference to the first node and free the memory of the node to be deleted.
removeFirstNode(){
if(head == null){
return;
}
head = head.next;
return;
}

DisplayAllNodes : Traverse through the linked list and print the data at each and every node.
displayAllNodes(){
Node temp = head;
while(temp != null){
System.out.println(temp.id+"\n");
temp = temp.next;
}
return;
}

FindByID : Traverse through each node ,check if the id at each node is equal to the input id , if true then print ID FOUND and return else repeat the process.If by the end of linked list the Loop does not return then there is no such id in the list then, print ID NOT FOUND and return.
findByID(int id){
Node temp = head;
while(temp != null){
if(temp.id == id){
System.println.out("Id Found\n");
return ;
}
temp = temp.next;
}
System.println.out("Id Not Found\n");
return;
}

2. Stack : In solving this question , we will make use of the above functions we created. If needed you can just replace the code in the function as per your needs.

Stack has a LIFO (Last In First Out) property .That means , from implementation perspective ,that in stack you insert an element at the end and extract an element from the top.

push : push operation is for inserting an element at the beginning of the stack.

we can use prepend function from question - 1
push(int id){
//check for overflow condition if needed
prepend(id);
return;
}

pop : In stack ,we remove an element from the front or top.Hence we can use the remove first node function from question - 1.
pop(){
//check for underflow condition if needed
removeFirstNode();
return;
}

DisplayAllNodes in both the questions is going to remain same,
displayAllNodes(){
displayAllNodes();
return;
}

3.Queues : Queues follow , First in First Out ( FIFO ) , policy , hence in this we insert it in the back but remove it from the front.

enqueue : As we have said ,we insert an element at the end of list in a queue.

enqueue(int id){
append(id);
return;
}

dequeue : We remove the node from the beginning of the queue.
dequeue(){
removeFirstNode():
return;
}
  
displayAllNodes(){
displayAllNodes();
return;
}