Linked Lists. Not sure where to go from here.

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

30 Replies - 1615 Views - Last Post: 03 November 2014 - 03:10 PM Rate Topic: ***-- 2 Votes

#1 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 06:45 AM

Basically, the program is to be able to read information from a file like this;

11111 63.5
22222 59.9
33333 82.4
44444 73.1
55555 77.3
66666 99.5
77777 68.7
88888 53.2
99999 66.8

where the first number is student number and the second is their grade. I need to read this information from a .txt file and dynamically create a new node containing that studentís number and mark, and insert it in the correct position in the linked list (in descending order based on grade).
So I get that each Node needs to contain two data types, an Int for Student # and a Double for their grade, and I'm pretty sure I've done it correctly with my StudentNode class which can be found in the source code linked above.

But what I don't get it using that class to create Nodes in my main class and then sort them based on their Double grade value WHILE they are being sorted.
I just don't understand where to actually put the methods and such that does these things.

Apparently I'm supposed to have three classes. One named StudentNode which is just the node info, which I have done.

The second is called StudentList which is apparently supposed to contain the head of LinkedList and the methods I need? I'm not sure how it ties into StudentNode though.

The third and final is just the main class which I'll use to test it.

Then after all that I need to print out the median mark through a recursive method that isn't allowed to use any loops or call and functions/methods that use loops. The function should return the node in the list which contains the median mark. Secondly, in order to find the median, you need to know how many items in total are in the list. Your recursive function must calculate that number (also recursively); you may not keep track of this count elsewhere your program. Your recursive solution should only examine each node only once, and the depth of the recursion should be equal to the number of nodes in the list.

I haven't the slighted clue on how to do that.

Can anyone give me some pointers or help? I'd really appreciate it.

Here's my current in-progress code.

import java.io.FileNotFoundException;
import java.util.Scanner;
 
class StudentNode {
	
	private int studentNum;
	private double grade;
    private StudentNode next;
 
    public StudentNode(int newStudentNum, double newGrade) {
    	studentNum = newStudentNum;
    	grade = newGrade;
    	next = null;
    }
    
    public StudentNode(int newStudentNum, double newGrade, StudentNode nextNode) {
    	studentNum = newStudentNum;
    	grade = newGrade;
    	next = nextNode;
    }
    
    public void setData(int newStudentNum, double newGrade) {
    	studentNum = newStudentNum;
    	grade = newGrade;
    } 
    
    public int getStudentNum() {
    	return studentNum;
    } 
    
    public double getGrade(){
    	return grade;
    }
    
    public void setNext(StudentNode nextNode) {
    	next = nextNode;
    }
    
    public StudentNode getNext() {
    	return next;
    }
    
} 
 
class StudentList { 
 
    StudentNode head;
 
    public StudentList(){
    	studentNum = 0;
    	grade = 0;
    }
    
    public StudentList(int studentNum, double grade) { 
 
       head = new StudentNode(studentNum, grade);
 
    }
}
 
public class Assignment3 {
 
	Scanner input = new Scanner(System.in);
	
	public static void main (String []args){
		
	}
	
	public void loadFromFile(String filename) throws FileNotFoundException { 
    	
    	java.io.File file = new java.io.File("a1data.txt");
		input = new Scanner(file);
		
		StudentList myList = new StudentList();
		
        while(input.hasNextLine()){
        	myList.add(getNext());
        }
    } 
	
}


I'm pretty sure the StudentNode class is fine, it's the StudentList class that I'm not sure about. I'm not sure how to add nodes since there isn't a getNext() method in the StudentList class.

Is This A Good Question/Topic? 0
  • +

Replies To: Linked Lists. Not sure where to go from here.

#2 aks29921  Icon User is offline

  • D.I.C Regular

Reputation: 116
  • View blog
  • Posts: 345
  • Joined: 24-August 09

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 07:00 AM

To get you started, a comparator would be needed in your StudentList class.
Have you used comparators before?
Was This Post Helpful? 0
  • +
  • -

#3 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 07:07 AM

