Course contentsShow
← Computer Science
Lesson 674 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency List: Operations and Complexity

Analyze O(1) edge insertion and O(degree) edge lookup complexity in adjacency list representation.

Adjacency List: Operations and Complexity

You'll learn why adjacency lists excel at adding edges quickly but require scanning when checking if a specific edge exists.

Now that you understand how adjacency lists store graphs (using arrays or linked lists to hold each vertex's neighbors), let's analyze how efficiently they perform common operations.

Edge Insertion: O(1) Time

Adding an edge between two vertices is remarkably fast with adjacency lists. When you want to connect vertex A to vertex B, you simply append B to A's neighbor list. This is a constant-time operation:

  • For arrays: append to the end (amortized O(1))
  • For linked lists: add a new node at the head or tail (O(1))

Think of it like adding a contact to your phone's favorites list—just tack it on the end, no reorganizing needed.

For undirected graphs, you perform this twice (once for each direction), but that's still O(1) overall.

Edge Lookup: O(degree) Time

Checking whether an edge exists between vertices A and B is slower. You must scan through A's entire neighbor list to see if B appears. The time depends on how many neighbors A has—its degree.

  • Best case: O(1) if B is the first neighbor
  • Worst case: O(degree) if B is last or absent
  • Average case: O(degree)

It's like searching through your phone contacts by scrolling—the more contacts, the longer it takes.

For sparse graphs (few edges), degrees are typically small, making this acceptable. For dense graphs (many edges), this can become expensive compared to adjacency matrices, which offer O(1) edge lookup.

Key Takeaway: Adjacency lists provide O(1) edge insertion, making them excellent for building graphs quickly, but edge lookup takes O(degree) time because you must scan through a vertex's neighbor list sequentially.