Generalised Linked List

Linked list is linear data structure, But when we create list into another list ie nested list that time we can't use normal linked list.

We can solve this problem using Generalised Linked list:

Generalised Linked List :

It is list of list.
A Generalized Linked List L, is defined as a finite sequence of n>=0 elements, l1, l2, l3, l4, …, ln, such that li are either item(data) or the list of items. Thus L = (l1, l2, l3, l4, …, ln) where n is total number of nodes in the list

Representation of GLL:

To represent a list of items there are certain assumptions about the node structure.

Flag = 1 implies that down pointer exists

Flag = 0 implies that next pointer exists

Data means the item

Down pointer is the address of node which is down of the current node

Next pointer is the address of node which is attached as the next node.

Why We use Generlised Linked List:

1. Generalized linked lists are used because although the efficiency of polynomial operations using linked list is good

2. but still, the disadvantage is that the linked list is unable to use multiple

variable polynomial equation efficiently.

3. It helps us to represent multi-variable polynomial along with the list of elements.structure of Generalized Linked List

class node {

data_type data;

int flag;

node *next, *down;

}

Example of GLL : Represent the GLL for: ( a, (b, c), d) When first field is 0, it indicates that the second field is variable. If first field is 1 means the second field is a down pointer, means some list is starting. Polynomial Representation using Generalized Linked List:
Here Flag = 0 means variable is present Flag = 1 means down pointer is present Flag = 2 means coefficient and exponent is present
Example: 9x^5+ 7x^4y+ 10xz

Here Flag = 0 means variable is present
Flag = 1 means down pointer is present
Flag = 2 means coefficient and exponent is present

In the above example the head node is of variable x. The temp node shows the first field as 2 means coefficient and exponent are present.