多层链表 Multi-level Linked List

多层链表 Multi-level linked list, 又称为十字链表 Orthogonal linked list.

可以使用它存储稀疏矩阵和图等数据结构.

链表中的每个节点包括两个指针, 分别指向左右水平的邻接节点和上下垂直邻结节点. 如果使用双链表风格的话, 每个节点会包含四个指针.

十字链表的应用: 十字链表最常见的应用是稀疏矩阵表示. 简而言之, 稀疏矩阵是其中大多数元素为零 (或任何已知常数) 的矩阵. 它们经常出现在科学应用中, 将稀疏矩阵表示为二维数组会浪费大量内存; 相反地, 稀疏矩阵表示为十字链表. 我们仅为矩阵中的非零元素创建一个节点, 并且在每个节点中存储值, 行索引和列索引以及指向其他节点的必要指针. 这节省了大量性能开销, 并且是实现稀疏矩阵最节省内存的方法.

单链表风格

每个节点只存储两个指针, 分别指向右侧和下层相邻的节点.

双链表风格

每个节点存储四个指针, 分别指向左右水平的邻接节点和上下垂直邻结节点.