Linked list inside a linked list

[viperlasson]

Hello... I have a project where I'm supposed to create one linked list, where each node in that list (Graph Nodes) also contains a linked list (Adjacent Nodes). It's a simple singular linked list, and I've created the main one easily, but having issues thinking how to have each of it's nodes have their own linked list... I've created two separate Node classes, one for gNodes, and the other for aNodes. And in the gNode class, I have aNode objects like prev, curr, and head.

Here's my code for the two classes

class gNode
{
	private int element; //holds an int for graph list
	private gNode next; //reference to next graph node
	
	aNode head, prev, curr;
	
	//constructors node accepts a value and next node
	public gNode (int e, gNode n)
	{
		element = e;
		next = n;
	}
	//returns element
	public int getElement()
	{
		return element;
	}  
	//returns next node
	public gNode getNext()
	{
		return next;
	}
	//sets the element
	public void setElement(int e)
	{
		element = e;
	}
	//sets the node
	public void setNext(gNode n)
	{
		next = n;
	}
	
	
	//insert an adjacent node into the gNode's list
	boolean adjInsert (int value, int value2)
	{
	    if (adjExists(value))
	    {
	    	System.out.println (value + " already exists as an adjacency node to graph node " + value2 + ", did not insert " + value + ".");
	    	return false;
	    }

	  prev = null;
	  curr = head;
	    
	  while (curr != null)
	  {
	    prev = curr;
	    curr = curr.getNext();
	  }
	    
	  //makes a new node temp and sets value to it
	  aNode temp = new aNode ('\0', null);
	  temp.setElement(value);
	  temp.setNext(curr);
	    
	  //if the list was empty
	  if (prev == null)
		  head = temp;
	  //if list was not empty ... middle or end insert
	  else
	    prev.setNext(temp);
	    
	  System.out.println (value + " inserted as adjacent node to graph node " + value2 + ".");
	  return true;
	}
	  
	  //Adjacent Node exist method
	  public boolean adjExists (int value)
	  {
		  curr = head;
		  
		  //traverses through list, breaks out of loop if it sees value in it. 
		  //If it doesn't find, it will go all the way to the end, putting curr to null
		  while ((curr != null) && (curr.getElement() != value))
			  curr = curr.getNext();
		
		  if (curr == null)
			  return false;
		  else
			  return true;
	  }
	  
	 
	  //lists all adjacent nodes tied to this graph node
	  public void listAllaNodes (int value)
	  {
		 // if (curr == null)
		//	  System.out.println("EMPTY");
		//  else
		 // {
		  System.out.print ("Listing all adjacent nodes to graph node " + value + ": ");
			for (aNode temp = head; temp != null; temp = temp.getNext())
			{
				System.out.print(temp.getElement() + ", ");
			}
			System.out.println();
			System.out.println();
			//System.out.println("head is " + head);
		  }
		 // }
	  
} //end gNode class
	
class aNode
{
	private int element; //holds an int
	private aNode next; //reference to next node
	//constructors node accepts a value and next node
	public aNode (int e, aNode n)
	{
		element = e;
		next = n;
	}
	//returns element
	public int getElement()
	{
		return element;
	}  
	//returns next node
	public aNode getNext()
	{
		return next;
	}
	//sets the element
	public void setElement(int e)
	{
		element = e;
	}
	//sets the node
	public void setNext(aNode n)
	{
		next = n;
	}
} //end aNode class

At first I thought it was working, but now it seems like every graph node shares the same adjacency list. I don't know why this is happening, since each gNode should have their own aNode objects... Unless I'm thinking about this the wrong way.


Any help would be appreciated!

[viperlasson]

Anyone? I'm just having issues with all the nodes in gNode sharing the same linked list aNode.

This is what I have going on in the main

		graph g1 = new graph();
		
		g1.insert(5);
		g1.insert(6);
		g1.insert(7);

		
		g1.ADJinsert(6, 5);
		g1.ADJinsert(7, 6);

		g1.listAllaNodesS(6);

and here is the output

