Java: How to iterate through an array of type linked lists and append those to an array

Question

For homework in an algorithms class we had to write a program that implemented a Radix sort algorithm. I ended up implementing it in a round about way, and it functions correctly. However there is a part of my code that is an atrocious looking if else block in a for loop. I have to retrieve the items out of an array of linked lists in the correct order and add the elements back into an Integer array. One of my classmates and I spent quite a while trying to figure out how to put this block into for loops but could just not come up with a to do that. So that's my questions, how would I put the objects of the linked lists in an array into a different array. The code I came up for the sort method is below:

private static Integer[] sort(Integer[] input, int place){
    //create an array of linked lists
    LinkedList<Integer>[] bucketsOut = new LinkedList[10];

    //initialize the linked lists
    for(int i=0; i < 10; i++){
        bucketsOut[i] = new LinkedList<Integer>();
    }

    int bucketPlacement = 0;
    //place every input into the correct bucket
    for(int i = 0; i < input.length; i++){
        bucketPlacement = getDigit(input[i].intValue(), place);
        bucketsOut[bucketPlacement].add(input[i]);
    }

    //Place the elements out of the linked lists into the correct place in input[]
    for(int i = 0; i < input.length; i++){ //for each input number
        if(bucketsOut[0].peekFirst() != null){  
            input[i] = bucketsOut[0].pollFirst().intValue();
        }else if(bucketsOut[1].peekFirst() != null){    
            input[i] = bucketsOut[1].pollFirst().intValue();
        }else if(bucketsOut[2].peekFirst() != null){    
            input[i] = bucketsOut[2].pollFirst().intValue();
        }else if(bucketsOut[3].peekFirst() != null){    
            input[i] = bucketsOut[3].pollFirst().intValue();
        }else if(bucketsOut[4].peekFirst() != null){    
            input[i] = bucketsOut[4].pollFirst().intValue();
        }else if(bucketsOut[5].peekFirst() != null){    
            input[i] = bucketsOut[5].pollFirst().intValue();
        }else if(bucketsOut[6].peekFirst() != null){    
            input[i] = bucketsOut[6].pollFirst().intValue();
        }else if(bucketsOut[7].peekFirst() != null){    
            input[i] = bucketsOut[7].pollFirst().intValue();
        }else if(bucketsOut[8].peekFirst() != null){    
            input[i] = bucketsOut[8].pollFirst().intValue();
        }else if(bucketsOut[9].peekFirst() != null){    
            input[i] = bucketsOut[9].pollFirst().intValue();
        }
    }
    //return sorted list for digit
    return input;
}

You pull the first element from all arrays, and then go back to the second element in all arrays. Is that intentional? — markspace
– markspace, Commented Nov 24, 2015 at 21:24
(@markspace : don't think so - look at all those elses.) If your environment had a CompositeCollection like Apache Commons, you could instantiate one for toArray() (to be followed by a System.arraycopy(), if need be). — greybeard
– greybeard, Commented Nov 24, 2015 at 22:21
My code works for numbers up to max_int positive numbers. I didn't originally upload the whole thing as to not take up space, so here is my completed code in pastebin: link — T. MacInnis
– T. MacInnis, Commented Nov 24, 2015 at 23:14

RealSkeptic · Accepted Answer · 2015-11-24 21:28:22Z

1

When you have a series of operations that are exactly the same except for the change in an index, it means that you can do it in a for loop:

First attempt

for (int j = 0; j < bucketsOut.length; j++ ) {
    // The part that is repeated again and again
    if (bucketsOut[j].peekFirst() != null) {
        input[i] = bucketsOut[j].pollFirst().intValue();
    }
}

But wait! This will continue through all the buckets. Your original if structure actually meant that once you hit the right if, you would not be looking at any of the other elses.

This can be done by breaking out of the loop when the condition becomes true:

Improved version

for (int j = 0; j < bucketsOut.length; j++ ) {
    if (bucketsOut[j].peekFirst() != null) {
        input[i] = bucketsOut[j].pollFirst().intValue();
        break; // Now the j loop will stop when we hit the first non-null.
    }
}

Or you could use enhanced for - the logic is the same:

for ( LinkedList<Integer> bucket : bucketsOut ) {
    if (bucket.peekFirst() != null) {
        input[i] = bucket.pollFirst().intValue();
        break; 
    }
}

answered Nov 24, 2015 at 21:28

RealSkeptic

34.8k7 gold badges56 silver badges83 bronze badges

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

2 Comments

greybeard Over a year ago

(This would seem less mistakable if it mentioned that these loops are still to be in an outer loop iterating input by incrementing i.)

RealSkeptic Over a year ago

@greybeard I thought that would be obvious since the code still refers to i in the input index.

markspace · Accepted Answer · 2015-11-25 01:49:07Z

Thanks to greybeard for pointing out that the elses above actually causes the first bucket to be emptied completely first.

With that in mind, its not too hard to turn this into a loop. Remember, your basic idea is that you first want to copy all of the items in the first bucket. This is easily done with a while loop.

     while( bucketsOut[bucketIndex].peekFirst() != null &&
             inputIndex < input.length ) 
     {
        input[inputIndex++] = bucketsOut[bucketIndex].pollFirst();
     }

So here, for each bucket, we copy until the peek value is null. Notice I use post-increment inside the array index. This is really common when you need to copy some number of elements into an array. It allows me to copy to increasing elements while not having to fix in advance the exact number with a for loop.

With that, the rest is pretty easy. I just added a for loop around the while loop to increment to the next bucket. The while loop checks inputIndex so we don't accidentally try to copy beyond the end of input.

  for( int inputIndex = 0, bucketIndex = 0; bucketIndex < bucketsOut.length;
          bucketIndex++ ) 
  {
     while( bucketsOut[bucketIndex].peekFirst() != null &&
             inputIndex < input.length ) 
     {
        input[inputIndex++] = bucketsOut[bucketIndex].pollFirst();
     }
  }

If you want to be fancy (or if you have many more elements) you might add a manual test at the after the while loop so you don't have to test for more buckets if input is full.

     if( inputIndex >= input.length ) break;

Collectives™ on Stack Overflow

Java: How to iterate through an array of type linked lists and append those to an array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related