Java

Algorithm for creating a linked list that is sorted as nodes are inserted

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Jul 2009

Posts: 35

Reputation: iamsmooth is an unknown quantity at this point

Solved Threads: 0

iamsmooth

Offline

Light Poster

Algorithm for creating a linked list that is sorted as nodes are inserted

Nov 7th, 2009

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

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
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;
}
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!

•

Join Date: Aug 2007

Posts: 801

Reputation: darkagn has a spectacular aura about

Solved Threads: 110

darkagn

Offline

Practically a Posting Shark

Nov 7th, 2009

I think if you remove the line

Help with Code Tags

Java Syntax (Toggle Plain Text)

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.

There are no stupid questions, only those too stupid to ask for help.
echo is a web developer's best friend.

•

Join Date: Jul 2009

Posts: 35

Reputation: iamsmooth is an unknown quantity at this point

Solved Threads: 0

iamsmooth

Offline

Light Poster

Nov 7th, 2009

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 ><

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
      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;
      }
      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!