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 :)
Yes.
Linked lists consume more memory, because they have to store pointers to the next element in addition to elements themselves.
Vectors, unlike lists, occupy a single block of memory which is more cache-efficient.
But how can we maintain a sorted vector without incurring any additional cost while adding a new edge?
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)
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.