- #1
iamsmooth
- 103
- 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.
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!
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!