5 inserted as a graph node.
6 inserted as a graph node.
7 inserted as a graph node.
5 inserted as adjacent node to graph node 6.
6 inserted as adjacent node to graph node 7.
Listing all adjacent nodes to graph node 6: 5, 6,

graph node 6 should not have 6 in it's list, it should be in 7's list.


actually, now that I look at it, I said that all of the gNodes share the aNode list, which is wrong. 7's list is actually empty, so everything is going into one gNode right now.

Edit: Man, I should just wait and work on it more before I post haha. It seems to be working to what I want it to do now, had to mess with my ADJinstert method a little bit.

Here is the output now

5 inserted as a graph node.
6 inserted as a graph node.
7 inserted as a graph node.
5 inserted as adjacent node to graph node 7.
6 inserted as adjacent node to graph node 6.
Listing all adjacent nodes to graph node 7: 5, 
Listing all adjacent nodes to graph node 6: 6,

I'm happy haha, this project is getting confusing

[Qmatt]

Hey, Do you mind, posting your working code, like the graph class and main which are not here?

Anyone? I'm just having issues with all the nodes in gNode sharing the same linked list aNode.

This is what I have going on in the main

		graph g1 = new graph();
		
		g1.insert(5);
		g1.insert(6);
		g1.insert(7);

		
		g1.ADJinsert(6, 5);
		g1.ADJinsert(7, 6);

		g1.listAllaNodesS(6);

and here is the output

5 inserted as a graph node.
6 inserted as a graph node.
7 inserted as a graph node.
5 inserted as adjacent node to graph node 6.
6 inserted as adjacent node to graph node 7.
Listing all adjacent nodes to graph node 6: 5, 6,

graph node 6 should not have 6 in it's list, it should be in 7's list.


actually, now that I look at it, I said that all of the gNodes share the aNode list, which is wrong. 7's list is actually empty, so everything is going into one gNode right now.

Edit: Man, I should just wait and work on it more before I post haha. It seems to be working to what I want it to do now, had to mess with my ADJinstert method a little bit.

Here is the output now

5 inserted as a graph node.
6 inserted as a graph node.
7 inserted as a graph node.
5 inserted as adjacent node to graph node 7.
6 inserted as adjacent node to graph node 6.
Listing all adjacent nodes to graph node 7: 5, 
Listing all adjacent nodes to graph node 6: 6,

I'm happy haha, this project is getting confusing

[viperlasson]

Do you need help with something in particular? This was a project I did a couple months ago while cramming for finals, the code is pretty messy and confusing. I DO have the code, but just giving people code isn't what this forum is about :)

[Qmatt]

Yes I understand, it fair enough, I have a similar problem and wanted to understand it better because I got stack when I used LinkedList so I want to know how you implimented your insert() method (ie g1.insert(5);), With my own I am struggling to use the size() method to get the number of degree of a particular vertex but going to your idea I think I can make it work but didnt understand how you use you insert vertex with you insert() method. If you don't mind I can go into your messy and confusing code and will work it out.

[viperlasson]

I'm a little confused of what you need, so I'll help you out the easy way. This is the code I came up with for my insert in the graph class.

//insert a new GNODE
	  public boolean insert (int value)
	  {
	    if (exists(value))
	    {
	    	System.out.println (value + " already exists as a graph node, did not insert " + value + ".");
	    	return false;
	    }
	    
	    prev = null;
	    curr = head;
	    
	    while (curr != null)
	    {
	    	prev = curr;
	    	curr = curr.getNext();
	    }
	    
	    //makes a new node temp and sets value to it
	    gNode temp = new gNode ('\0', null);
	    temp.setElement(value);
	    temp.setNext(curr);
	    
	    //if the list was empty
	    if (prev == null)
	    	head = temp;
	    //if list was not empty ... middle or end insert
	    else
	    	prev.setNext(temp);
	    
	    System.out.println (value + " inserted as a graph node.");
	    return true;
	  }

That part is simple, our prof gave us most of that. We had to come up with adding adjacent nodes to those graph nodes, thus making a linked list.