Stack

A Stack is a Last In, First Out (LIFO) data structure, which means that the most recently added element is the first one to be removed. Think of it like a stack of pancakes where you can only add or remove on the top. The basic Stack commands are push (add on top), pop (remove from top), and peek (see what is on top without removing it)

In Java, you can use the Stack class of the JDK.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        System.out.println(stack); // [a, b, c, d]
        
        // get the last element without removing it 
        System.out.println(stack.peek()); // d

        while (!stack.isEmpty()) {
            // pop elements from the last (it removes them!)
            System.out.println(stack.pop()); // d c b a
        }

        System.out.println(stack); // empty []

    }
}

Note that Stack of the JDK extends Vector, and thus allow operations like inserting and removing elements at arbitrary positions in the underlying array. Basically, you can violate the LIFO principle of Stack if you use the Vector methods, be careful! However, this also give you flexibility as in some cases you want to change the Stack without adhere to the LIFO principle.

What is Vector of the JDK? It’s a legacy (old) class, which does not have as good performance as ArrayList or LinkedList. You can use the follwoing alternatives:

Deque<String> stack = new ArrayDeque<>();

or

Deque<String> stack = new LinkedList<>();

A concrete example on when Stack can be useful is when implementing the “undo” functionality of a text editor. Every time a user modifies the text, the action is pushed to the stack. When undoing, you simply remove the last action by popping it off the stack, effectively reversing the recent change.

Queue

A Queue is a First In, First Out (FIFO) data structure, which means that the first element added is the first one to be removed. Think of it like a line of people waiting for a ticket, where the first person to join the line is the first one to get the ticket. The basic Queue commands are add, remove, and peek

In Java, you can implement a Queue using the Queue interface and LinkedLsit as implementation.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.add("a");
        queue.add("b");
        queue.add("c");
        queue.add("d");
        System.out.println(queue); // [a, b, c, d]
        
        // get the first element without removing it 
        System.out.println(queue.peek()); // a

        while (!queue.isEmpty()) {
            // remove elements from the first
            System.out.println(queue.remove()); // a b c d
        }

        System.out.println(queue); // empty []
    }
}

A concrete example on when using Queue will be appropriate is when implementing a printer, which should adhere to FIFO.

Deque

A Deque is a double-ended queue, which supports insertion and deletion at both ends. This makes it a hybrid of a stack and a queue. You can use the LinkedList as implementation using Deque as interface.

import java.util.LinkedList;
import java.util.Deque;

public class Main {
  public static void main(String[] args) {
    Deque<String> deque = new LinkedList<>();
    deque.add("a");
    deque.push("b");
    deque.add("c");
    deque.push("d");
    System.out.println(deque); // [d, b, a, c]
    
    // get the first element without removing it 
    System.out.println(deque.peek()); // d
    System.out.println(deque.peekFirst()); // d
    
    // get the last element without removing it 
    System.out.println(deque.peekLast()); // c
    
    System.out.println(deque.pop()); // d
    System.out.println(deque.remove()); // b

    System.out.println(deque); // empty [a, c]
}
}

You can also use ArrayDeque as implementation using Deque as interface.

Deque<String> stack = new ArrayDeque<>(); 

ArrayDeque has better performance than LinkedList for situations that need frequently accessed elements at both ends of the deque, LinkedList has better performance than ArrayDeque with frequent insertions and removals at arbitrary positions.

A concrete example on when Deque can be useful is when implementing a web browser’s navigation history. You can use a deque to implement the back and forward buttons. As the user navigates through pages, URLs are added to the back of the deque. Pressing the back button removes URLs from the back of the deque, and pressing the forward button removes URLs from the front of the deque.

Graphs

Graph is a data structure for storing connected data. A graph consists of nodes (also called vertices) and edges. A node represents the entity and an edge represents the relationship between entities. For example, you can use graphs to represent network of people on a social media platform (e.g., Facebook); nodes are the people and the edges are friendship relations. Graphs are also very useful when modeling telecommunications and transportation networks.

Does JDK have a Graph Data structure ? No Why? Graph implementations can be very different, a general Graph might not turn out to be very useful. There are many types of Graphs (directed, undirected, weighted).

There are, of course, external libraries that offer Graphs implementations. However, often it is better to have a customized Graph to better fit the intended usage, let’s implement one.

