std::list.begin() slows down for bigger lists

I have following problem. I need to implement LexBFS algorithm which has to use double linked list. I chose std::list . When I finally debugged my code I've noticed strange behaviour - list operations slows down as list grows. I narrowed down to this one line:

// start new iteration
clock_t tbegin = clock();
if(L.size() && L.begin()->empty) {
  double ee = double(clock() - tbegin) / CLOCKS_PER_SEC;
  cerr << fixed << setprecision(6) << "t: " << ee << " size: " << L.size() << "\n";
  //...
}
// here I make other operations on L...

L is std::list<Class> where Class is my simple struct with a few fields.

This is the output:

t: 0.000086 size: 5224
t: 0.000124 size: 7818
t: 0.000281 size: 17515
t: 0.000300 size: 19310
t: 0.000341 size: 21202
t: 0.000406 size: 25117
t: 0.000459 size: 29202
t: 0.000510 size: 31307
t: 0.000528 size: 33413
t: 0.000562 size: 35487
t: 0.000638 size: 39740
t: 0.000706 size: 41885
t: 0.000710 size: 44037
t: 0.000747 size: 46261
t: 0.000868 size: 52670
t: 0.000982 size: 54800
t: 0.000957 size: 56895
t: 0.001084 size: 58993
t: 0.001114 size: 61101

Simple lookup slows down! What is going on?

Thanks in advance.