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

Question

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
    }
}

To clarify, The Nodes Linked List stores objects of type Node, where as the Adjacencies Linked List needs to be of type Edge. — bene96
– bene96, Commented Mar 2, 2016 at 14:30
Hey Erick, the code shown is prior to my attempt at generics. I tried public class LLNode<T> {..} and declaring data as T data but this did not work as LLNode's methods relied on a Node type (findItemByData) — bene96
– bene96, Commented Mar 2, 2016 at 14:44

wvdz · Accepted Answer · 2016-03-02 14:30:45Z

1

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.

answered Mar 2, 2016 at 14:30

wvdz

16.2k4 gold badges60 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

bene96 Over a year ago

It worked! To clarify for anyone else, I extended the Edge class and created an empty constructor inside the Node class.

Erick G. Hagstrom · Accepted Answer · 2016-03-02 15:26:13Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related