Write a note on header linked list. Explain the widely used header lists with diagrams

HEADER LINKED LISTS

A header linked list is a linked list which contains a special node, called the header node, at the
beginning of the list.
The following are two kinds of widely used header lists:

1. A grounded header list is a header list where the last node contains the null pointer.
2. A circular header list is a header list where the last node points back to the header node.
   Below figure contains schematic diagrams of these header lists.

Observe that the list pointer START always points to the header node.

• If START→LINK = NULL indicates that a grounded header list is empty
• If START→LINK = START indicates that a circular header list is empty.

The first node in a header list is the node following the header node, and the location of the first node is START→LINK, not START, as with ordinary linked lists.

Below algorithm, which uses a pointer variable PTR to traverse a circular header list

1.Begins with PTR = START→LINK (not PTR = START)

2.Ends when PTR = START (not PTR = NULL)

Algorithm: (Traversing a Circular Header List) Let LIST be a circular header list in memory.

This algorithm traverses LIST, applying an operation PROCESS to each node of LIST.

• Set PTR: = START→LINK. [Initializes the pointer PTR.]
• Repeat Steps 3 and 4 while PTR ≠ START:
• Apply PROCESS to PTR→INFO.
• Set PTR: = PTR→LINK. [PTR now points to the next node.] [End of Step 2 loop.]
• Exit.
  

Algorithm: SRCHHL (INFO, LINK, START, ITEM, LOC)

LIST is a circular header list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST or sets LOC = NULL.

• Set PTR: = START→LINK
• Repeat while PTR→INFO [PTR] ≠ ITEM and PTR ≠ START: Set PTR: =PTR→LINK.
  [PTR now points to the next node.] [End of loop.]
• If PTR→INFO = ITEM, then:
  Set LOC: = PTR.
  Else:
  Set LOC: = NULL.
  [End of If structure.]
• Exit.

The two properties of circular header lists:

• The null pointer is not used, and hence all pointers contain validaddresses.
• Every (ordinary) node has a predecessor, so the first node may not require a special case.

There are two other variations of linked lists

• A linked list whose last node points back to the first node instead of containing the null pointer, called a circular list.
• A linked list which contains both a special header node at the beginning of the list and a special trailer node at the end of the list.