Header Linked Lists PDF

Header Linked Lists A header linked list is a linked list which always contains a special node called header node, at the beginning of the list. Two kinds of widely used header lists: Grounded header list Circular header list  Grounded header list A header list where the last...

Header Linked Lists A header linked list is a linked list which always contains a special node called header node, at the beginning of the list. Two kinds of widely used header lists: Grounded header list Circular header list  Grounded header list A header list where the last node contains the NULL pointer. The list pointer START always point to the header node START ⋯ Header Node LINK[START]==NULL List is Empty  Circular Header List A header list where the last node points back to the header node. START The list pointer START always point to the header node Header Node ⋯ LINK[START]==START List is Empty Header Linked Lists The first node in a header list is the node following the header node. A header node is an extra node in the list that holds no data but serves to satisfy the requirement that every node has a previous node. Unless otherwise stated or implied, our header lists will always be circular. Accordingly, in such a case, the header node also acts as a sentinel indicating the end of the list. Circular Header list are frequently used instead of ordinary linked list Null pointer are not used, hence all pointer contain valid addresses Every node has a predecessor, so the first node may not require a special case. Traversing a Circular Header List TRAVCHL(INFO, LINK, START) Let LIST be a circular header list in memory. This algorithm traverse LIST, applying an operation PROCESS to each node of LIST. 1. Set PTR = LINK[START] 2. Repeat Steps 3 and 4 while PTR ≠ START 3. Apply PROCESS to INFO[PTR] 4. Set PTR = LINK[PTR] 5. Exit Locating an ITEM SRCHL(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 1. Set PTR = LINK[START] 2. Repeat while INFO[PTR] ≠ ITEM and PTR ≠ START Set PTR = LINK[PTR] 3. If INFO[PTR] == ITEM then Set LOC = PTR Else Set LOC = NULL 4. Exit Deleting the first node containing ITEM in CHL FINDLOCHL(INFO, LINK, START, ITEM, LOC, LOCP) This algorithm finds the location LOC of the first node N which contains ITEM and the location LOCP of the predecessor node of N. If ITEM does not appear in the list then LOC = NULL 1. Set SAVE = START and PTR = LINK[START] 2. Repeat while INFO[PTR] ≠ ITEM and PTR ≠ START Set SAVE = PTR and PTR = LINK[PTR] 3. If INFO[PTR] == ITEM then Set LOC = PTR and LOCP = SAVE Else Set LOC = NULL and LOCP = SAVE 4. Exit Deleting the first node containing ITEM in CHL DELETEHL(INFO, LINK, START, AVAIL, ITEM) This algorithm deletes list the first node N which contains the information ITEM 1. Call FINDLOCHL(INFO, LINK, START, ITEM, LOC, LOCP) 2. If LOC == NULL then Write ITEM is not in the list and Exit 3. Set LINK[LOCP] = LINK[LOC] 4. Set LINK[LOC] = AVAIL and AVAIL = LOC 5. Exit. Inserting in CHL Try yourself Application of Linked Lists: Polynomial representation Polynomial Representation and operation on Polynomials Ex: 10x6 +20x3 + 55  Polynomial representation p(x) = 2x8 – 5x7 – 3x2 + 4 POLY Coefficient Exponent Header Node 0 -1 2 8 -5 7 -3 2 4 0