# Introduction to Multi Linked List

• Last Updated :16 May, 2022

In a multi-linked list, each node can have N number of pointers to other nodes. A multi-linked list is generally used to organize multiple orders of one set of elements.

The properties of a multi-linked list are mentioned below.

• It is an integrated list of related structures.
• All the nodes are integrated using links of pointers.
• Linked nodes are connected with related data.
• Nodes contain pointers from one structure to the other.

The structure of a multi-linked list depends on the structure of a node. A single node generally contains two things:

• A list of pointers
• All the relevant data.

Shown below is the structure of a node that contains only one data and a list of pointers.

## C

 `typedef``struct``node {``    ``int``data;``    ``vector<``struct``node*> pointers;``} Node;`

## Java

 `/*package whatever //do not write package name here */` `import``java.io.*;` `class``GFG {``    ``public``static``void``main(String[] args) {}``    ``public``static``class``Node {``        ``int``data;``        ``Node[] children;``    ``};``}` `// This code is contributed by ishankhandelwal`

Some use cases of a multi-linked list are:

• Multiple orders of one set of elements
• Representation of a sparse matrix
• List of List

Multiple orders of one set of elements:

• For example, suppose the task is to maintain a list in multiple orders, age and name here, we can define a Node that has two references, an age pointer and a name pointer.
• Then it is possible to maintain one list, where if we follow the name pointer we can traverse the list in alphabetical order
• And if we try to traverse the age pointer, we can traverse the list by age also.
• This type of node organization may be useful for maintaining a customer list in a bank where the same list can be traversed in any order (name, age, or any other criteria) based on the need. For example, suppose my elements include the name of a person and his/her age. e.g.

(ANIMESH, 19), (SUMIT, 17), (HARDIK, 22), (ISHA, 18)

Multiple orders of set

Inserting into this structure is very much like inserting the same node into two separate lists. In multi-linked lists it is quite common to have back-pointers, i.e. inverses of each of the forward links; in the above example, this would mean that each node had 4pointers.

Representation of Sparse Matrix:

Multi Linked Lists are used to store sparse matrices. A sparse matrix is such a matrix that has few non-zero values. If we use a normal array to store such a matrix, it will end up wasting lots of space.

Spare Matrix

The sparse matrix can be represented by using a linked list for every row and column.

• A node in a multi-linked list has four parts:
• The first part stores the data.
• The second stores the pointer to the next row.
• Third for the pointer to the next column and
• Fourth for storing the coordinate number of the cell in the matrix.

Representation of sparse matrix

List of List:

A multi-linked list can be used to represent a list of lists. For example, we can create a linked list where each node is itself a list and have pointers to other nodes.
See the structure below:

• It is a 2-dimensional data structure.
• Here each node has three fields:
• The first field stores the data.
• The second field stores a pointer to the child node.
• The third field stores the pointer to the next node.

List of List (multi-level linked list)

• Sets of same data can be processed into multiple sequences.
• Data are not duplicated anywhere.
• Data of one kind exist only once in the list.

Let’s first see the structure of a node of Doubly Linked List:

## C

 `typedef``struct``node {``    ``int``data;``    ``struct``node* prev;``    ``struct``node* next;``} Node;`

## Java

 `/*package whatever //do not write package name here */` `import``java.io.*;` `class``GFG {``    ``public``static``void``main(String[] args) {}``    ``public``static``class``Node {``        ``int``data;``        ``Node prev;``        ``Node next;``    ``};``}` `// This code is contributed by ishankhandelwal`