If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all the vertices $j$ such that $(i,j)$ is an edge of $G$. On the other hand, if I want to find all the in-neighbors of $i$, i.e. the set of all vertices $j$: $(j,i)$ is an edge, then this takes $\mathcal O(n)$.If I want to answer both in- and out-neighbor queries fast, I could just store the graph $G'$ obtained from $G$ by reversing all the edges, but that doubles memory usage. Is there a graph storage scheme for which both in- and out-neighbor queries take $\mathcal O(d)$ time, but doesn't required double the memory?
directed graph data structure with fast in/out neighbor query
graphs;data structures;efficiency
If you care about constant factors, then big-Oh notation is not a useful tool to help you compare or measure possible data structures.  If you want to minimize storage as much as possible, you need to think about the layout of the bits -- and then it would help to know concrete parameters and information, like roughly how big $n$ is, a rough estimate of the average degree (averaged over all vertices), a rough estimate of the largest degree and the distribution of degrees, etc.For instance, one scheme is to represent the list of out-neighbors using something more efficient than a plain linked list (e.g., a linked list of buckets, where each bucket contains $c$ elements, and where you choose an optimal value of $c$ to minimize expected space usage).  Or, you can pack these lists of out-neighbors and in-neighbors into a single big array, with each vertex having a pointer to the first index in that array where the sequence of out-neighbors or in-neighbors exist.  You can also arrange that each entry needs only $\lceil \lg n \rceil$ bits, where $n$ is the number of vertices.Another scheme is to use a multi-linked list as Patrick suggests, but with a slight twist.  Instead of storing a pair of vertices $(a,b)$ in each linked-list node, store $a \oplus b$ (the xor of the identifier for vertex $a$ and the identifier for vertex $b$).  This will be present in two linked lists: the out-neighbors of $a$, and the in-neighbors of $b$.  Each linked-list node will have two next pointers.  Notice that, when traversing the list of out-neighbors of $a$, all of the nodes will have $a$ as one of the two vertices, so if the value $x$ is stored in the node, we know it represents an edge to $a \oplus x$ (since $a \oplus (a \oplus b) = b$).  Similarly, when traversing the list of in-neighbors of $b$, the value $x$ in a node represents an edge from the vertex $x \oplus b$.  This doesn't reduce the number of pointers compared to a naive scheme, but it halves the amount of space for storing the data (the vertex identifiers) in each linked-list.There are many more such bit-packing tricks and considerations that can be tried when you care about constant factors.