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

  • c++
  • data structures
  • [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"
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.