Adding into a sorted `linkedList`

Question

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

laune · Accepted Answer · 2015-10-11 04:44:47Z

1

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.

edited Oct 11, 2015 at 4:44

answered Oct 11, 2015 at 4:39

laune

31.3k3 gold badges32 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

laune Over a year ago

@KemalP. You can delete a comment if it isn't correct - it seems that it works now?

Kemal P. Over a year ago

Yep! Thanks @laune... (the comment is deleted)

Kemal P. Over a year ago

Btw, @laune, to add the objects so it could be checked in cols first and the n rows, so it could be entered into the list sorted with cols first, do I have to only switch the row with col in if - statement?

laune Over a year ago

Certainly: you need to check the more important criterion first, and only when this is a "draw", you check the next.

Kemal P. Over a year ago

Could you please also take a look here? @laune I have a bigger problem: adding objects diagonally. stackoverflow.com/questions/33062219/…

Collectives™ on Stack Overflow

Adding into a sorted `linkedList`

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related