That's the interface right? I've never had much experience with interface but the assignment says they are encouraged but not required. Will it make this easier?
Was This Post Helpful? 0
  • +
  • -

#4 aks29921  Icon User is offline

  • D.I.C Regular

Reputation: 116
  • View blog
  • Posts: 345
  • Joined: 24-August 09

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 07:17 AM

View PostDylanLyon, on 29 October 2014 - 07:07 AM, said:

That's the interface right? I've never had much experience with interface but the assignment says they are encouraged but not required. Will it make this easier?

Yes, comparator would serve the functionality you need nicely. You need to order custom data types based on some given criteria. I suggest you google "comparator in java". A lot of examples/tutorials would come up. Go through one or more of them and try to get as much clarity (concept-wise) as possible. Then come back to your problem and apply your learning. In the process, if you are stuck and uncertain at any point, post the code that you have at that point here and I am sure myself or someone else would provide you with more guidance.
Was This Post Helpful? 1
  • +
  • -

#5 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 08:18 AM

Honestly, I don't have the first idea on how to do it. I'm so frustrated right now I can't even think straight. I'm trying to learn all these different methods and Linked Lists from scratch because my Professor has a very strong accent/lisp and the lecture notes only cover how to make a Node class, not a list class so I'm flying completely blind here.

I don't know what the Linked List class needs to contain or how to use Linked Lists from scratch like this, especially ones with two parameters (studentnumber and grade) because it just throws me off.

So I need to use an interface. Do I implement the interface in the StudentNode class? Or just the StudentList class? It would have to be the StudentList class right? Since that is where I need to use the compare method? But how would I also use the same method to add nodes to the List? There needs to be one method that sorts the nodes as they are being read from the file.

So I need to be able to compare the two node objects, then add them into the list at a specified index. So that means the add method needs t o be able to insert at a certain index right?

I'm really confused right now.
Was This Post Helpful? 0
  • +
  • -

#6 aks29921  Icon User is offline

  • D.I.C Regular

Reputation: 116
  • View blog
  • Posts: 345
  • Joined: 24-August 09

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 08:58 AM

View PostDylanLyon, on 29 October 2014 - 08:18 AM, said:

Honestly, I don't have the first idea on how to do it. I'm so frustrated right now I can't even think straight. I'm trying to learn all these different methods and Linked Lists from scratch because my Professor has a very strong accent/lisp and the lecture notes only cover how to make a Node class, not a list class so I'm flying completely blind here.

I don't know what the Linked List class needs to contain or how to use Linked Lists from scratch like this, especially ones with two parameters (studentnumber and grade) because it just throws me off.

So I need to use an interface. Do I implement the interface in the StudentNode class? Or just the StudentList class? It would have to be the StudentList class right? Since that is where I need to use the compare method? But how would I also use the same method to add nodes to the List? There needs to be one method that sorts the nodes as they are being read from the file.

So I need to be able to compare the two node objects, then add them into the list at a specified index. So that means the add method needs t o be able to insert at a certain index right?

I'm really confused right now.


You need to clear your mind. Calm down and look at the problem from a fresh perspective (what you have and what you want). I cannot teach you comparators here, neither can I code for you.
Yes you have to compare two nodes based on custom criteria. When you have associated a comparator to your linked list, it will handle addition of new elements to the list.
So you need to go through the tutorials/examples and come back here when you have an exact idea of what you want to do and you have tried doing it yourself (and hopefully some code to show).
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12297
  • View blog
  • Posts: 45,399
  • Joined: 27-December 08

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 09:06 AM

I have a tutorial on Linked Lists you may find helpful.

Quote

insert it in the correct position in the linked list (in descending order based on grade).

Are you familiar with Insertion Sort? You should look at adopting this algorithm.

While a Comparator is certainly helpful and probably in good design to use, let's focus for the moment on getting your understanding of the Linked List up to speed. We can revisit whether or not you want to use a Comparator later and explain where it would go.
Was This Post Helpful? 0
  • +
  • -

#8 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 09:50 AM

