Introduction to Generalized Lists and Multi-Linked Lists

title: Introduction to Generalized Lists and Multi-Linked Lists
link: Introduction to Generalized Lists and Multi-Linked Lists
catalog: true
lang: en
date: 2020-02-27 01:18:23
tags:

c++
data structures
categories:
[notes, data structures]

1. Generalized Lists#

Generalized lists are an extension of linear lists.
In linear lists, each element is a basic unit.
In generalized lists, these elements can be either single elements or another generalized list.

typedef struct GNode *GList; 
struct GNode {
    int Tag;    // Tag field: 0 represents a node with a single element, 1 represents a node with a generalized list
    union {     // Union of SubList pointer field and Data field for single element, sharing storage space
        ElementType Data;
        GList SubList;
    } URegion;
    GList Next;     // Pointer to the next node
};

2. Multi-Linked Lists#

Nodes in a linked list can belong to multiple chains.

In a multi-linked list, nodes have multiple pointer fields, such as Next and SubList in the previous example;
However, a linked list with two pointer fields is not necessarily a multi-linked list, for example, a doubly linked list is not a multi-linked list.

Multi-linked lists have a wide range of applications:

Basically, complex data structures such as trees and graphs can be implemented using multi-linked lists for storage.

Example: Storing a Matrix#

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 will result in a lot of wasted storage space.

Analysis: Use a typical multi-linked list called the cross-linked list to store sparse matrices.
Only store non-zero elements

Pointer fields of nodes:
Row coordinate (Row), column coordinate (Col), value (Value)
Each node is linked horizontally and vertically through two pointer fields:
Row pointer (also known as the right pointer) Right
Column pointer (also known as the down pointer) Down
Use a tag field Tag to distinguish between the head node and non-zero element nodes.
The tag value of the head node is "Head", and the tag value of non-zero element nodes in the matrix is "Term"