Editing Adjacency list (section)

==Data structures==
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only {{math|{{abs|''V''}}<sup>2</sup>/8}} bytes of contiguous space, where {{math|{{abs|''V''}}}} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages [[locality of reference]].

However, for a sparse graph, adjacency lists require less space, because they do not waste any space to represent edges that are not present. Using a naïve array implementation on a 32-bit computer, an adjacency list for an undirected graph requires about {{math|1=2⋅(32/8){{abs|''E''}} = 8{{abs|''E''}}}} bytes of space, where {{math|{{abs|''E''}}}} is the number of edges of the graph.

Noting that an undirected simple graph can have at most {{math|({{abs|''V''}}<sup>2</sup>&minus;{{abs|''V''}})/2 ≈ ''V''<sup> 2</sup>}} edges, allowing loops, we can let {{math|1=''d'' = {{abs|''E''}}/{{abs|''V''}}<sup>2</sup>}} denote the density of the graph. Then, {{math|8{{abs|''E''}} > {{abs|''V''}}<sup>2</sup>/8}} when {{math|{{abs|''E''}}/{{abs|''V''}}<sup>2</sup> > 1/64}}, that is the adjacency list representation occupies more space than the adjacency matrix representation when {{math|''d'' > 1/64}}. Thus a graph must be sparse enough to justify an adjacency list representation.

Besides the space trade-off, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes {{math|''O''({{abs|''V''}})}} time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.