First Encounter with Generalized Lists and Multilinked Lists

This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

I. Generalized Lists

• A generalization of linear lists
• In a linear list, all n elements are basic single elements
• In a generalized list, these elements can be not only single elements but also another generalized list

> typedef struct GNode *GList; struct GNode {
>     int Tag;    //标志域:0表示结点是单元素，1表示结点是广义表
>     union {     //子表指针域SubList域单元素数据域Data复用，共用存储空间
>         ElementType Data;
>         GList SubList;
>     } URegion;
>     GList Next;     //指向后继结点 };

II. Multilinked Lists

• Nodes in a list may belong to multiple chains

Nodes in a multilinked list have multiple pointer fields, as in the previous example which contains Next and SubList; However, a list with two pointer fields is not necessarily a multilinked list — for example, a doubly linked list is not a multilinked list

• Multilinked lists have a wide range of applications:

Relatively complex data structures such as trees and graphs can generally be implemented using multilinked lists for storage

Example: Storing Matrices

Using a two-dimensional array has two drawbacks

• First, the size of the array needs to be determined in advance
• Second, for sparse matrices, it causes a large waste of storage space

Analysis: Use a typical multilinked list — orthogonal linked list to store sparse matrices Only store non-zero elements

• Pointer fields of a node: Row coordinate Row, column coordinate Col, value Value
• Each node is linked through two pointer fields to connect nodes in the same row and same column: Row pointer (or right pointer) Right Column pointer (or down pointer) Down
• A tag field Tag is used to distinguish between head nodes and non-zero element nodes: The tag value for head nodes is “Head”, and the tag value for non-zero element nodes is “Term”