Why won't my linked list add nodes? (Java)

Question

I'm trying to add a new Node to the end of my linked list but it doesn't seem to be doing anything. It adds the first element because it's a special case but then ignores all of the other assignments when I step through the debugging.

Here's the test I'm running:

@Test
public void testInsertElement()
{
PriorityList<String> list = new LinkedPriorityList<String>();
list.insertElementAt(0, "first");
list.insertElementAt(1, "second");
list.insertElementAt(2, "third");
assertEquals("first" , list.getElementAt(0));
assertEquals("second", list.getElementAt(1));
assertEquals("third" , list.getElementAt(2));
}

It fails on the second assertion because nothing is added after the first.

Here's the constructor for the Node Objects:

public class LinkedPriorityList<E> implements PriorityList<E> {

  private class Node
  {

    private E data;
    private Node next;

    public Node(E element)
    {
      data = element;
      next = null;
    }
  }

And finally the code that is failing on me:

public void insertElementAt(int index, E element) throws IllegalArgumentException
  {
      if(index>size() || index<0) //can only be between 0 and size()
            throw new IllegalArgumentException();

      if(size()==0)
          first = new Node(element); //adding the first element. This works
      else
      {
          if(index == size()) //if an element is being added to the end
          {
              Node ref = first;                //assigning ref to the first element of the list
              for(;ref!=null; ref = ref.next); //stepping through the list until ref is null
              ref = new Node(element);         //assigning the null reference a new Node. Doesn't assign
          }
          else //if an element is being inserted in the list. untested...
          {
              Node ref = first;
              Node temp = new Node(element);
              for(int i=1; i<index; i++)
                  ref = ref.next;
              temp = ref.next;
              ref = temp;
          }
      }
      size++; //keeping track of how many elements in list
  }

I think this works but if you want the get method too, here it is:

public E getElementAt(int index) throws IllegalArgumentException
  {
    if(index>=size() || index<0)
        throw new IllegalArgumentException();

    Node ref = first;
    for(int i=0; i<index; i++)
        ref = ref.next;
    return ref.data;
  }

If the size isn't 0, then your insertElementAt method does nothing useful. It ends up assigning a value to a local variable, but that's all. It never adds a new element into the list. Which statement did you expect to do that? — Jon Skeet
– Jon Skeet, Commented Oct 11, 2013 at 21:57
Sorry I didn't include it. First is actually a global instance variable — Joey Flynn
– Joey Flynn, Commented Oct 11, 2013 at 22:03

JB Nizet · Accepted Answer · 2013-10-11 22:01:29Z

3

When index == size, you want to create a new node, find the last node in the list, and assign the new node to its next pointer.

The last node is the one whose next pointer is null.

This should be enough to let you implement the algorithm by yourself.

answered Oct 11, 2013 at 22:01

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Has QUIT--Anony-Mousse · Accepted Answer · 2013-10-11 22:02:51Z

1

This is probably what you meant to do:

for(; ref.next != null; ref = ref.next) {
  /* intentionally empty */
}
ref.next = new Node(element);

Note that I'm both testing and assigning ref.next, not ref itself.

answered Oct 11, 2013 at 22:02

Has QUIT--Anony-Mousse

77.8k14 gold badges145 silver badges198 bronze badges

3 Comments

JB Nizet Over a year ago

Am I the only one to find that a while loop would be much more readable here, and wouldn't need any comment?

Ingo Bürk Over a year ago

@JBNizet That and extracting it into a method, i.e. getLastNode().

Has QUIT--Anony-Mousse Over a year ago

I agree, but I tried to keep the changes to his code minimal, so he finds easily where this part is supposed to go to.

Ravi K Thapliyal · Accepted Answer · 2013-10-11 22:06:46Z

1

You need a temp node when adding at the end too (to keep track of the last element)

if (index == size())
{
    Node ref = first, temp = first;
    for (; ref != null; temp = ref, ref = ref.next);
    temp.next = new Node(element);    
}

By just assigning the new Node to ref; it doesn't link it to the current last node's next.

edited Oct 11, 2013 at 22:06

answered Oct 11, 2013 at 22:01

Ravi K Thapliyal

51.8k9 gold badges80 silver badges90 bronze badges

Collectives™ on Stack Overflow

Why won't my linked list add nodes? (Java)

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related