Comparing Linked Lists and Vectors

21. April 2012, 08:14

In this article I’m just going to show a very brief comparison of the performance of C++ vectors and linked lists.

First, some code to compare the two:

#include <vector>
#include <list>
#include <stdlib.h>
#include <sys/time.h>
#include <iostream>
double microTime() {
  timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec*1000000.0 + tv.tv_usec;
}
int main(int ac, char** av) {
  long iterations = 1000;
  if (ac == 2) {
    iterations = atol(av[1]);
  }
  //Do <iterations> push front and push back operations
  //to a vector and a linked list
  //Record the times for each operation

  std::cerr<<iterations<<‘\t’;
  {
    std::vector<int> v;
    double start = microTime();
    for (long i = 0; i < iterations; ++i) {
      v.insert(v.begin(), 1);
    }
    std::cerr<<microTime() – start<<‘\t’;
  }

  {
    std::list<int> l;
    double start = microTime();
    for (long i = 0; i < iterations; ++i) {
      l.push_front(1);
    }
    std::cerr<<microTime() – start<<‘\t’;
  }

  {
    std::vector<int> v;
    double start = microTime();
    for (long i = 0; i < iterations; ++i) {
      v.push_back(1);
    }
    std::cerr<<microTime() – start<<‘\t’;
  }

  {
    std::list<int> l;
    double start = microTime();
    for (long i = 0; i < iterations; ++i) {
      l.push_back(1);
    }
    std::cerr<<microTime() – start<<‘\t’;
  }
  std::cerr<<‘\n’;

  return 0;
}

And then I’ll create a lot of data points like this (in linux):
for I in `seq 1000 1000 30000`; do ./a.out $I 2>> time_data.txt; done

Okay, now a graph showing the comparison

So what happened here? The vector is faster at inserting at the end because insertion is immediate – it just puts the value into the end of an array and then increments its total size. If it isn’t large enough then it requests more memory from the operating system and need to copy over some memory, but this is rare. The link list needs to write not just the new value, but also the forward and backward links. Additionally, the vector can allocate large chunks of memory at a time, whereas the linked list only allocates memory for one link at a time. This makes the vector more efficient when inserting data into the end of the structure.

However, the vector is terribly slow compared to the linked list when inserting at the beginning — why is that? First, the linked list does the same amount of work to insert at the end or the beginning so its performance doesn’t change. On the other hand, since the first spot is already occupied in the vector it must move everything over 1 space so that there is room at the beginning. This has a very high performance cost that rises as the number of elements increases. (eg. shift 1 element, then shift 2, then shift 3, then shift 4, and so on). If you insert a total of N elements then the vector must do (1 + 2 + 3 + … + N-2 + N-1) shifts, which is:

shifts, which is why you should avoid vectors if you will inserting at the beginning of your data structure.

Ben Firner

Algorithms

---

Comment

Commenting is closed for this article.

---