I actually think I got it really close to working.

So here is what I have as of now.

import java.io.FileNotFoundException;
import java.util.Scanner;

public class Assignment3 {

		Scanner input = new Scanner(System.in);

	public static void main (String []args){
	
	}
	
	public void loadFromFile(String filename) throws FileNotFoundException { 
	
		java.io.File file = new java.io.File("test1.txt");
		input = new Scanner(file);
	
		StudentList myList = new StudentList();
	
    	while(input.hasNextLine()){
    		myList.add(getNext());
    	}
	} 

}


class StudentList { 

	
    private StudentNode head;
    
    public void setHead(StudentNode headNode) {
    	head = headNode;
    }
    	
    public StudentNode getHead() {
    	return head;
    }
    	
    public StudentList(){
    	//head = new StudentNode();
    }
    	
    public void add(StudentNode newNode) {
        newNode.setNext(getHead());
        setHead(newNode);
    }
    
    public StudentList(int studentNum, double grade){ 
    	head = new StudentNode(studentNum, grade);
    }
		

    class StudentNode {
    	
    	private int studentNum;
    	private double grade;
        private StudentNode next;

        public StudentNode(int newStudentNum, double newGrade) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        	next = null;
        }
        
        public StudentNode(int newStudentNum, double newGrade, StudentNode nextNode) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        	next = nextNode;
        }
        
        public void setData(int newStudentNum, double newGrade) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        } 
        
        public int getStudentNum() {
        	return studentNum;
        } 
        
        public double getGrade(){
        	return grade;
        }
        
        public void setNext(StudentNode nextNode) {
        	next = nextNode;
        }
        
        public StudentNode getNext() {
        	return next;
        }
        
    }
    
}


The problem I have now is that I get an error in my loadFromFile() method on the line

myList.add(getNext());


and it says that getNext() is undefined for the type Assignment 3. That's a scope issue right?

Them after that I'm not sure how I would actually read from file because I would need to create a class for the method and the main to use the method right?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12297
  • View blog
  • Posts: 45,399
  • Joined: 27-December 08

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 09:55 AM

The getNext() method is defined for your StudentNode class. Note that you really shouldn't be inserting anyNode.getNext() into your List, as the element is already there. Consider the example. If I have Nodes (not using Java syntax, but just illustrating the point conceptually):
someStudentNode := (11111, 63.5)
someStudentNode.next := (22222, 59.9)



So right now, the Node containing (22222, 59.9) is already in the LinkedList because someStudentNode.next points to it. So you don't need to insert someStudentNode.getNext().

You actually aren't parsing the File and reading the data into StudentNode objects. That's your biggest issue right now.
Was This Post Helpful? 0
  • +
  • -

#10 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 10:07 AM

So does that mean I just leave it as myList.add()? Then I would need to make an add method that doesn't have any arguments? How would that work?
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12297
  • View blog
  • Posts: 45,399
  • Joined: 27-December 08

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 10:12 AM

Quote

So does that mean I just leave it as myList.add()?

Generally you want to add() something not already in the List, right?

If you are dealing with the standard java.util.LinkedList class, do you actually add a Node yourself? Or do you just pass the data and let the LinkedList do its job? I'd model your class after the standard class (and my tutorial).
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12297
  • View blog
  • Posts: 45,399
  • Joined: 27-December 08

Re: Linked Lists. Not sure where to go from here.

Posted 29 October 2014 - 10:22 AM

I'll also note that you are trying to do a lot of things at once. It's hard to debug this way. Get your StudentNode class up and working. Test it. Then go onto your StudentList class and get that working. Make sure to test it. After you have all that done, then worry about parsing the File.
Was This Post Helpful? 0
  • +
  • -

#13 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 03 November 2014 - 02:24 AM

Ok so I've been working on it and I think I've made some progress but I'm still having some major issues.

So here is my current StudentList class

import java.io.FileNotFoundException;
import java.util.Scanner;

public class StudentList<E> { 

    private static StudentNode head = null;
    private StudentNode<E> tail = null;
    private StudentNode<E> node;
    
    
    public StudentList(){}
    
