Graphs: Adjacency List

`What is Adjacency List`

Here we have an array of linked lists.
In every element of the array, We have a linked list.
The linked list contains the index of adjacent neighbors of a given node
The john is present in the 0 index and the linked-list at zero position contains the edges 1, 2, and 3 meaning that the john is connected to Mary, bob and Alice.

We are storing only the edges that exist, so this is more space-efficient than the matrix.
We have V vertices and if E represents the number of edges. The space complexity of the graph is (V+E).

When every node is connected to every other node in the tree, It is called a dense graph.
Here is the total number of edges (Because every node is connected to all other nodes apart from itself)

E = V * (V-1) = V2-V = V2

Here there are two steps
- Delete the node.
- Also remove all the usages of it, For which other nodes are connected to it. So we will iterate the array and in each array, we visit individual nodes in the list and remove them.
Iterating the array --> There are n items --> The complexity is O(V).
In each iteration, We need to remove the target node from each linked list. So if the graph has E edges there are E nodes across all the linked lists.
Time complexity is O(E+V)
In a dense graph --> O(V2)