When we talk about how to show graphs, we have two main options: adjacency lists and adjacency matrices. Each choice affects how much memory we use, and which one is better depends on what kind of graph we have.

Adjacency matrices are easy to understand. They use a grid, or a 2D array, to show connections. For a graph with $n$ points (or vertices), this grid takes up $O(n^2)$ space. This works best for dense graphs. Dense graphs have many edges, close to the maximum number possible with those points.

But if the graph is sparse, meaning it has few edges, the matrix wastes a lot of space. Many spots in that $O(n^2)$ grid will just be empty.

On the other hand, adjacency lists save memory for sparse graphs. In this method, each point points to a list of nearby points. This way, the total space needed is $O(n + E)$, where $E$ is the number of edges. We only keep information about the edges that actually exist, making it a smarter choice when we have way fewer edges than possible.

Let’s look at a real-world example: a social media site. Imagine millions of users (the points), but only a small number of them are connected to each other (the edges). Using an adjacency matrix would waste a lot of memory because it would try to show all possible connections, even the ones that don’t exist. But an adjacency list would only store the real connections, which saves a lot of memory.

However, there’s a trade-off. When you need to check if an edge exists, adjacency matrices make it super quick — it takes $O(1)$ time. With adjacency lists, it might take longer — up to $O(k)$ time in the worst case, where $k$ is the number of edges connected to a single point.

In short, when choosing how to represent a graph, think about how many connections there are and what you'll need to do with the graph later. You have to balance memory use and speed. Picking the right way can really make a big difference!