What's wrong with my sorted linked list algorithm? (Java)

[iamsmooth]

So my algorithm compares a node that needs to be inserted with the current linked list set. it goes from first (which contains the lowest integer) and moves forward until it hits null or when the key trying to be inserted is no longer greater than the nodes being compared to.

My input of 23, 17, 3, 28, 8, 12 should yield output of 3, 8, 12, 17, 23, 28

but instead it goes:

3, 8, 17, 23, 23, 23, 23, 23... where 23 becomes an infinite loop.

      Node traverseInOrder = first; // loops through the linked list (first is preconstructed node)
   
      // iterator is the node trying to be inserted
      while (iterator.key.compareTo(traverseInOrder.key) > 0) {
          if (traverseInOrder.successor != null) {
             traverseInOrder = traverseInOrder.successor;
          }
          else {
              break;
          }
      }
      // if node should be inserted in the front
      if (traverseInOrder.predecessor == null) {
          iterator.successor = traverseInOrder;
          traverseInOrder.predecessor = iterator;
          iterator.predecessor = null;
          first = iterator;
      }
      // when the node should be inserted at the end
      // there are 2 cases, as node could be at the end, or the one before the end
      else if (traverseInOrder.successor == null) {
          if (iterator.key.compareTo(traverseInOrder.key) < 0) {
              traverseInOrder.predecessor.successor = iterator;
              iterator.predecessor = traverseInOrder.predecessor;
              iterator.successor = traverseInOrder;
              traverseInOrder.predecessor = iterator;
          }
          else {
              iterator.predecessor = traverseInOrder;
              traverseInOrder.successor = iterator;
          }
      }
      // when the node should be inserted in the middle
      else if (traverseInOrder.successor != null && traverseInOrder.predecessor != null) {
          iterator.predecessor = traverseInOrder.predecessor;
          traverseInOrder.predecessor.successor = iterator;
          iterator.successor = traverseInOrder;
          traverseInOrder.predecessor = iterator;
      }

I can't figure out what I did wrong. I've tried rewriting my algorithm from scratch like 6 times but it's always some different variant of an infinite loop. Can anyone help make some suggestions or even give me a better algorithm? They have to be placed into the list sorted so I can't use any sorting algorithms afterwards.

Thanks!

 

[hamster143]

What does 'successor' point to in a node you insert at the end of the list?

 

[iamsmooth]

The last node on the list should have successor null, and vise versa with the first node on the list having predecessor of null. I think my code already does that though, doesn't it? I don't see where it's wrong.

 

[hamster143]

I don't see any place in your code where you actually set it to null.

 

[iamsmooth]

// there are 2 cases, as node could be at the end, or the one before the end
      else if (traverseInOrder.successor == null) {
          // this condition is here because if traverse.successor is null, traversal is not incremented
          if (iterator.key.compareTo(traverseInOrder.key) < 0) {
              traverseInOrder.predecessor.successor = iterator;
              iterator.predecessor = traverseInOrder.predecessor;
              iterator.successor = traverseInOrder;
              traverseInOrder.predecessor = iterator;
          } 
          // this covers the case when successor is null, but the key to insert is greater
          else { 
              iterator.predecessor = traverseInOrder;
              traverseInOrder.successor = iterator; 
              //iterator.successor = null // **even if I put this here, nothing happens**
          }
      }

The nodes are constructed with all pointer nodes initialized as null, so I don't think that's what was wrong. I did change them to point to null in the code and it made no difference. Still an infinite loop. Or am I misunderstanding what you're saying?

 

[hamster143]

You need to post more code, including initialization and declarations. I suspect that there's something going wrong during the very first insertion, where the node with 23 ends up pointing at itself (lines 14-17 of your fragment).

     Node traverseInOrder = first; // loops through the linked list (first is preconstructed node)
...
     iterator.successor = traverseInOrder;
...
     first = iterator;

Unfortunately, I know C++ much better than I know Java. In C++, it would've been much clearer (to me, anyways) whether objects being assigned are pointers, references, or values.

 

[iamsmooth]

You were right. I was using a reference to the node's parent instead of the node itself which caused these crazy bugs. After removing it, the program works fine. Thanks!