Difference between Single Linked List and Generalized Linked List ?

What is the difference between Single Linked List and Generalized Linked List?

Generalized Linked 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 atom or the list of atoms. 

Thus

L = (l1, l2, l3, l4, …, ln)

where n is a total number of nodes in the list.

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 atom

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 Generalized Linked List?

Generalized linked lists are used because the efficiency of polynomial operations using linked lists is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equations efficiently. It helps us to represent multi-variable polynomial along with the list of elements. 

Representation of GLL, for example: 

When the first field is 0, it indicates that the second field is variable. If the first field is 1 means the second field is a down pointer, which means some list is starting.

Polynomial Representation using Generalized Linked List

The typical node structure will be:

Here Flag = 0 means variable is present

Flag = 1 means down pointer is present

Flag = 2 means coefficient and exponent is present

Now let's take an example:

This is basically 9x^5 + 7xy^4 + 10xz

Single Linked List :

import java.util.*;

import java.io.*;

import java.lang.*;

class AbhiBlog { 

    static class Node{

        int data;

        Node next;

        Node(int x){

            data=x;

            next=null;

        }

    }

    public static void main(String args[]) 

    { 

        Node head=new Node(10);

    Node temp1=new Node(20);

    Node temp2=new Node(30);

    head.next=temp1;

    temp1.next=temp2;

    System.out.print(head.data+"-->"+temp1.data+"-->"+temp2.data);

    } 

} 

So it is like a One-way chain or singly linked list that can be traversed only in one direction. In other words, we can say that each node contains only the next pointer, therefore we can not traverse the list in the reverse direction.

But we can add two polynomial using a doubly-linked list efficiently.