Question about space complexity

I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to v, and which nodes are outwardly adjacent to v. To get around this, my idea was to use a list of pairs, where each pair consists of two sets - which correspond directly to the inward and outward adjacency sets of any vertex in the graph.

I understand that the maximum number of edges in a directed acyclic graph of size $n$ is $\frac{n(n-1)}{2}$. In the proposed graph encoding, the existence of a vertex u in vertex v's 'in' set implies the existence of an edge (u, v). The existence of a vertex u in vertex v's 'out' set implies the existence of an edge (v, u). Additionally, $u \in in(v) \iff v \in out(u)$. Therefore, my intuition tells me that this representation of a directed acyclic graph has a space complexity of $\mathcal{O}(2|E|)$, since the existence of each edge $(v, u)$ is implied twice; once by $v \in in(u)$ and once by $u \in out(v)$.

My question is, does my intuition fail me?

You say "using a structure similar to an adjacency list". So space complexity required for storing undirected graph using adjacency list is $O(|V| + |E|)$, in your case $O(|V| + 2|E|)$. That is implemented using a list of nodes where each node has two fields: label of the vertex and pointer to the list of adjacent nodes (in your case two lists).

But I don't know how you are going to use the graph. If you are interested in simply a set of edges then you could store them in a list as triples $$. But if at some point for a node $v$ you want to systematically loop on all adjacent vertices (inward or outward) then you should use adjacency list.

Finally if you want to decide in $O(1)$ if there is an edge $$ then you should use hash like data structure to store pairs $$.

StackExchange Computer Science Q#78139, answer score: 2