LinkBack URL
About LinkBacks
Help with singly linked list.
Hello guys. I need help with a project I am working on. Its a program that creates a singly linked list that stores names and high scores and prints them. For some reason it is printing an entry extra times. Also my remove function is not working properly can someone help me out? Thank you in advance.
GameEntry class:
package project; public class GameEntry implements Comparable<GameEntry> { private String name; private int score; public GameEntry(String n, int s) { name = n; score = s; } @Override public int compareTo(GameEntry o){ int comparedScore = o.score; if (this.score>comparedScore){ return 1; } else if(this.score ==comparedScore){ return 0; } else{ return -1; } } /** Returns the name field. */ public String getName() { return name; } /** Returns the score field. */ public int getScore() { return score; } /** Returns a string representation of this entry. */ public String toString() { return "(" + name + ", " + score + ")"; } }
Linkedlist class:
package project; public class LinkedList<A> { public static class Node<A> { // instance variables private A element; private Node<A> next; // methods, constructor first public Node () { this (null, null); // call the constructor with two args } // end no argument constructor public Node (A element, Node<A> next) { this.element = element; this.next = next; } // end constructor with arguments // set/get methods public A getElement () { return element; } public Node<A> getNext () { return next; } public void setElement (A element) { this.element = element; } public void setNext (Node<A> next) { this.next = next; } } // End of nested node class // instance variables. Add the tail reference. protected Node<A> head, tail; protected long size; // methods, empty list constructor first public LinkedList () { head = null; tail = null; size = 0; } // end constructor of a SLinkedList // method to add nodes to the list. Storage space for the node // is already allocated in the calling method public void addFirst (Node<A> node) { // set the tail only if this is the very first node if (tail == null) tail = node; node.setNext (head); // make next of the new node refer to the head head = node; // give head a new value // change our size size++; } // end method addFirst // addAfter - add new node after current node, checking to see if we are at the tail public void addAfter (Node<A>currentNode, Node<A>newNode) { if (currentNode == tail) tail = newNode; newNode.setNext (currentNode.getNext ()); currentNode.setNext (newNode); // change our size size++; } // end method addAfter // addLast - add new node after the tail node. Adapted from Code Fragment 3.15, p. 118. // Mike Qualls public void addLast (Node<A> node) { node.setNext (null); tail.setNext (node); tail = node; size++; } // end method addLast // methods to remove nodes from the list. (Unfortunately, with a single linked list // there is no way to remove last. Need a previous reference to do that. (See // Double Linked Lists and the code below.) public Node<A> removeFirst () { if (head == null) System.err.println("Error: Attempt to remove from an empty list"); // save the one to return Node<A> temp = head; // do reference manipulation head = head.getNext (); temp.setNext(null); size--; return temp; } // end method removeFirst // remove the node at the end of the list. tail refers to this node, but // since the list is single linked, there is no way to refer to the node // before the tail node. Need to traverse the list. public Node<A> removeLast () { // // declare local variables/objects Node<A> nodeBefore; Node<A> nodeToRemove; // make sure we have something to remove if (size == 0) System.err.println("Error: Attempt to remove fron an empty list"); // traverse through the list, getting a reference to the node before // the trailer. Since there is no previous reference. nodeBefore = getFirst (); // potential error ?? See an analysis and drawing that indicates the number of iterations // 9/21/10. size - 2 to account for the head and tail nodes. We want to refer to the one before the // tail. for (int count = 0; count < size - 2; count++) nodeBefore = nodeBefore.getNext (); // save the last node nodeToRemove = tail; // now, do the pointer manipulation nodeBefore.setNext (null); tail = nodeBefore; size--; return nodeToRemove; } // end method removeLast // method remove. Remove a known node from the list. No need to search or return a value. This method // makes use of a 'before' reference in order to allow list manipulation. public void remove (Node<A> nodeToRemove) { // declare local variables/references Node<A> nodeBefore, currentNode; // make sure we have something to remove if (size == 0) System.err.println("Error: Attempt to remove fron an empty list"); // starting at the beginning check for removal currentNode = getFirst (); if (currentNode == nodeToRemove) removeFirst (); currentNode = getLast (); if (currentNode == nodeToRemove) removeLast (); // we've already check two nodes, check the rest if (size - 2 > 0) { nodeBefore = getFirst (); currentNode = getFirst ().getNext (); for (int count = 0; count < size - 2; count++) { if (currentNode == nodeToRemove) { // remove current node nodeBefore.setNext (currentNode.getNext ()); size--; break; } // end if node found // change references nodeBefore = currentNode; currentNode = currentNode.getNext (); } // end loop to process elements } // end if size - 2 > 0 } // end method remove // the gets to return the head and/or tail nodes and size of the list public Node<A> getFirst () { return head; } public Node<A> getLast () { return tail; } public long getSize () { return size; } }
Scoreboard class:
package project; import project.LinkedList.Node; public class Scoreboard { public LinkedList<GameEntry> add(GameEntry rank, LinkedList<GameEntry> scores) { Node<GameEntry> currentNode = scores.getFirst(); Node<GameEntry> nextNode = null; Node<GameEntry> newNode = new Node<GameEntry>(); newNode.setElement(rank); if(scores.getSize() == 0) { scores.addFirst(newNode); } else { while(currentNode != null) { nextNode = currentNode.getNext(); if(nextNode == null) { scores.addLast(newNode); } else { scores.addAfter(currentNode, newNode); break; } currentNode = currentNode.getNext(); } } return scores; } public void print(LinkedList<GameEntry> scores) { Node<GameEntry> currentNode = scores.getFirst(); GameEntry currentEntry = currentNode.getElement(); System.out.printf("["); for(int i = 0; i < scores.getSize(); i++) { System.out.printf(", %s", currentEntry.toString()); currentNode = currentNode.getNext(); currentEntry = currentNode.getElement(); } System.out.println("]"); } }
ScoreboardTest class:
package project; public class ScoreboardTest { public static void main(String[] args) { LinkedList<GameEntry> highScores = new LinkedList<GameEntry>(); //Linked List for Game Entry GameEntry entry; Scoreboard rank = new Scoreboard(); entry = new GameEntry("Flanders", 681); highScores = rank.add(entry, highScores); entry = new GameEntry("Krusty", 324); highScores = rank.add(entry, highScores); entry = new GameEntry("Otto", 438); highScores = rank.add(entry, highScores); entry = new GameEntry("Bart", 875); highScores = rank.add(entry, highScores); entry = new GameEntry("Homer", 12); highScores = rank.add(entry, highScores); entry = new GameEntry("Lisa", 506); highScores = rank.add(entry, highScores); entry = new GameEntry("Maggie", 980); highScores = rank.add(entry, highScores); entry = new GameEntry("Apoo", 648); highScores = rank.add(entry, highScores); entry = new GameEntry("Smithers", 150); highScores = rank.add(entry, highScores); entry = new GameEntry("Burns", 152); highScores = rank.add(entry, highScores); System.out.println("The Original High Scores"); rank.print(highScores); entry = new GameEntry("Tyler", 000); highScores = rank.add(entry, highScores); System.out.println("Scores after adding Moe"); rank.print(highScores); //highScores = rank.remove(4); System.out.println("Scores after removing Apoo"); rank.print(highScores); } }
Output:
The Original High Scores
[, (Flanders, 681), (Burns, 152), (Smithers, 150), (Apoo, 648), (Maggie, 980), (Lisa, 506), (Homer, 12), (Bart, 875), (Otto, 438), (Krusty, 324), (Krusty, 324), (Krusty, 324)]
Scores after adding Moe
[, (Flanders, 681), (Tyler, 0), (Burns, 152), (Smithers, 150), (Apoo, 648), (Maggie, 980), (Lisa, 506), (Homer, 12), (Bart, 875), (Otto, 438), (Krusty, 324), (Krusty, 324), (Krusty, 324)]
Scores after removing Apoo
[, (Flanders, 681), (Tyler, 0), (Burns, 152), (Smithers, 150), (Apoo, 648), (Maggie, 980), (Lisa, 506), (Homer, 12), (Bart, 875), (Otto, 438), (Krusty, 324), (Krusty, 324), (Krusty, 324)]
Reply With Quote
Related threads:
