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

AI Thread Summary
The linked list algorithm is experiencing an infinite loop when trying to insert nodes in sorted order, particularly with the input sequence of 23, 17, 3, 28, 8, 12. The issue arises from incorrect handling of node pointers, where the node with the key 23 ends up pointing to itself. The algorithm fails to properly set the successor and predecessor pointers during insertion, leading to a circular reference. After addressing the pointer assignment and ensuring that the correct nodes are referenced, the algorithm functions as intended. Proper initialization and management of node pointers are crucial for avoiding such issues in linked list implementations.
iamsmooth
Messages
103
Reaction score
0
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.


Code:
      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!
 
Technology news on Phys.org
What does 'successor' point to in a node you insert at the end of the list?
 
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.
 
I don't see any place in your code where you actually set it to null.
 
Code:
// 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?
 
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).

Code:
     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.
 
Last edited:
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!
 

Similar threads

Replies
2
Views
1K
Replies
2
Views
2K
Replies
6
Views
13K
Replies
1
Views
3K
Replies
2
Views
4K
Replies
5
Views
3K
Replies
11
Views
12K
Replies
2
Views
3K
Back
Top