Implementing Stack using Singly Linked List

Linked List Implementation of Stack

A Stack is an ordered list. Insertion and deletion of element is done at top. The last element inserted will the first element for delete or traversal. Hence it is Last In First Out (LIFO) list. The basic stack functionality includes push and pop. Depending on the requirement you can add functionality like top , deleteStack , etc. 

As we are using the linked list implementation , we have the Node class which is  representation of singly linked list. It has data and next attribute.

class Node {
private Integer data;
private Node next;
public Node(Integer data) {
super();
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}

We will have an interface to specify the requirements of the stack.
Note: We are implementing a stack which stores integer values.

interface Stack {
public void push(int data);

public Node pop();

public Node top();

public boolean isEmpty();

public void deleteStack();
}

Now based on the interface we have the below class MyStack which has the implementation of Stack.

class MyStack implements Stack {
private Node headNode;
public void push(int data) {
if (headNode == null) {
headNode = new Node(data);
} else {
Node node = new Node(data);
node.setNext(headNode);
headNode = node;
}
}
public Node top() {
if (headNode == null) {
return null;
} else {
return headNode;
}
}
public Node pop() {
Node node = null;
if (headNode == null) {
System.out.println("stack empty");
} else {
node = headNode;
headNode = headNode.getNext();
}
return node;
}
public boolean isEmpty() {
if (headNode == null) {
return true;
} else {
return false;
}
}
public void deleteStack() {
headNode = null;
}
@Override
public String toString() {
return "MyStack [headNode=" + headNode + "]";
}
}

MyStack class contains headNode which is used for operations of push , pop,etc. 

Below is the MainClass which contaions the main method.

public class MainClass {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(55);
stack.push(12);
stack.push(5);
stack.push(18);
System.out.println(stack);
System.out.println("Top is :" + stack.top().getData());
System.out.println("Pop :" + stack.pop().getData());
System.out.println("Top after one pop :" + stack.top().getData());
}
}

Output:

MyStack [headNode=Node [data=18, next=Node [data=5, next=Node [data=12, next=Node [data=55, next=null]]]]]

Top is :18

Pop :18

Top after one pop :5

In the main method we are inserting 55 , 12 , 5 and 18. The top method will return the top Node having data as 18. Pop will remove 18 from stack. The top will be Node with value 5 after one pop.

Conclusion: Singly Linked List implementation of Stack is very simple.

Intersection Point of Loop in Singly Linked List

Problem Statement:
To find the intersection point of loop in a non null ending singly linked list.

Solution: 
We are using the Node class and the SinglyLinkedList class for implementing singly linked list in java.

Demo:

package com.linkedlist;
import java.util.HashSet;

//Node Class for data and next reference
class Node {
String data;
Node next;
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}

// Singly linked list implementation
class SinglyLinkedList {
Node head;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
// add Node
public void add(String data) {
Node newNode = new Node();
newNode.setData(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.getNext() != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// method for explicit next reference to make loop
public void setNext(int n) {
Node temp1 = head;
Node temp2 = head;
while (temp1.next != null) {
temp1 = temp1.next;
}
for (int i = 1; i < n; i++) {
temp2 = temp2.next;
}
temp1.next = temp2;
}
}
public class MainClass {
public static void main(String[] args) {
// create singly linked list
SinglyLinkedList list = new SinglyLinkedList();
// add 10 nodes where last node points(refers) to null
for (int i = 1; i <= 10; i++) {
list.add("a" + i);
}
// method changing the pointer(reference) of last node
// to a particular node to make it kind of circular
list.setNext(5);
// Use of hashset to find the intersection point
HashSet<Node> set = new HashSet<Node>();
Node temp = list.head;
while (temp.next != null) {
if (!set.add(temp)) {
System.out.println(temp.data);
break;
}
temp = temp.next;
}
}
}

In the implementation class we have a additional function public void setNext(int n) which will make the last node of the singly linked list point to one of the node of the list.

Image 1: Debugging point before setNext method

Image 2: Debugging point after setNext method

Image 3: Linked List Structure before and after setNext method

We are using Hashset to find the intersection point.

Output:
a5

The output shows the intersceion point

Conclusion:
We have used hashset to find whether the element has been already added or not.

equals and hashcode method

Why it is necessary to override equals and hashcode?

This is one of the popular interview question. So lets understand the same practically.
I have class Employee having id and name member variables and I am trying to put few Employee object as key in HashMap.
In this example I am not overriding hashcode and equals method.

Demo1:(Without hashcode and equals)

package com.a;
import java.util.HashMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;

public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
}

public class Demo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "John1");
Employee emp2 = new Employee(2, "Tom2");
Employee emp3 = new Employee(3, "Tom3");
Employee emp4 = new Employee(4, "Tom4");
map.put(emp1, "first");
map.put(emp2, "second");
map.put(emp3, "third");
map.put(emp4, "fouth");
System.out.println(map);
}
}

Possible Output 1:
{Employee [id=2, name=Tom2]=second, Employee [id=3, name=Tom3]=third, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth}

Possible Output 2:
{Employee [id=3, name=Tom3]=third, Employee [id=4, name=Tom4]=fouth, Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first}

From the above output it is clear that every time you execute the code , it will generate different hashcode for your objects and they will go in different buckets.
The hashcode implementation of Object class is native.

In the next example , we are overriding only hashcode.

Demo 2:(With hashcode and Without equals)

package com.a;
import java.util.HashMap;

/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;

public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
}
public class Demo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "John1");
Employee emp2 = new Employee(2, "Tom2");
Employee emp3 = new Employee(3, "Tom3");
Employee emp4 = new Employee(4, "Tom4");
map.put(emp1, "first");
map.put(emp2, "second");
map.put(emp3, "third");
map.put(emp4, "fouth");
System.out.println(map);
}
}

Output: 
{Employee [id=2, name=Tom2]=second, Employee [id=1, name=John1]=first, Employee [id=4, name=Tom4]=fouth, Employee [id=3, name=Tom3]=third}

As we have overriden hashcode and the calculation of hashcode value is on the basis of id and name , everytime you execute it will generate the same hashcode and it will go in the same bucket.

Now lets try to understand why we need equals method.

Demo 3:(With hashcode and Without equals)

package com.a;
import java.util.HashMap;

/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;

public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
}
public class Demo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "John1");
Employee emp2 = new Employee(1, "John1");
map.put(emp1, "first");
map.put(emp2, "second");
System.out.println(map);
}
}

Output:
{Employee [id=1, name=John1]=second, Employee [id=1, name=John1]=first}

From the above output it is clear that even though the contents of the both objects are same and hashcode is also same , they are added in same bucket. The problem here is both the objects are added. The reason is that the Object class has the equals implementation which checks the address and as these are two different objects they are different.

Now lets override equals method.

Demo 4:(With hashcode and equals)

package com.a;
import java.util.HashMap;

/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;

public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Employee other = (Employee) obj;
if (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
}
public class Demo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "John1");
Employee emp2 = new Employee(1, "John1");
map.put(emp1, "first");
map.put(emp2, "second");
System.out.println(map);
}
}

Output:
{Employee [id=1, name=John1]=second}

Now you can see that only one object has been added.

Conclusion: 
It is neccessary to override equals and hashcode function for the class which is added as key in HashMap.