performance of the adjacency list structure table summarizes the performance of the adjacency list structure implementation of graphassuming that the primary collection and all secondary collections (vare implemented with doubly linked lists asymptoticallythe space requirements for an adjacency list are the same as an edge list structureusing ( mspace for graph with vertices and edges the primary list of vertices uses (nspace the sum of the lengths of all secondary lists is ( )for reasons that were formalized in propositions and in shortan undirected edge (uvis referenced in both (uand ( )but its presence in the graph results in only constant amount of additional space we have already noted that the incident edges(vmethod can be achieved in (deg( )time based on use of (vwe can achieve the degree(vmethod of the graph adt to use ( timeassuming collection (vcan report its size in similar time to locate specific edge for implementing get edge( , )we can search through either (uand (vby choosing the smaller of the twowe get (min(deg( )deg( ))running time the rest of the bounds in table can be achieved with additional care to efficiently support deletions of edgesan edge (uvwould need to maintain reference to its positions within both (uand ( )so that it could be deleted from those collections in ( time to remove vertex vwe must also remove any incident edgesbut at least we can locate those edges in (deg( )time the easiest way to support edgesin (mand count edgesin ( is to maintain an auxiliary list of edgesas in the edge list representation otherwisewe can implement the edges method in ( mtime by accessing each secondary list and reporting its edgestaking care not to report an undirected edge (uvtwice operation vertex count)edge countverticesedgesget edge( ,vdegree(vincident edges(vinsert vertex( )insert edge( , ,xremove edge(eremove vertex(vrunning time ( (no(mo(min(deg( )deg( )) ( (deg( ) ( ( (deg( )table running times of the methods of graph implemented with the adjacency list structure the space used is ( )where is the number of vertices and is the number of edges