十字鏈結串列

十字鏈結串列（英語：Orthogonal linked list）是電腦科學中的一種進階資料結構，在Linux核心中應用廣泛。具體說，一個二維十字鏈結串列是鏈結串列的元素同時連結左右水平鄰結點與上下垂直鄰結點。這一方法可以推廣到更高維以儲存稀疏矩陣、圖等資料集合。^[1]

簡介

典型用於稀疏矩陣儲存時，矩陣每個元素為以下五元組：

typedef struct OLNode {    
     int  LineNumber, ColumneNumber;          //行号与列号     
     ElemType value;        //值     
     struct OLNode *right, *down;  //同行、同列下一个元素的指针     
}OLNode, *OList;

分別建立兩個指標陣列，分別存放每行或每列的第一個結點的位址。

參見

• 鏈結串列
• 舞蹈鏈