Double Brace Initialization in Java

Sometimes Double Brace Initialization is treated as a hidden feature of Java, But let's look closer to the syntax. In a normal way when we are declaring and initializing Collection we would use following code snippet:

 List normal = new ArrayList();
normal.add("string_1");
normal.add("string_2");
normal.add("string_3");

Now we can use double brace initialization and rewrite code:

 List list = new ArrayList() {{
      add("string_1");
      add("string_2");
      add("string_3");
   }};

What we got is not a new feature, we are just declaring anonymous class and second braces creates an initializer block, which will be invoked when class is created.

As we can see this approach is nice for initializations and we can use it in following case:

     method(new ArrayList() {{
       add("string_1");
       add("string_2");
       add("string_3");
     }});

But it is slightly inefficient, instead of creating new instance of class we are creating new class and if we have 100 such initializations we will receive 100 new classes. I don't suggest to use it under high performance requirements.

Linked List shuffling

Every programmer should know what a linked list is, here is brief a description from wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

In this post I want write how to shuffle linked list.

In a very simple way when you are shuffling array you can make it in two steps:

1. for every index you can generate some random index - time complexity is O(N)
2. swap corresponding elements. - time complexity is O(1)

This algorithm works in O(N) time, where N is size of array.

Let's try to implement this approach for our linked list. first step is the same, but second one isn't as easy as it seems. In linked list you can't access elements by index, therefore you must iterate whole list and examine all elements. This takes N operation and you would get O(N*N) complexity.

My aim is to show you another algorithm, which will work in O(N LogN) time.

In my algorithm I'm using Divide and Conquer approach.

1. divide list into halves
2. reshuffle both lists
3. merge reshuffled list.

This algorithm works in O(N*LogN), because list will be divided LogN times and complexity of merging is O(N). Here is my implementation of this algorithm:

 #include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
//list item
struct Item{
Item* next; // pointer to the next element in list
int value; // value of element
Item(){
  next = NULL;
}
};
int Min(int a, int b){
return a<b?a:b;
}
//construction list
Item* constructList(int N){
Item* root = new Item();
Item* t = root;
t->value = 0;
for(int i = 1; i < N; i++) {
  t->next = new Item();
  t = t->next;
  t->value = i;
  }
return root;
}
//root = first element of list
//len = length of list
void shuffle(Item* root, int len){
if(len==1) return; //if len==1 than there is nothing to shuffle
Item* r2 = root;
//splitting list,  get first element of second list r2
int i = 0;
while(i < len/2) r2 = r2->next,i++;
//shuffle first list
shuffle(root, len/2);
//shuffle second list
shuffle(r2, len-len/2);
//merging lists
for(int i = 0; i < Min(len/2, len - len/2); i++){
  if(rand()%2) {
        //swap values of two element
        int value = root->value;
        root->value = r2->value;
        r2->value = value;
  }
  //goto next element
  root = root->next;
  r2 = r2->next;
}
}
int main(int argc, char *argv[])
{
srand(time(NULL));
Item* root = constructList(20);
Item* iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
printf("\n");
shuffle(root, 20);
iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
system("PAUSE");
return EXIT_SUCCESS;
}