Hello,
I am not clear on below point because if we are taking array of linked List for adjacency list then each vertex will be at particular index else array won’t work. so can please clarify.
Search can take up to O(V)O(V) if all V nodes are present at a certain index and we have to traverse them.
Hi @chandraprabha,
This is Fatimah Abdullah from Educative. Thank you for reaching out to us!
Yes, it is correct that we are using an array, therefore, it is understood that we can access each index in O(1) . However, this is not the standard implementation of an adjacency list. You might find some implementations using a linked list of linked lists. In that case, the complexity of the search will be O(VxV) . We mentioned indexing so that it is clear that this only applies if an array is used. I hope this clears up your confusion.
Thank you for reaching out to us! If you have any further queries, please let us know.
Best Regards,
Fatimah Abdullah | Developer Advocate
Educative