Using a novel index, which combines hashes with linked-list, it is possible to gain the same complexity O(n) when traversing the whole graph.
Index-free adjacency is an implementation detail - with drawbacks:
If you store the vertices at each node as list of direct pointers, then traversing all neighbors has complexity O(k), if a vertex has k edges. Note that this is the best possible complexity because O(k) is the size of the answer. Deleting a single edge also has the same complexity of O(k) (assuming a doubly linked list), which is much worse.
Furthermore, usually one will want to be able to traverse edges in both directions, which makes it necessary to store direct pointers on both vertices that are incident with an edge. A consequence of this is that deleting a supernode is even worse: To remove all incident edges one has to visit every adjacent vertex – and perform a potentially expensive removal operation for each of them.
In general, a graph database is “a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data” (Wikipedia) – independent of the way the data is stored internally.
Your last sentence is perfect. Each chosen internal representation has time/space-tradeoffs its making. Users needs to pick a graph database based on the tradeoffs they can live with for their application.
Index-free adjacency is an implementation detail - with drawbacks:
If you store the vertices at each node as list of direct pointers, then traversing all neighbors has complexity O(k), if a vertex has k edges. Note that this is the best possible complexity because O(k) is the size of the answer. Deleting a single edge also has the same complexity of O(k) (assuming a doubly linked list), which is much worse.
Furthermore, usually one will want to be able to traverse edges in both directions, which makes it necessary to store direct pointers on both vertices that are incident with an edge. A consequence of this is that deleting a supernode is even worse: To remove all incident edges one has to visit every adjacent vertex – and perform a potentially expensive removal operation for each of them.
In general, a graph database is “a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data” (Wikipedia) – independent of the way the data is stored internally.