Learn-dsa..in 30 days!



























CC-1 : Implement Stack using LinkedList.

Description:

Create and test a Stack.

In below sections we will code a custom LIFO Stack use using a LinkedList concept. Add() method of the Stack will add the node to start of the Stack and remove() method will remove element from the start of the Stack. We will use a StackNode class to store the individual data of the nodes. The StackNode 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
Stack stack=new Stack();
stack.add(9);
stack.add(14);
stack.add(17);
stack.add(34);
stack.add(21);
stack.add(28); 		Stack nodes: 28 <- 21 <- 34 <- 17 <- 14 <- 9
stack.remove();
stack.remove();
stack.remove(); 		Stack nodes: 17 <- 14 <- 9

Below is the code for the StackNode java class: 

public class StackNode {
	private StackNode nextNode=null;
	private int nodeData=0;
	
	public StackNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(StackNode 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 Stack.

Addition of node to top of Stack.

Pseudocode:

To handle addition of a new node to start of a Stack, we need to handle 2 cases:
If Stack is empty add node as first node of Stack.
Else point new node’s nextNode link to original first node of the stack and set new node as first node of Stack.

Code:

public boolean add(int data){
	StackNode node=new StackNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;
	}
	else {
		node.setNextNode(firstNode);
		firstNode=node;;
		return true;
	}
}

Removal of top node from Stack.

Pseudocode:

To handle removal of top/first node of Stack, we need to handle 2 cases:
If the Stack has only one node, the set first node variable of Stack to null.
If the Stack 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 Stack.

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 Stack (without removing node).

Pseudocode:

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

Code:

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

Get size of Stack.

Pseudocode:

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

Code:

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

Traversing the elements of a Stack.

Pseudocode:

The elements of Stack can be traversed using loops or Iterators:

Code:

public void traverse() {
	StackNode 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