tirupati's blog

list vs vector
By tirupati, history, 9 years ago, In English

I usually use vector arr[n] to represent the adjacency list of a n-vertex graph. What if I use list instead of a vector. I mean it's O(1) to add an edge in the list similar to vector(amortized) also it's O(n) to check if there is an edge between two vertices in both vector and list. I have seen most people using vector instead of list. Are there any performance costs associated with lists compared to vector?

THANK YOU :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Are there any performance costs associated with lists compared to vector?

Yes.

  1. Linked lists consume more memory, because they have to store pointers to the next element in addition to elements themselves.

  2. Vectors, unlike lists, occupy a single block of memory which is more cache-efficient.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

also it's O(n) to check if there is an edge between two vertices in both vector and list

for sorted vector

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    But how can we maintain a sorted vector without incurring any additional cost while adding a new edge?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Depends on the purpose:

Why list?

If the problem requires deletion of vertices, or addition of vertices with numbering less than the existing ones, use list.

erase in list: O(1), in vector: propotional to no. of elements after the position (can go upto O(n) )

Why vector?

Easier to implement. Can be accessed directly by indices unlike list.

(ar[i] is permitted in vector, but not in list)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Iterating trough vector is waaaay faster than iterating trough list (because of the cashe-efficiency [user:skycelote] mentioned above. And it should definitely be your choice if you'd like to iterate trough container fast enough.

→ Reply