    public void setHead(StudentNode<E> headNode) {
    	head = headNode;
    }
    	
    public static StudentNode getHead() {
    	return head;
    }
    
    public void add(StudentNode<E> newNode){
    	if (head == null){
    		
    		head = tail = new StudentNode<E>();
    		
    		head.elem = newNode;
    		head.nextNode = tail;
    		tail = head;
    	}
    	else{
    		tail.nextNode = new StudentNode<E>();
    		tail = tail.nextNode;
    		tail.elem = (E) newNode;
    	}
    }
    
    public void loadFromFile(String filename) throws FileNotFoundException { 
    	
    	Scanner input = new Scanner(System.in);
    	
		java.io.File file = new java.io.File("test1.txt");
		input = new Scanner(file);
	
		StudentList<E> myList = new StudentList<E>();
	
    	while(input.hasNextLine()){
    		node = new StudentNode<E>(input.nextInt(), input.nextDouble());
    		myList.add(node);
    	}
    	
	} 
}



And here is my current StudentNode class.

import java.util.Comparator;



public class StudentNode<E> {
    	
		E elem;
		StudentNode<E> nextNode;
		
    	private int studentNum;
    	private double grade;
        private StudentNode<E> next;
        
        public StudentNode(){}
        
        public StudentNode(int newStudentNum, double newGrade) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        	//next = null;
        }
        
        public StudentNode(int newStudentNum, double newGrade, StudentNode<E> nextNode) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        	next = nextNode;
        }
        
        public void setData(int newStudentNum, double newGrade) {
        	studentNum = newStudentNum;
        	grade = newGrade;
        } 
        
        public int getData(){
        	return studentNum;
        }
        
        public int getStudentNum() {
        	return studentNum;
        } 
        
        public double getGrade(){
        	return grade;
        }
        
        public void setNext(StudentNode<E> nextNode) {
        	next = nextNode;
        }
        
        public StudentNode<E> getNext() {
        	return next;
        }
        
        @Override
        public String toString() {
            String result = studentNum + " " + grade;
            if (next != null) {
                result += next.toString();
            }
            return result;
        }
       
    }

class nodeCompare implements Comparator<StudentNode>{
	 
    @Override
    public int compare(StudentNode e1, StudentNode e2) {
        if(e1.getData() < e2.getData()){
            return 1;
        } else {
            return -1;
        }
    }
}



And then the class I'm using to test it.

import java.io.FileNotFoundException;
import java.util.*;

public class Assignment3 {

	public static void main (String []args){
	
		StudentList<StudentNode> myList = new StudentList<StudentNode>();
		
		try {
			myList.loadFromFile("test1.txt");
		} 
		catch (FileNotFoundException e){
			System.out.println("File not found.");
		}
		
		//Collections.sort(myList, new nodeCompare());
		
		// for(StudentNode e:myList){
	        //       System.out.println(e);
	        // }
		
		
		for (StudentNode student = StudentList.getHead(); student != null; student=student.getNext()) {
			System.out.println(myList.toString());
		}
		
	}
}




As you can see I tried using collections to sort it but I get the error, "The method sort(List<T>, Comparator<? super T>) in the type Collections is not applicable for the arguments (StudentList<StudentNode>, nodeCompare)" and I'm not sure why.

On top of that I not getting the proper output I want.

