header, circular and two way linked lists

header, circular and two way linked lists

• 1.
  Header, Circular andTwo-way Linked Lists
• 2.
  Header Linked Lists •Header linked list is a linked list which always contains a special node called the Header Node, at the beginning of the list. • It has two types: a) Grounded Header List Last Node Contains the NULL Pointer. b) Circular Header List Last Node Points Back to the Header Node. 2 Header linked list Grounded Header linked list Circular Header linked list
• 3.
  Grounded Header LinkedList • A grounded header list is a header list where the last node contains the null pointer. • The term “grounded” comes from the fact that many texts use the electrical ground symbol to indicate the null pointer. Header Node Start Figure: Grounded Header Link List
• 4.
  Circular Header LinkedList • A circular header linked list is a header list where the last node points back to the header node. • START always points to the header node. • LINK[START] = NULL means grounded header list is empty. • LINK[START] = START indicates that a circular header list is empty. Header Node Figure: Circular Header Link List Start
• 5.
  Benefits of usingCircular Header List • The null pointer is not used, and hence pointers contain valid addresses. • Every (ordinary) node has a predecessor, so the first node may not require a special case.
• 6.
  Traversing a CircularHeader List Let LIST be a circular header list in memory. This algorithm traverses list, applying an operation PROCESS to each element of LIST. The variable PTR points to the node currently being processed. 1. Set PTR := LINK[START]. [Initializes pointer PTR.] 2. Repeat Steps 3 and 4 while PTR != START. 3. Apply PROCESS to INFO[PTR]. 4. Set PTR := LINK[PTR]. [PTR now points to the next node.] [End of Step 2 loop.] 5. Exit.
• 7.
  Searching in circularheader list SRCHHL(INFO,LINK,START,ITEM,LOC) 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
• 8.
  Two-way lists • Atwo-way list is a linear collection of data elements, called nodes, where each node N is divided into three parts: – Information field – Forward Link which points to the next node – Backward Link which points to the previous node • The starting address or the address of first node is stored in START / FIRST pointer . • Another pointer can be used to traverse list from end. This pointer is called END or LAST.
• 9.
  Two-way lists(cont…) • Everynode (except the last node) contains the address of the next node, and every node (except the first node) contains the address of the previous node. • A two-way list (doubly linked list) can be traversed in either direction.
• 10.
  Representation of Two-way lists Start X4 2 10 Last INFO Field BACK Pointer FORE Pointer X
• 11.
  Inserting • INST(INFO, FORW,BACK, START, LOCA, LOCB, ITEM) 1. Set NEW := AVAIL, AVAIL=FORW[AVAIL]. [Allocate memory to the new node.] 2. 3. INFO[NEW] := ITEM. 4. Set FORW[LOCA] := NEW, FORW[NEW] := LOCB, BACK[LOCB] := NEW, BACK[NEW] := LOCA. 5. Exit.
• 12.
  Deletion DEL(INFO, FORW, BACK,START, LOC) 1. Set FORW[BACK[LOC]] := FORW[LOC], and BACK[FORW[LOC]] := BACK[LOC]. 2. Free memory. FREE[LOC]. 3. Exit.