# Are These Two Friends? Adjacency Lists and Grids

Answer "are these two already friends?" in one step without running out of memory, before every Add friend button: why reading a friend list and a box for every pair both fall short at a million people, and how to choose between an adjacency list, a set per person and an adjacency matrix.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Store a graph as an adjacency list or an adjacency matrix
- Choose between an adjacency list and an adjacency matrix from their costs

## Key takeaways

- Checking a friend list reads up to the whole list, O(k), and a grid with a box for every pair needs V² boxes, about a million million for a million people.
- An adjacency list keeps, for each vertex, the list of its neighbors, like a page per person in an address book.
- An adjacency matrix is a grid with a row and a column for every vertex, and a mark where two vertices are joined; it answers "are these two joined?" in one look, O(1).
- Most real graphs connect each vertex to only a few others, so the adjacency list is the usual choice, and keeping each person's neighbors in a set makes the pair check O(1) on average too.
- A grid earns its space when the graph is small or dense, or when checking pairs is almost the only job.

**Before this:** *Who Knows Whom? When Anything Can Connect: Graphs* kept a page of friends per person. Listing a person's friends is quick, but checking for one name means reading down the page.

The social app has a new rule. Before it shows an **Add friend** button on someone's profile, it checks: are these two already friends? Every profile anyone opens asks that question once, and the app's busiest hour opens about 2 million profiles. The app has 1,000,000 people. Most have about 200 friends; a few, like a singer who joined to talk to fans, have 5 million followers.

## What would you try?

**Read one person's page.** Turn to Dev's page and look for Fay. For an ordinary person that's up to 200 names, O(k). But open the singer's profile and her page has 5 million names: answering "are you already a fan?" reads up to 5 million, and the busiest hour does it again for every fan who looks.

**Keep a box for every pair.** Picture the mileage chart in a printed road atlas: every town down the side, every town across the top, and the miles in the box where a row meets a column. Do that for people: a 1 in the box where Dev's row meets Fay's column if they're friends, a 0 if not. Now every check is one look, O(1), however famous anyone is. But a million people means 1,000,000 × 1,000,000 boxes: a million million, about a terabyte even at one byte a box. Each person has about 200 friends, so about 999,800 of the million boxes in their row hold a 0.

**Keep each person's friends in a set.** The page per person stays, but each page is a set (*Have I Seen This Before? Sets*) instead of a list. "Is Fay on Dev's page?" is one hash lookup, O(1) on average, even on the singer's page, and the memory is still only the friendships that exist.

| What we tried | Are these two friends? | Memory for a million people | Where it breaks |
|---|---|---|---|
| A list of friends per person | O(k): up to 5 million reads | about 200 million names | famous people |
| A box for every pair | O(1): one box | a million million boxes | memory |
| A set of friends per person | O(1) on average | about 200 million names | nowhere so far |

## The questions that lead to it

**Which question does the app ask most?** "Are these two friends?" before every button, and "who are this person's friends?" for every "people you may know" box. Both have to be fast.

**How many boxes would the grid need, and how many would hold a 1?** A million million boxes, and only about 200 million 1s: one box in 5,000. The grid spends almost all its memory saying "no".

**So what should the storage hold?** Only the friendships that exist, in a form that answers "is this one there?" without reading. That's the page per person, with each page as a set.

## How they got their names

Both ways of storing a graph are old enough to have textbook names, and you'll hear them from teammates and interviewers.

- The page per person is an **adjacency list**: for each vertex, the vertices next to it ("adjacent" means "next to"). Its pages can be lists or sets; the name stays the same.
- The grid is an **adjacency matrix** ("matrix" is the math word for a grid of numbers). For a two-way graph it's a mirror image: Dev's row, Fay's column and Fay's row, Dev's column hold the same mark. For a one-way graph, only the box in the follower's row is marked. For a weighted graph, the box holds the weight instead of a 1.

