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"