Type casting within my reference to Node class

Question

I am using breadth First Search to traverse an array list. Right now I have a Graph class, and a Node class. The problem I am having is this line :for(Node adj : n.adjacentNodes){ and I think it has to do with the type casting of this line: Node n = (Node)q.poll();

The compiler doesn't like this, but why is this? What could I change for the compiler to except that my object n is of type Node and that I am trying to traverse it in this for loop?

Here is my code:

Node Class:

    import java.util.*;

public class Node {

        public String data; // data element
        public boolean visited=false; // flag to track the already visited node
        public List adjacentNodes = new LinkedList(); // adjacency list
        public Node rootNode;

        public Node(String data){
            this.data = data;
        }

        public void addAdjacentNode(final Node node){
            adjacentNodes.add(node);
            node.adjacentNodes.add(this);
            adjacentNodes.add(rootNode);
            node.adjacentNodes.add(this);
        }

    }

And my graph class:

 import java.util.*;


/*- enqueue the start node to a Queue
- make the start node as visited
- while queue is not empty
  - dequeue the node lets say u
  - print or whatever you want to
  - for every adjacent node v of u
      - if v is not already visited
          - mark v as visited
          - enqueue v to the Queue*/
public class Graph {

    public List nodes = new ArrayList();

    public void breadthFirstTraversal(Node rootNode){
        Queue<Node> q = new LinkedList<Node>();
//      Queue q = new LinkedList();
        q.add(rootNode);
        printNode(rootNode);
        rootNode.visited=true;
        while(!q.isEmpty()){
            Node n = (Node)q.poll();
            System.out.print(n.data + " ");
            for(Node adj : n.adjacentNodes){
                if(!adj.visited){
                    adj.visited=true;
                    q.add(adj);
                }
            }
            clearNodes();
        }

    }

    private void clearNodes() {
        // TODO Auto-generated method stub
        nodes = null;   //clear nodes and set to null
    }

    private void printNode(Node node) {
        // TODO Auto-generated method stub
        System.out.print(node);
    }

    public static void main(String[] args) {

        Node frankfurt = new Node("frankfurt");
        Node mannheim = new Node("mannheim");
        Node wurzburg = new Node("wurzburg");
        Node stuttgard = new Node("stuttgard");
        Node kassel = new Node("kassel");
        Node karlsruhe = new Node("karlsruhe");
        Node erfurt = new Node("erfurt");
        Node numberg = new Node("numberg");
        Node augsburg = new Node("augsburg");
        Node munchen = new Node("munchen");

        Graph g = new Graph();

        g.nodes.add(frankfurt);
        g.nodes.add(mannheim);
        g.nodes.add(wurzburg);
        g.nodes.add(stuttgard);
        g.nodes.add(kassel);
        g.nodes.add(karlsruhe);
        g.nodes.add(erfurt);
        g.nodes.add(numberg);
        g.nodes.add(augsburg);
        g.nodes.add(munchen);

        frankfurt.addAdjacentNode(mannheim);
        frankfurt.addAdjacentNode(wurzburg);
        frankfurt.addAdjacentNode(kassel);

        mannheim.addAdjacentNode(karlsruhe);

        karlsruhe.addAdjacentNode(augsburg);

        augsburg.addAdjacentNode(munchen);

        munchen.addAdjacentNode(kassel);
        munchen.addAdjacentNode(numberg);

        wurzburg.addAdjacentNode(erfurt);
        wurzburg.addAdjacentNode(numberg);

        numberg.addAdjacentNode(stuttgard);

        g.breadthFirstTraversal(frankfurt);
    }

}

Answer 1

when declaring your queue if you specify the 'Type' of elements it will be storing then you wouldnt need the cast. Queue q = new LinkedList();

Correct way :

Queue<Node> q = new LinkedList<Node>();

Answer 2

Yes, you have to do the typecasting in this case. As in Java, you are implementing QUEUE using LinkedList. We know that LinkedList always contains two values in each container, one is valued and another is the address to the next container. So we can be called each and every container as an object as it always contains two types of dataStructure.

So when you run queue.poll() it will give you an object containing two data structure one is the data you enqueued in the queue and another is the address. So we have to do typecasting to get the desired datatype. so compiler needs Node n = (Node)q.poll();