CODEWITHSUNDEEP
javagenericslinked-list
bene96
bene96

Reputation: 65

Re-use Linked List for another type (Generic Types)

So I have this linked list class:

public class LinkedList {
    private LLNode rootNode;

    public Node FindItemByData(String data) {
        if(rootNode == null)
            return null;
        else
            return rootNode.findItemByData(data);
    }

And this node class:

public class LLNode {


   LLNode tail; //tail node
   Node data; //some data


   public LLNode(LLNode tail, Node data)
   {
       this.tail = tail;
       this.data = data;
   }

   public Node findItemByData(String data) {
       if(this.data.name.equals(data))
           return this.data;
       else
           return this.tail.findItemByData(data);
   }

I want to re-use the linked list for storing edges in a graph within each Node data of the LLNode. I had a go at replacing the type using Generic Types but this breaks the functionality of the findItemByData function as it relies on data being explicitly declared as a Node.

Is there any way I can reuse this class for multiple types? Or should I not be referring to data.name in a Generic Class?

Implementation context:

public class Graph {

    //USE LINKED LIST
    LinkedList Nodes;
    //Node[] Nodes;   
    int noOfNodes;

    public Graph() {
        noOfNodes = 0;
        //Nodes = new Node[25];
        Nodes = new LinkedList();
    }

    public void AddNode(String name, int x, int y) {
        //Nodes[noOfNodes++] = new Node(name,x,y);
        Nodes.AddItem(new Node(name,x,y));
    }

..

public class Node {
    String name;    //Node's name
    int x,y;        //Node's coords
    LinkedList Adjacencies;
    int noOfAdj = 0;
    int size = 0;


    public Node(String name, int x, int y) {    //Constructor
        this.name = name;
        this.x = x;
        this.y = y;
        Adjacencies = new LinkedList();
    }

    public void addAdjacency(String dest, double distance) {
        Adjacencies.AddItem(new Edge(this.name, dest, distance)); //I want to do this
    }
}

Edit: attempt at using generics:

public class LinkedList<T> {
    private LLNode rootNode;

    public T FindItemByData(String data) {
        if(rootNode == null)
            return null;
        else
            return rootNode.findItemByData(data);
    }
}

public class LLNode<T> {


   LLNode tail; //tail node
   T data; //some data


   public LLNode(LLNode tail, T data)
   {
       this.tail = tail;
       this.data = data;
   }

   public T findItemByData(String data) {
       if(this.data.name.equals(data))
           return (T) this.data;
       else
           return (T) this.tail.findItemByData(data);
   }
}

public class Graph {

    LinkedList<Node> Nodes;
    int noOfNodes;

    public Graph() {
        noOfNodes = 0;
        Nodes = new LinkedList();
    }

    public void AddNode(String name, int x, int y) {
        Nodes.AddItem(new Node(name,x,y));
    }
}

public class Node {
    String name;    //Node's name
    int x,y;        //Node's coords
    LinkedList<Edge> Adjacencies;
    int noOfAdj = 0;
    int size = 0;


    public Node(String name, int x, int y) {    //Constructor
        this.name = name;
        this.x = x;
        this.y = y;
        Adjacencies = new LinkedList();
    }

    public void addAdjacency(String dest, double distance) {
        Adjacencies.AddItem(new Edge(this.name, dest, distance)); //I want to do this
    }
}

Upvotes: 2

Views: 114

Answers (2)

Erick G. Hagstrom
Erick G. Hagstrom

Reputation: 4945

I think your attempt at generics was actually pretty close. It has the advantage of enabling the compiler to tell whether a particular LinkedList holds Nodes or Edges. So I'd suggest that you keep the generic parameterization of LinkedList, but make it mean something a little different. The T should be the kind of data that is held in the LLNode. The trick is that your data has a String name, so you need something from which to extend in order to get that name.

interface Named {
  String getName();
}

public class LinkedList<T extends Named> {
  private LLNode<T> rootNode;
  // etc.
}

public class LLNode<T extends Named> {
  LLNode<T> tail; //tail node
  T data; //some data

  public LLNode(LLNode<T> tail, T data) {
    this.tail = tail;
    this.data = data;
  }

  public T findItemByData(String data) {
    if(this.data.getName().equals(data))
      return this.data;
    else
      return this.tail.findItemByData(data);
  }
  // etc.
}

Now you can instantiate a LinkedList that holds just Nodes, and another that holds just Edges, assuming that both Node and Edge implement Named.

I've mentioned it but want to reemphasize: this is superior to an approach that just uses a supertype of Node and Edge within LinkedList. In that case, you could put both Node and Edge instances in the same LinkedList and the compiler wouldn't be able to warn you. The generic approach gives you the ability to create LinkedList instances that are restricted to Node, or Edge, or unrestricted (new LinkedList<Named>()). In all cases the compiler will give you the support you need to keep the lists straight.

Upvotes: 1

wvdz
wvdz

Reputation: 16641

Basically you are saying that Node and Edge should abide to the same contract. To do this you should both let them implement an interface that contains all the methods that are part of that contract.

In this case this will probably only be getData(). Then use this interface for your methods which can take any Edge or Node.

Another way to do this would be to make Edge an extension of Node. public class Edge extends Node. Then you can use it whereever a Node is needed.

Upvotes: 1

Related Questions