对于有向图来说，邻接表是有缺陷的。用邻接表存储，了解出度特别容易，知道入度就特别难；用逆邻接表存储，解决了入度问题，出度又特别难得到。有没有两全的办法呢？有，就是十字链表（orthogonal list），是有向图的另一种链式存储结构，将有向图的邻接表和逆邻接表结合在一起，就得到了有向图的另一种链式存储结构——十字链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫作顶点结点。这两类结点结构如图7－20所示。

图7－20 十字链表头结点和表结点

如图7－21所示为图的十字链表表示。若有向图是稀疏图，则它的邻接矩阵一定是稀疏矩阵，这时该图的十字链表表示法可以看成是其邻接矩阵的链表表示法。只是在图的十字链表表示法中，弧结点所在的链表不是循环链表且结点之间相对位置自然形成，不一定按顶点序号有序。另外，表头结点即顶点结点，它们之间并非循环链式连接，而是顺序存储。

十字链表的好处就是把邻接表和逆邻接表整合在一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度，而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此在有向图应用中，十字链表是非常好的数据结构类型。

图7－21 图的十字链表存储