Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Help with singly linked list.

  1. #1
    Junior Member
    Join Date
    Sep 2014
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Post 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)]


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,404
    Thanks
    53
    Thanked 2,399 Times in 2,352 Posts

    Default Re: Help with singly linked list.

    How are you debugging the code? I use println() statements to print out the values of variables as they are used. The print out should help you see what the code is doing so you can correct the bugs.

    What is wrong with the printout from the program? Could you add some comments describing what is wrong?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2014
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Help with singly linked list.

    In the output section, it is printing "(Krusty, 324)" multiple times. More accurately, it is printing the second game entry multiple times.

    --- Update ---

    I was getting feedback from another source and they told me that the Scoreboard class for loop was entirely wrong. That may be an issue as well.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,404
    Thanks
    53
    Thanked 2,399 Times in 2,352 Posts

    Default Re: Help with singly linked list.

    getting feedback from another source
    Ok, I'll leave you with that other source. No sense me wasting time when the question is being answered elsewhere.

    --- Update ---

    Also posted at: Singly linked list not printing correctly. (Beginning Java forum at JavaRanch)

    The problems with cross-posting
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. [SOLVED] Singly Linked List - Sort Method
    By Sfrius in forum Collections and Generics
    Replies: 6
    Last Post: July 26th, 2014, 05:21 PM
  2. Creating methods in a singly linked list?
    By EDale in forum Collections and Generics
    Replies: 13
    Last Post: September 29th, 2013, 06:13 PM
  3. Singly Linked List
    By koala711 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 02:15 PM
  4. Singly-Linked list structure
    By blaster in forum Algorithms & Recursion
    Replies: 24
    Last Post: March 11th, 2012, 03:42 PM
  5. Singly Circular Linked List Error
    By clydefrog in forum Collections and Generics
    Replies: 7
    Last Post: March 5th, 2012, 07:17 PM

Tags for this Thread