Node (Vertex)

First, you need to create your Node class. If you want to use primitive data as nodes, you can use wrapper classes (e.g., Integer, Double, and Float) to represent primitive data types as objects. However, it is often better to have a dedicated class. For example, we want to model a network of people, so we have a class Person as nodes of the Graph.

Make sure that you @Override the equals and hashcode methods as we need them to compare and find nodes in the Graph. If you don’t do that, the Graph will consider two nodes to be different as long as they are different reference in memory regardless of the content of their instance fields.

For example, let’s consider a Person class:

public class Person {
  private String id;
  private String name;
  private String lastName;

  public Person(String id, String name, String lastName) {
    this.id = id;
    this.name = name;
    this.lastName = lastName;
  }

  @Override
  public String toString() {
    return "Person [id=" + id + ", name=" + name + ", lastName=" + lastName + "]";
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((id == null) ? 0 : id.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;
    Person other = (Person) obj;
    if (id == null) {
      if (other.id != null)
        return false;
    } else if (!id.equals(other.id))
      return false;
    return true;
  }
} 

Note that the only id field is used for the hashCode and equals methods. Indeed, it’s possible for multiple people to have the same combination of name and lastname.

Edges

The implementation of the edges of the Graph depends on what kind of graph we want.

Main types of Graphs are directed (the edges have a direction, the relation is not symmetric) undirected (the relation is symmetric), weighted or unweighted.

For directed and weighted graphs makes sense to have a dedicated class for edges.

class Edge {
        private Node to;
        private Node from;
        private Integer weight;
    }

This class specifies the direction of the edge and the weight of the connection. For example, the “follow” relations in X (former Twitter) is one-way relationship, because a person A can follow person B, but not vice-versa. It implies a connection from A to B but not necessarily from B to A. So, for directed graphs we need to specify the direction of the relationship. The class above uses to and from to specify the direction.

However, let’s say that we want to model the “friendship” relation of Facebook. If there is an edge between nodes A and B, it implies that there is a friendship connection from A to B and from B to A. As friendship on Facebook are mutual. In this case, we don’t need a separate class, we can keep track of the relationships using a Map.

public class Graph {
 private Map<Person, List<Person>> adjNodes;

 public Graph() {
   this.adjNodes = new HashMap<>();
 }

adjNodes maps for each node N in the Graph a list of adjacent nodes, that is the list of nodes that have a relationship with node N.

Let’s see the addNode operation:

public void addNode(Person node) {
   adjNodes.putIfAbsent(node, new ArrayList<>());
 }

The Map method putIfAbsent puts in the map a new key only if it is absent in the map. Otherwise, if we use put instead of putIfAbsent we will replace the adjacent list with an empty one. Map checks for equivalent keys (to know if a key is absent or not) using equals. As such, make sure you @Override the default implementation!

 public void addEdge(Person node1, Person node2) {
   adjNodes.get(node1).add(node2);
   adjNodes.get(node2).add(node1);
 }

addEdge adds node2 in the adjacent list of node1 and vice-versa. Note that we are assuming that the nodes are already in the Graph. Otherwise, the method will throw a NullPointerException. We can modify the method as follows to make sure that the nodes will be added in the Graph if are not there.

 public void addEdge(Person node1, Person node2) {
   addNode(node1);
   addNode(node2);
   adjNodes.get(node1).add(node2);
   adjNodes.get(node2).add(node1);
 }

For removing a node N, we need to first remove the entry in the map with N as the key. Then, we need to scan the adjNodes maps and remove N from all the list of adjacent nodes.

 public void removeNode(Person node) {
   adjNodes.remove(node);
   for (Person key : adjNodes.keySet()) {
     adjNodes.get(key).remove(node);
   }
 }

For remove an edge:

 public void removeEdge(Person node1, Person node2) {
  adjNodes.getOrDefault(node1, new ArrayList<>()).remove(node2);
   adjNodes.getOrDefault(node2, new ArrayList<>()).remove(node1);
 }

getOrDefault returns the content associated to the key or empty list new ArrayList<>() if the map does not contain that key. We need to do this otherwise we will have NullPointerException. Alternatively, we can check the content of the map before we remove the element.

 public void removeEdge(Person node1, Person node2) {
   if (adjNodes.containsKey(node1) && adjNodes.containsKey(node2) ){
	   adjNodes.get(node1).remove(node2);
	   adjNodes.get(node2).remove(node1);
   }
 }

To print the adjNodes we can do like this

 public String toString() {
   StringBuilder sb = new StringBuilder();
   for (Node n : adjNodes.keySet()) {
     sb.append(n);
     sb.append("->");
     sb.append(adjNodes.get(n));
     sb.append(System.lineSeparator());
   }
   return sb.toString();
 }

Remember that we should use a StringBuilder in this case as we should not concatenate a String inside a loop.

Graph traversal

Given a Graph, we often need to traverse the Graph to search something or to extract properties of the Graph. There are two main algorithms to traverse a graph: Breadth-First Search (BFS) and Depth-First Search (DFS)

Both of these algorithms start the search from a pre-defined node called root.

Breadth-First Search (BFS):

Starting from the root, BFS explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. In other words, it traverses the graph level by level.

BFS is typically used to find the shortest path between two nodes or to explore all nodes within a certain distance from the starting node.

BFS can be implemented using a queue data structure, where nodes are visited in the order they were encountered (avoiding infinite loop by making sure to visit each node only one time).

public List<Node> breathFirstTraversal(Node root) {
   List<Node> visited = new ArrayList<>();
   Queue<Node> queue = new LinkedList<>();
   queue.add(root);
   visited.add(root);
   while (!queue.isEmpty()) {
       Node node = queue.poll();
       for (Node n : adjNodes.get(node)) {
           if (!visited.contains(n)) {
               visited.add(n);
               queue.add(n);
           }
       }
   }
   return visited;
 }

Depth-First Search (DFS):

Starting from the root, BFS explores as far as possible along each branch before backtracking. In other words, it traverses the graph level by level.

DFS can be used to find cycles in a Graph: When performing DFS, if it is encountered an edge that connects a node to one of its ancestors in the DFS tree, it indicates the presence of a cycle.

DFS can be implemented using a stack data structure.

 public List<Node> depthFirstTraversal(Node root) {
   List<Node> visited = new ArrayList<>();
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   while (!stack.isEmpty()) {
     Node node = stack.pop();
     if (!visited.contains(node)) {
       visited.add(node);
       for (Node n : adjNodes.get(node)) {
         stack.push(n);
       }
     }
   }
   return visited;
 }

Here’s a simple example to illustrate the difference between BFS and DFS:

Let’s say we have a graph represented as follows:

       A
     / | \
    B  C  D
   / \    |
  E   F   G

If we start the traversal from node A:

BFS: We would visit nodes in the order A, B, C, D, E, F, G.

DFS: We would visit nodes in the order A, B, E, F, C, D, G.

In BFS, we explore all nodes at the current depth level before moving to the next level, while in DFS, we explore as far as possible along each branch before backtracking.

Both algorithms have their own strengths and weaknesses, and the choice between them depends on the specific problem at hand and on the characteristics of the graph.

BFS is better if

• The search graph has cycles or is infinite, or
• We need the shortest path to a solution, or
• There are some solutions at shallow depth.

DFS is better if

• There are only solutions at great depth, or
• Memory is limited

You might wonder why the visited check