I should be getting this (after it's sorted).


66666 99.5
33333 82.4
55555 77.3
44444 73.1
77777 68.7
99999 66.8
11111 63.5
22222 59.9
88888 53.2


But instead I'm just getting this.

[email protected]

Which tells me (I think) that it's not actually getting each line from the file, only the first one. Either that or my printing loop doesn't work. Also, it isn't printing it properly, since I'm pretty sure that that is the address being printed, which I think means my toString() method is faulty which I also don't know why.

Can anyone give me a hand?

Attached File(s)

  • Attached File  test1.txt (106bytes)
    Number of downloads: 35

Was This Post Helpful? 0
  • +
  • -

#14 aks29921  Icon User is offline

  • D.I.C Regular

Reputation: 116
  • View blog
  • Posts: 345
  • Joined: 24-August 09

Re: Linked Lists. Not sure where to go from here.

Posted 03 November 2014 - 08:20 AM

As macosxnerd101 said, you are doing many things at once.
Go one step at a time.
First you should get your node and comparator working.
What I did was to get rid of your StudentList class, for the time being, and use the LinkedList provided in Java.
import java.io.FileNotFoundException;
import java.util.*;

public class Assignment3 {

	public static void main (String []args){
	
		LinkedList<StudentNode> myList = new LinkedList<StudentNode>();
		
		/*try {
			myList.loadFromFile("test1.txt");
		} 
		catch (FileNotFoundException e){
			System.out.println("File not found.");
		}*/
		
		StudentNode node1 = new StudentNode(44444, 73.1);
		StudentNode node2 = new StudentNode(11111, 63.5);
		myList.add(node2);
		myList.add(node1);
		
		Collections.sort(myList, new nodeCompare());
		
		// for(StudentNode e:myList){
	        //       System.out.println(e);
	        // }
		
		
		for (StudentNode student = myList.getFirst(); student != null; student=student.getNext()) {
			System.out.println(myList.toString());
		}
		
	}
}


The output of this is that the nodes are sorted in descending order.

Next steps for you:
1. Clean up your StudentNode class a bit. I am not sure what you mean by StudentNode<E>. I would prefer to use StudentNode. Make sure you use Generics to give a clear meaning to the compiler.
2. Put your StudentList<StudentNode> class instead of the LinkedList<StudentNode> used by me. Get its add method working. You can consider extending the java.util.LinkedList and only write the extra methods needed by you.
3. Put in the code for parsing text file in StudentList<StudentNode>.

This post has been edited by macosxnerd101: 03 November 2014 - 09:26 AM
Reason for edit:: Please stop quoting large posts

Was This Post Helpful? 0
  • +
  • -

#15 DylanLyon  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 39
  • Joined: 24-September 14

Re: Linked Lists. Not sure where to go from here.

Posted 03 November 2014 - 09:09 AM

Unfourtunetly the Assignment requires to write everything from scratch so I can't use Java's LinkedList which is why I'm having so much difficulty. The Professor never covered how to make a valid LinkedList class, only a Node class si I'm flying blind here.

Anyways, after cleaning up StudentNode like you said and after some changes I mad earlier today this is my current StudentList class.

import java.io.FileNotFoundException;
import java.util.*;

class StudentList<E>{ 

    private static StudentNode head = null;
    private StudentNode tail = null;
    private StudentNode node;
    
    public StudentList(){}
    
    public void setHead(StudentNode headNode) {
    	head = headNode;
    }
    	
    public static StudentNode getHead() {
    	return head;
    }
    
    public void add(StudentNode newNode){
    	if (head == null){
    		
    		head = tail = new StudentNode();
    		
    		head = newNode;
    		head.nextNode = tail;
    		tail = head;
    	}
    	else{
    		tail.nextNode = new StudentNode();
    		tail = tail.nextNode;
    		tail = newNode;
    	}
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        StudentNode node = getHead();
        while(node != null) {
            sb.append(node.toString());
            if (node.getNext() != null) {
                //sb.append(", "); //Or even 'getSeparator()' if I wanted to configure how toString represents things
                node = node.getNext();
            }
        }
        return sb.toString();
    }
    
    
    public void loadFromFile(String filename) throws FileNotFoundException { 
    	
    	Scanner input = new Scanner(System.in);
    	
		java.io.File file = new java.io.File("test1.txt");
		input = new Scanner(file);
	
		StudentList<E> myList = new StudentList<E>();
	
    	while(input.hasNextLine()){
    		node = new StudentNode(input.nextInt(), input.nextDouble());
    		myList.add(node);
    	}
    	
	} 
}





Now the problem I'm running into now is that I'm not 100% sure if my add method or my toString method is working. Can you take a look?
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3