Learn-dsa..in 30 days!



























CC-1 : Implement FIFO Queue Using LinkedList.

Description:

Create and test a FIFO Queue Using LinkedList.

In below sections we will code a custom FIFO Queue use using a LinkedList concept. add() method of the Queue will add the node to start of the Queue and remove() method will remove element from the end of the Queue. We will use a QueueNode class to store the individual data of the nodes. The QueueNode below stores integer data, it can easily be modified to store String, Char, or custom classes as data.

Test cases and expected outputs:

Input Parameters Expected outputs
Queue queue=new Queue();
queue.add(9);
queue.add(14);
queue.add(17);
queue.add(34);
queue.add(21);
queue.add(28); 		Queue nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28
queue.remove();
queue.remove();
queue.remove(); 		Queue nodes: 34 <- 21 <- 28

Below is the code for the QueueNode java class: 

public class QueueNode {
	private QueueNode nextNode=null;
	private int nodeData=0;
	public QueueNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(QueueNode nextNode) {
		this.nextNode = nextNode;
	}	
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
}

Next, let’s see the logic involved in adding/ deleting nodes from FIFO Queues.

Addition of node to end of Queue.

Pseudocode:

To handle addition of a new node to end of a Queue, we need to handle 2 cases:
If Queue is empty add node as first node of Queue.
Else locate the last node of Queue and add new node as last node of Queue.

Code:

public boolean add(int data){
	QueueNode node=new QueueNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;
	}
	else {
		QueueNode currentNode=firstNode;
		while (currentNode.getNextNode()!=null) {
			currentNode=currentNode.getNextNode();
		}
		currentNode.setNextNode(node);
		node.setNextNode(null);
		return true;			
	}
}

Removal of first node from Queue.

Pseudocode:

To handle removal of first node of Queue, we need to handle 2 cases:
If the Queue has only one node, the set first node variable of Queue to null.
If the Queue already has more than one nodes, then remove the first node and return data of first node and set second node as the first node of the Queue.

Code:

public int remove() {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	int removedData=firstNode.getNodeData();
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return removedData;
	}
	firstNode=firstNode.getNextNode();
	return removedData;
}

Get value of first node of Queue (without removing node).

Pseudocode:

We can code a get() method to return data of first node of Queue without removing it.

Code:

public int get() {
	if (firstNode !=null) {
		return firstNode.getNodeData();
	}
	return Integer.MIN_VALUE;
}

Get size of Queue.

Pseudocode:

We can code a getSize() method to return count of elements in the Queue.

Code:

public int getSize() {
	QueueNode currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}

Traversing the elements of a Queue.

Pseudocode:

The elements of queue can be traversed using loops or Iterators.

Code:

public void traverse() {
	QueueNode currentNode=firstNode;
	while (currentNode !=null) {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us