Header Linked Lists Overview

Header Linked Lists

• A header linked list is a linked list that always contains a special node called the header node, situated at the beginning of the list.
• Two common types of header lists are grounded and circular.

Grounded Header List

• In a grounded header list, the last node contains a NULL pointer.
• The list pointer START always points to the header node.
• If the list is empty, LINK[START] = NULL.

Circular Header List

• In a circular header list, the last node points back to the header node.
• The list pointer START always points to the header node.
• If the list is empty, LINK[START] = START.

Header Linked Lists (General Properties)

• The first node in a header list is the node following the header node.
• A header node is an additional node, holding no data, ensuring every node has a predecessor.
• Unless specified, header lists are typically circular.
• Consequently, the header node acts as a sentinel marking the end of the circular list.
• Circular header lists replace ordinary linked lists to avoid null pointers, as each pointer holds valid addresses.
• Every node possesses a predecessor, making a special case for the first node unnecessary.

Traversing a Circular Header List

• Algorithm TRAVCHL(INFO, LINK, START).
• Input: A circular header list in memory (LIST).
• The algorithm traverses LIST, applying an operation PROCESS to each node.
• To begin, set a pointer PTR = LINK[START].
• Repeat steps 3 and 4 while PTR is not equal to START.
• Apply the operation PROCESS to INFO[PTR].
• Update PTR by resetting it to LINK[PTR].
• Exit.

Locating an ITEM

• Algorithm SRCHL(INFO, LINK, START, ITEM, LOC).
• Input: A circular header list in memory (LIST), target ITEM.
• The algorithm finds the location (LOC) of the first occurrence of ITEM within LIST. If ITEM is absent, LOC is set to NULL.
• Start by setting PTR = LINK[START].
• Repeat while INFO[PTR] is not equal to ITEM and PTR is not equal to START.
• Update PTR to LINK[PTR].
• If INFO[PTR] == ITEM, then set LOC = PTR. Otherwise, set LOC = NULL.
• Exit.

Deleting the First Node Containing ITEM in CHL

• Algorithm FINDLOCHL(INFO, LINK, START, ITEM, LOC, LOCP)
• This algorithm locates the first node containing ITEM, storing its location in LOC and the location of its predecessor in LOCP.
• If ITEM is not found, LOC is set to NULL.
• Set SAVE = START, PTR = LINK[START].
• Repeat while INFO[PTR] is not equal to ITEM and PTR is not equal to START
• Set SAVE = PTR and PTR = LINK[PTR].
• If INFO[PTR] == ITEM, set LOC = PTR and LOCP = SAVE. Otherwise, set LOC = NULL and LOCP = SAVE.
• Exit.

Deleting a Node by its position

• Algorithm DELETEHL(INFO, LINK, START, AVAIL, ITEM).
• Deletes the first node containing ITEM in a circular header list.
• Calls FINDLOCHL to find ITEM's position.
• If ITEM is not found, report the error.
• Update pointers for deletion.
• Return the freed node to AVAIL.

Inserting in CHL

• The study material provided suggests this is a task to be done by the student.

Application of Linked Lists: Polynomial Representation

• Linked lists are suitable for representing polynomials.
• Example: 10x⁶ + 20x³ + 55.
• Nodes hold coefficient and exponent values.
• A structure example: coef, expon, link – Each node stores the coefficient, exponent, and pointer to the next node.

Polynomial Representation (Example)

• A sample polynomial representation: 2x⁸ – 5x⁷ – 3x² + 4
• The representation is done through a linked list containing a header node 0, -1, 2, 8, -5, 7, -3, 2, 4, 0.