   if (!visited.contains(node)) {
       visited.add(node);

it is outside the innder loop for DFS but inside the inner loop for BFS.

DFS: The check is outside the inner loop, immediately after popping from the stack, because nodes are pushed onto the stack without checking if they have been visited. This ensures nodes are only processed once when they are popped.

BFS: The check is inside the inner loop, ensuring that nodes are added to the queue and marked as visited only if they haven’t been visited before, maintaining the level-order exploration of BFS.

Java Generics

Until now, we have worked with examples where the type of the graph nodes is fixed. How can we create a data structure that works for any type of object? We use Java Generics!

• The key idea is to support parametric types.
• Thus, classes and interfaces operate on data types that can be changed like a parameter.
• Classes, interfaces, and methods operating on parametric types are called generic classes, interfaces, or methods.
• This allows us to define a data structure agnostic to the data types it will operate on.
• It ensures type-safe operations. Type safety ensures that expressions and assignments are done using consistent types. This ensures that what the programmer intends at compile time happens at runtime.

You have used generics before!

For example:

List<Integer> list = new ArrayList<>();

Inside <>, you specify the object type of the elements in the list. This feature is called a generic, and it allows type safety at compile time:

List<String> list = new ArrayList<>();
list.add("Hello");
list.add(123); // COMPILATION ERROR: `123` is an Integer, not a String

With generics, you can do this without needing to cast:

String message = list.get(0);

Without specifying the type, it defaults to java.lang.Object, and you need to cast:

List list = new ArrayList();
list.add("Hello");
String message = (String) list.get(0); // Explicit cast needed

While with generics:

List<String> list = new ArrayList<>();
list.add("Hello");
String message = list.get(0); // No cast needed, type is known

With generics, we can create a data structure like a graph that can be used with any type.

class Graph<T> {
    private Map<T, List<T>> adjacencyMap;

    public Graph() {
        this.adjacencyMap = new HashMap<>();
    }

    public void addVertex(T node) {
        adjacencyMap.putIfAbsent(node, new LinkedList<>());
    }

    public void addEdge(T node1, T node2) {
        addVertex(node1);
        addVertex(node2);
        adjacencyMap.get(node1).add(node2);
        adjacencyMap.get(node2).add(node1);
    }
}

We can then create a graph of Strings, Integers, or any custom object:

Graph<String> stringGraph = new Graph<>();

We can restrict the types that can be used as type parameters with bounded type parameters using extends:

public class Graph<T extends Number> {
    // Class implementation
}

This means the graph can only be used with types that are subclasses of Number (e.g., Integer, Double).

Wildcards

Wildcards allow more flexibility when working with generic types. There are three types of wildcards:

Unbounded Wildcards (?):

public void printList(List<?> list) {
    for (Object elem : list) {
        System.out.println(elem);
    }
}

This method can accept a list of any type.

Bounded Wildcards with an Upper Bound (? extends Type):

public void processNumbers(List<? extends Number> list) {
    for (Number num : list) {
        System.out.println(num.doubleValue());
    }
}

This method can accept a list of any type that is a subclass of Number.

Bounded Wildcards with a Lower Bound (? super Type):

public void addNumbers(List<? super Integer> list) {
    list.add(10); // Can add Integer or any subclass of Integer
}

This method can accept a list of any type that is a superclass of Integer (including Integer itself).

Generic Interfaces

Interfaces can also use generic:

public interface Pair<K, V> {
    public K getKey();
    public V getValue();
}

public class OrderedPair<K, V> implements Pair<K, V> {
    private K key;
    private V value;

    public OrderedPair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}

import java.util.*;

class Graph<T> {
  private Map<T, List<T>> adjacencyMap;

  public Graph() {
    this.adjacencyMap = new HashMap<>();
  }

  public void addVertex(T node) {
    adjacencyMap.putIfAbsent(node, new LinkedList<>());
  }

  public void addEdge(T node1, T node2) {
    addVertex(node1);
    addVertex(node2);
    adjacencyMap.get(node1).add(node2);
    adjacencyMap.get(node2).add(node1);
  }

  public List<T> detectCycleFromNode(T startNode) {
   //implement method
  }

  
  public static void main(String[] args) {
    Graph<Integer> graph = new Graph<>();
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 2); // Creates a cycle: 2 -> 3 -> 4 -> 2
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 3); // Creates another cycle: 3 -> 5 -> 6 -> 3
    findCycle(graph, 1); // No cycle detected starting from node 1 and endind in node 1
    findCycle(graph, 2); // Cycle detected starting from node 2 and endind in node 2: [2, 4, 3, 2]
    findCycle(graph, 3); // Cycle detected starting from node 3 and endind in node 3: [3, 6, 5, 3]
    findCycle(graph, 4); // Cycle detected starting from node 4 and endind in node 4: [4, 2, 3, 4]
    findCycle(graph, 5); // Cycle detected starting from node 5 and endind in node 5: [5, 6, 3, 5]
    findCycle(graph, 6); // Cycle detected starting from node 6 and endind in node 6: [6, 3, 5, 6]
  }

  private static void findCycle(Graph<Integer> g, Integer node) {
    List<Integer> cycle = g.detectCycleFromNode(node);
    if (cycle != null) {
      System.out.println(
          "Cycle detected starting from node "
              + node
              + " and endind in node "
              + node
              + ": "
              + cycle);
      return;
    } 
    System.out.println(
          "No cycle detected starting from node " + node + " and endind in node " + node);
    
  }
}