CODEWITHSUNDEEP
javalinked-listiterator
Kemal P.
Kemal P.

Reputation: 143

Adding into a sorted `linkedList`

Folks, my method needs to add a new element into already a sorted list, i.e. in a proper position. The point is the method checks the lowest row index and then compares its cols. For example,

    board.set(2,2, 11);
    board.set(-1,0,22);
    board.set(-1,2,33);
    board.set(1,0,44);
    board.set(3,0,55);
    board.set(3,1,66);
    board.set(3,3,77);
    board.set(3,2,88);
    board.set(-1,1,99);

The result should be:

[(-1,0,22), (-1,1,99), (-1,2,33), (1,0,44),  (2,2,11), (3,0,55), (3,1,66), (3,2,88), (3,3,77)]

But my program prints this:

[(-1,0,22), (-1,1,99), (3,2,88), (3,3,77), (3,1,66), (3,0,55), (1,0,44), (-1,2,33), (2,2,11)]

i.e. it does not put the objects into the proper positions.

I have a LinkedList<RowColElem<T>>rowColSeq where the objects are added and put into a proper position "on the go". What is my code missing?

NOTE: Im not allowed to use comparators, comparable interface!

LinkedList<RowColElem<T>> rowColSeq; // Is not empty, already contains objects!
 private void sortedRowColSeq(int row, int col, T x){
      RowColElem<T> object = new RowColElem<T>(row, col, x);
      ListIterator<RowColElem<T>> iter = rowColSeq.listIterator();
      RowColElem<T> inListObject;
      boolean added = false;
      while(iter.hasNext()){
          inListObject = iter.next();
          if(object.getRow() < inListObject.getRow()){
              iter.previous();
              iter.add(object);
              undoStack.push(object);
              added = true;
              break;
          }
          else if(object.getRow() == inListObject.getRow()){
              if(object.getCol() < inListObject.getCol()){
                  iter.previous();
                  iter.add(object);
                  undoStack.push(object);
                  added = true;

              }
          }

          else{
              iter.add(object);
              undoStack.push(object);
              added = true;
              break;
            }
          }
     }

Upvotes: 0

Views: 71

Answers (1)

laune
laune

Reputation: 31290

You may not add if the new element is greater than some element. You must enter before one that is greater, or at the end.

 boolean added = false;
 while(iter.hasNext()){
      inListObject = iter.next();
      if(object.getRow() < inListObject.getRow() ||
         object.getRow() == inListObject.getRow()) &&
         object.getCol() < inListObject.getCol() ){
          if( iter.hasPrevious() ){
              iter.previous();
              iter.add(object);
          } else {
              rowColSeq.addFirst( object );
          }
          undoStack.push(object);
          added = true;
          break;
      }
 }

 if( ! added ){
      rowColSeq.addLast(object);
      undoStack.push(object);
      added = true;
 }

The approach using iter.previous() is doomed to fail under certain circumstances so I added a test and alternative code.

Upvotes: 1

Related Questions