![The chapter's eight-person network stored two ways, side by side: on the left, an adjacency list with a row per person and their friends' names after it, such as Dev followed by Ben, Cara and Eli; on the right, an 8 by 8 grid with the people's first letters A to H along the top and down the side, a 1 in each box where two people are friends and a 0 everywhere else, with the 1s mirrored across the diagonal](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/f1fb16edc391432cbbd9366236ce6990.webp)

## Both, in code

This program stores the chapter's eight people both ways, prints the grid, then asks both the same question: are Dev and Fay friends?

```csharp
string[] people = { "Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana" };
(string, string)[] friendships = { ("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana") };

Dictionary<string, List<string>> friendsOf = new Dictionary<string, List<string>>();
Dictionary<string, int> position = new Dictionary<string, int>();
for (int i = 0; i < people.Length; i++)
{
    friendsOf[people[i]] = new List<string>();
    position[people[i]] = i;
}
int[,] grid = new int[people.Length, people.Length];

foreach ((string first, string second) in friendships)
{
    friendsOf[first].Add(second);
    friendsOf[second].Add(first);
    grid[position[first], position[second]] = 1;
    grid[position[second], position[first]] = 1;
}

string header = "    ";
foreach (string person in people)
{
    header += " " + person[0];
}
Console.WriteLine(header);
for (int row = 0; row < people.Length; row++)
{
    string line = people[row].PadRight(4);
    for (int column = 0; column < people.Length; column++)
    {
        line += " " + grid[row, column];
    }
    Console.WriteLine(line);
}

bool byList = friendsOf["Dev"].Contains("Fay");
bool byGrid = grid[position["Dev"], position["Fay"]] == 1;
Console.WriteLine("Dev and Fay, by list: " + (byList ? "yes" : "no") + ", after reading " + friendsOf["Dev"].Count + " names");
Console.WriteLine("Dev and Fay, by grid: " + (byGrid ? "yes" : "no") + ", after reading 1 box");
```

```text
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
```

```java
String[] people = {"Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"};
String[][] friendships = {{"Ava", "Ben"}, {"Ava", "Cara"}, {"Ben", "Dev"}, {"Cara", "Dev"}, {"Dev", "Eli"}, {"Eli", "Fay"}, {"Gus", "Hana"}};

void main() {
    Map<String, List<String>> friendsOf = new LinkedHashMap<>();
    Map<String, Integer> position = new HashMap<>();
    for (int i = 0; i < people.length; i++) {
        friendsOf.put(people[i], new ArrayList<>());
        position.put(people[i], i);
    }
    int[][] grid = new int[people.length][people.length];

    for (String[] pair : friendships) {
        friendsOf.get(pair[0]).add(pair[1]);
        friendsOf.get(pair[1]).add(pair[0]);
        grid[position.get(pair[0])][position.get(pair[1])] = 1;
        grid[position.get(pair[1])][position.get(pair[0])] = 1;
    }

    String header = "    ";
    for (String person : people) {
        header += " " + person.charAt(0);
    }
    IO.println(header);
    for (int row = 0; row < people.length; row++) {
        String line = String.format("%-4s", people[row]);
        for (int column = 0; column < people.length; column++) {
            line += " " + grid[row][column];
        }
        IO.println(line);
    }

    boolean byList = friendsOf.get("Dev").contains("Fay");
    boolean byGrid = grid[position.get("Dev")][position.get("Fay")] == 1;
    IO.println("Dev and Fay, by list: " + (byList ? "yes" : "no") + ", after reading " + friendsOf.get("Dev").size() + " names");
    IO.println("Dev and Fay, by grid: " + (byGrid ? "yes" : "no") + ", after reading 1 box");
}
```

```text
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
```

```python
people = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"]
friendships = [("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana")]

friends_of = {}
position = {}
for i, person in enumerate(people):
    friends_of[person] = []
    position[person] = i
grid = [[0] * len(people) for _ in people]

for first, second in friendships:
    friends_of[first].append(second)
    friends_of[second].append(first)
    grid[position[first]][position[second]] = 1
    grid[position[second]][position[first]] = 1

header = "    "
for person in people:
    header += " " + person[0]
print(header)
for row, person in enumerate(people):
    line = f"{person:<4}"
    for cell in grid[row]:
        line += f" {cell}"
    print(line)

by_list = "Fay" in friends_of["Dev"]
by_grid = grid[position["Dev"]][position["Fay"]] == 1
print(f"Dev and Fay, by list: {'yes' if by_list else 'no'}, after reading {len(friends_of['Dev'])} names")
print(f"Dev and Fay, by grid: {'yes' if by_grid else 'no'}, after reading 1 box")
```

```text
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
```

```javascript
const people = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"];
const friendships = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];

const friendsOf = new Map();
const position = new Map();
people.forEach((person, i) => {
  friendsOf.set(person, []);
  position.set(person, i);
});
const grid = people.map(() => new Array(people.length).fill(0));

for (const [first, second] of friendships) {
  friendsOf.get(first).push(second);
  friendsOf.get(second).push(first);
  grid[position.get(first)][position.get(second)] = 1;
  grid[position.get(second)][position.get(first)] = 1;
}

let header = "    ";
for (const person of people) {
  header += ` ${person[0]}`;
}
console.log(header);
people.forEach((person, row) => {
  let line = person.padEnd(4);
  for (const cell of grid[row]) {
    line += ` ${cell}`;
  }
  console.log(line);
});

const byList = friendsOf.get("Dev").includes("Fay");
const byGrid = grid[position.get("Dev")][position.get("Fay")] === 1;
console.log(`Dev and Fay, by list: ${byList ? "yes" : "no"}, after reading ${friendsOf.get("Dev").length} names`);
console.log(`Dev and Fay, by grid: ${byGrid ? "yes" : "no"}, after reading 1 box`);
```

```text
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
```

```typescript
const people: string[] = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"];
const friendships: [string, string][] = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];

const friendsOf = new Map<string, string[]>();
const position = new Map<string, number>();
people.forEach((person, i) => {
  friendsOf.set(person, []);
  position.set(person, i);
});
const grid: number[][] = people.map(() => new Array<number>(people.length).fill(0));

for (const [first, second] of friendships) {
  friendsOf.get(first)!.push(second);
  friendsOf.get(second)!.push(first);
  grid[position.get(first)!][position.get(second)!] = 1;
  grid[position.get(second)!][position.get(first)!] = 1;
}

let header = "    ";
for (const person of people) {
  header += ` ${person[0]}`;
}
console.log(header);
people.forEach((person, row) => {
  let line = person.padEnd(4);
  for (const cell of grid[row]) {
    line += ` ${cell}`;
  }
  console.log(line);
});

const byList = friendsOf.get("Dev")!.includes("Fay");
const byGrid = grid[position.get("Dev")!][position.get("Fay")!] === 1;
console.log(`Dev and Fay, by list: ${byList ? "yes" : "no"}, after reading ${friendsOf.get("Dev")!.length} names`);
console.log(`Dev and Fay, by grid: ${byGrid ? "yes" : "no"}, after reading 1 box`);
```

```text
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
```

The `!` after `get(...)` in the TypeScript tab tells the checker "this key is there": a `Map`'s `get` could return `undefined`, and here every person was added first.

Count the zeros: 64 boxes for 7 friendships. The list read Dev's 3 friends to say "no"; the grid read one box. That's the whole trade, and at a million people it decides everything.

## Your language's set per person

To make the list's check one step, change each page from a list to a set: `Dictionary<string, HashSet<string>>` in C#, `Map<String, Set<String>>` with `HashSet` in Java, a `dict` of `set`s in Python, and a `Map` of `Set`s in JavaScript and TypeScript. Adding a friendship becomes `Add`, `add` or `add` on both people's sets, and "are Dev and Fay friends?" becomes one lookup, `Contains`, `contains`, `in` or `has`, O(1) on average. Today's social apps keep their friendships this way, or in a database that does the same job.

## Which one to choose

Start from the size and the job. Most real graphs are **sparse**: each vertex is joined to only a few of the others, as with roads, friendships and links. For those, the adjacency list is the usual choice, with sets when pair checks are common.

A grid earns its space when the graph is small, such as the mileage chart for 50 cities (2,500 boxes), or **dense**, with most pairs joined, or when checking pairs is almost the only job and the vertices never change. Adding a vertex to a grid means redrawing it one row and one column bigger.

## Cost card

V is the number of vertices, E the number of edges, and k how many neighbors one vertex has.

| What you do | Adjacency list | Adjacency list of sets | Adjacency matrix | The everyday reason |
|---|---|---|---|---|
| Memory | O(V + E) | O(V + E) | O(V²) | A page per person with only their friends, versus a box for every possible pair |
| Check whether two are joined | O(k) | O(1) on average | O(1) | Read down one page, look it up in a set, or look in one box |
| List a vertex's neighbors | O(k) | O(k) | O(V) | Read one page, versus check every box in a row |
| Add an edge | O(1) | O(1) on average | O(1) | A note on two pages, versus marking two boxes |
| Add a vertex | O(1) | O(1) | O(V²) | A new page, versus redrawing the whole grid one row and one column bigger |

## Check yourself

2 questions to try on the lesson page.

## So what

When you build anything with a graph inside, from a map to an Add friend button, pick its storage from the job it does most: a page per person for the usual sparse graph, with sets when you check pairs, and a grid only when the graph is small or dense.

## Key terms

- [Adjacency List](https://www.ask-codey.com/glossary/adjacency-list)
- [Adjacency Matrix](https://www.ask-codey.com/glossary/adjacency-matrix)
- [Graph](https://www.ask-codey.com/glossary/graph)
- [Vertex](https://www.ask-codey.com/glossary/vertex)
- [Edge](https://www.ask-codey.com/glossary/edge)

## Cheat sheets

- [Are These Two Friends? Adjacency Lists and Grids](https://www.ask-codey.com/cheat-sheets/ds-graph-representations-cheat-sheet)

## Related

- [Who Knows Whom? When Anything Can Connect: Graphs](https://www.ask-codey.com/lessons/ds-graphs)

Source: https://www.ask-codey.com/lessons/ds-graph-representations
