title: adding and removing from a singly linked list
body: <p>I thought I had understanding of this in my previous question about linked lists, but I was terribly mistaken, I'm just as lost as I was when I initially posted.</p>
  
  <p>I realize that I'm technically asking two questions, but hopefully getting at least one should make the other easy (assuming they are just reverse of each other).</p>
  
  <p>I have 3 classes already given to me, they are:</p>
  
  <p>SLinkedList.java</p>
  
  <pre><code>package chapter3.linkedList;
  
      public class SLinkedList&lt;V&gt; {
          // instance variables.  Add the tail reference.
          protected Node&lt;V&gt; head, tail;
          protected long size;
  
          // methods, empty list constructor first
          public SLinkedList () {
              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&lt;V&gt; 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&lt;V&gt;currentNode, Node&lt;V&gt;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&lt;V&gt; 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&lt;V&gt; removeFirst () {
              if (head == null)
                  System.err.println("Error:  Attempt to remove from an empty list");
  
              // save the one to return
              Node&lt;V&gt; 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&lt;V&gt; removeLast () {
              // // declare local variables/objects
              Node&lt;V&gt; nodeBefore;
              Node&lt;V&gt; 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 &lt; 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&lt;V&gt; nodeToRemove) {
              // declare local variables/references
              Node&lt;V&gt; 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 &gt; 0) {
                  nodeBefore = getFirst ();
                  currentNode = getFirst ().getNext ();
                  for (int count = 0; count &lt; 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 &gt; 0
  
          }  // end method remove
  
          // the gets to return the head and/or tail nodes and size of the list
          public Node&lt;V&gt; getFirst () { return head; }
          public Node&lt;V&gt; getLast () { return tail; }  
          public long getSize () { return size; }
  
      }  // end class SLinkedList
  </code></pre>
  
  <p>There's also Node.java</p>
  
  <pre><code>package chapter3.linkedList;
  
  public class Node&lt;V&gt; 
  {
      // instance variables
      private V element;
      private Node&lt;V&gt; next;
  
      // methods, constructor first
      public Node () 
      {
          this (null, null);      // call the constructor with two args
      }  // end no argument constructor
      public Node (V element, Node&lt;V&gt; next) 
      {
          this.element = element;
          this.next = next;
      }  // end constructor with arguments
  
      // set/get methods
      public V getElement () 
      { 
          return element; 
      }
      public Node&lt;V&gt; getNext () 
      { 
          return next; 
      }
      public void setElement (V element) 
      { 
          this.element = element; 
      }
      public void setNext (Node&lt;V&gt; next) 
      { 
          this.next = next; 
      }
  
  }  // end class Node
  </code></pre>
  
  <p>and finally GameEntry.java</p>
  
  <pre><code>package Project_1;
  
  public class GameEntry 
  {
      protected String name;  // name of the person earning this score
      protected int score;    // the score value
      /** Constructor to create a game entry */
      public GameEntry(String name, int score) 
      {
        this.name = name;
        this.score = score;
      }
      /** Retrieves the name field */
      public String getName() 
      { 
          return name; 
      }
      /** Retrieves the score field */
      public int getScore() 
      { 
          return score; 
      }
      /** Returns a string representation of this entry */
      public String toString() 
      { 
        return name + ", " + score + "\n"; 
      }
  
  }
  </code></pre>
  
  <p><strong>EDIT POINT</strong>
  I created a driver called Scores.java, in it so far all I have is **I have added what I THINK i need for the classes, I'm probably wrong though:</p>
  
  <pre><code>package Project_1;
  
  import chapter3.linkedList.*;
  
  import java.util.*;
  
  
  /** Class for storing high scores in an array in non-decreasing order. */
  public class Scores 
  {
  
      //add function
      public SLinkedList&lt;GameEntry&gt; add(GameEntry rank, SLinkedList&lt;GameEntry&gt; scores)
      {
          Node&lt;GameEntry&gt; currentNode = scores.getFirst();
          Node&lt;GameEntry&gt; nextNode = null;
          Node&lt;GameEntry&gt; previousNode = null;
          Node&lt;GameEntry&gt; newNode = new Node&lt;GameEntry&gt;();
          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;
                  }               
              previousNode = currentNode;
              currentNode = currentNode.getNext();
              }
          }
          return scores;
      }
  
      //remove function
      public void remove(int i)
      {
  
      }
  
      //print function
      /*gameenter printing; 
  printing=node.Getelement;           //pseudo code for making it work right
  print(printing.getscore) 
  print(print.getname) 
  */
      public void print(SLinkedList&lt;GameEntry&gt; scores)
      {
          Node&lt;GameEntry&gt; currentNode = scores.getFirst();        
          GameEntry currentEntry = currentNode.getElement();      
          System.out.printf("[");
          for(int i = 0; i &lt; scores.getSize(); i++)
          {
                  System.out.printf(", %s", currentEntry.toString());
                  currentNode = currentNode.getNext();
                  currentEntry = currentNode.getElement();
          }
          System.out.println("]");
      }
  }
  </code></pre>
  
  <p>I have my test driver called ScoresTest.java, that I have pretty much filled out:</p>
  
  <p>package Project_1;</p>
  
  <p>import chapter3.linkedList.SLinkedList;</p>
  
  <pre><code> public class ScoresTest {
      /**
       * @param args
       */
  
      public static void main(String[] args) 
      {
          SLinkedList&lt;GameEntry&gt; highScores = new SLinkedList&lt;GameEntry&gt;();  //Linked List for Game Entry
          GameEntry entry;
          Scores rank = new Scores();     
          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("Moe", 895);
          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);
      }
  }
  </code></pre>
  
  <p>That's entirely finished, pretty sure I have nothing left to add for it.</p>
  
  <p>I'm not looking for someone to answer it for me, but I have no clue where to start or how to make the add or remove function, in any way.  This is an intermediate course, the book does nothing for explaining linked lists (go ahead and look for yourself if you don't believe me, text is called Datastructures and Algorithms in Java, 5th edition).  It shows how to do such with an array quite easily...which works perfectly for a linked list, but apparently the teacher does not want us doing it this way, so sadly I am now utterly lost on how to do this.</p>
  
  <p>I've tried looking at other peoples answers on here, and google, and so far nothing has clicked or made any sense at all, I just can't grasp how it works, and the teacher's explanation and example was only to draw boxes on the board, I've never seen a sort, add, or remove function coded for a linked list...can't know what I've not been taught or can't locate.</p>
  
  <p>Any help is greatly appreciated, and thank you in advance!</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I looked at the import java.util.*; and the commands within it for linked lists, they seem painfully easy.  to remove I'd just use list.sublist(i, i).clear(); and the value I wish to remove is removed, super easy, it seems to be just trying to utilize the slinkedlist.java and node.java, I just can't seem to follow them in any way shape or form.  I believe the teacher did indeed write them, and I've tried asking for his assistance, stayed 2 hours after class trying to get any understanding from him, and as you can see it did not help much at all.  Thank you again for the assistance!</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I also apologize if this seems like it is vague, but I don't have a specific point where my confusion seems linked, I understand linked lists if we're talking about the java.util.linkedList;, but as far as using what I've been given in this circumstance, I can't follow the logic at all, leaving me quite lost and unsure of where to begin.</p>