So I have these nodes I'm trying to sort as such, but it's not working.
This is psudo code:

Node first = new Node(23); //previously construted node

put method(newNode) {
  Node traverseInOrder = first;
  while (newNode > traverseInOrder) {
    If (traverseInOrder.successor != null) {
      traverseInOrder = traverseInOrder.successor;
    }
    else 
  }
  newNode.predecessor = traverseInOrder;
  newNode.successor = traverseInOrder.successor;
  traverseInOrder.successor.predecessor = newNode
  traverseInOrder.successor = newNode;
}

That's my basic algorithm, but it's not working. Can anyone give me a description of an algorithm that will work?

Thanks!

I think if you remove the line

traverseInOrder.successor.predecessor = newNode

your algorithm will be correct. Remember, node.successor.predecessor should always equal node unless node is the last node in the list. Same with node.predecessor.successor, unless node is the first in the list.

My code's still not working. I have inputs of:
t.put(23);
t.put(17);
t.put(3);
t.put(28);
t.put(8);
t.put(12);

Output should be 3, 8, 12, 17, 23, 28

But when I iterate it, the output is 3, 8, 17, 23, 23, 23, 23...

23 becomes an infinite loop. Not sure what's wrong with my code ><

Node traverseInOrder = first; // loops through the linked list
   
      // 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've been stuck on this part of my program for the past 2 days. I thought I knew how to implement a linked list, but apparently not...

Thanks for the help!

This article has been dead for over six months. Start a new discussion instead.