Adjacency List

An Array that contains pointers to node Neighbourhoods. For a directed graph, this contains the out-

Drawing 2025-03-12 11.39.49.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

B

C

D

E

F

1

root

2

null

0

2

root

3

null

A

C

B

D

E

F

G

0

1

2

3

5

4

6

Link to original

Graph Operations

• Adding an edge ($i,j$)
  • Worst Case : $O(1)$
• Remove edge ($i,j$)
  • Worst case: $O(n)$
• Edge query
  • Worst case: $O(n)$
• Adding node
  • Worst case: $O(n)$
• Deleting a node
  • Worst case $O(n^2)$