Header Linked List & Polynomials

Header Linked List:

Header linked list is a linked list which always contains a special node, all the header nodes at the beginning of the list.

The following are the two kinds of widely used header lists:

1. A grounded header list is a header list where the last node contains null pointer.
2. A circular header list is a header list where last node points back to the header node

Observe that the list pointer start always points to the header node, accordingly LINK[START]=NULL indicates that the grounded release is empty.  And LINK[START]=START  indicates the circular header list is empty.

 Algorithm: (Traversing a circular header list) Let List be circular header list  in memory. This algorithm traverses list, applying an operation process to each node of list.

1. Set PTR:=LINK[START] [Initialize the pointer PTR]
2.  Repeat steps 3 and 4 while PTR!= START
3.  Apply process to INFO[PTR] 
4. Set PTR:=LINK[PTR]  [PTR now point to next node]

        [ End of step 2 loop]

    5. Exit

Polynomials:

Header linked list are frequently used to maintain the polynomials in memory.  The header list plays an important part of this representation. 

Let p(x) denotes the following polynomial in one variable (containing four non zero terms):

                                             p(x)=2x8-5x7-3x2+4

 Then p(x) may be represented by the header linked list shown in figure, where each node corresponds to a non zero term p(x).  Specifically, the information part of the nod is divided into two field representing, respectively, the coefficient and the exponent of the corresponding term, and in node or link according to decreasing degree.

 Observe that the list pointer variable POLY points to the header node, whose exponent field is assign in negative number, in this case - 1.  Here the array representation of the linked list will require three linear arrays, which will call COEF, EXP and LINK.