Scribd
Upload
131 views13 pages

Header Linked List Basics

The document discusses header linked lists. A header linked list contains a special node called a header node at the beginning of the list. The header node does not necessarily contain the same type of data as other nodes. There are two types of header linked lists: grounded header lists, where the last node contains a null pointer, and circular header lists, where the last node points back to the header node. Header linked lists are commonly used to store polynomials in memory.

Uploaded by

Ankit Rajput
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
131 views13 pages

Header Linked List Basics

The document discusses header linked lists. A header linked list contains a special node called a header node at the beginning of the list. The header node does not necessarily contain the same type of data as other nodes. There are two types of header linked lists: grounded header lists, where the last node contains a null pointer, and circular header lists, where the last node points back to the header node. Header linked lists are commonly used to store polynomials in memory.

Uploaded by

Ankit Rajput
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 13

Data Structures

Lecture 8: Header Linked List

By
Ravi Kant Sahu
Asst. Professor

Lovely Professional University, Punjab


Outlines
• Introduction
• Header Linked List
• Advantages of Header Linked List
• Types of Header Linked List
• Review Questions

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Header Linked List
 A header linked list which always contains a special
node, called the header node, at the beginning of the
list.

START
Ø

HEADER NODE

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Header Linked List

Name Salary LINK


2 0
START 1
5 59,000 6
2
E 10000 9
3
10 C 4000 7
AVAIL 4
8
5
B 20000 4
6
D 13000 3
7
1
8
F 12000 2
9
5
10
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Advantages of Header Linked List
• Header linked list contains a special node at the top.

• This header node need not represent the same type of data that
succeeding nodes do.

• It can have data like, number of nodes, any other data...

• Header node can access the data of all the nodes in the linked
list.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Types of Header Linked List
 A Grounded header list is a header list where the last node
contains the null pointer.

 A Circular header list is a header list where the last node


points back to the header node.

Note:
• Unless otherwise stated or implied, header list will always be circular
list.
• Accordingly, in such a case, the header node also acts as a sentinel
indicating the end of the list.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
START
Ø

HEADER NODE

Grounded Header List

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
START

HEADER NODE

Circular Header List

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
• If Link [START] = NULL,
then, Grounded Header List is Empty.

• If Link [START] = START,


then, Circular Header List is Empty.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Traversing a Circuar Header List
 Algorithm (Traversing a Circular Header list)

1. Set PTR = LINK [START]. [Initialize pointer PTR]


2. Repeat step 3 and 4 while PTR ≠ START.
3. Apply PROCESS to INFO[PTR].
4. Set PTR = LINK [PTR]. [PTR points to next node]
[End of Step 2 Loop.]
5. EXIT

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Use of Header Linked List
• Header Linked lists are frequently used for maintaining
Polynomials in memory.

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Review Questions
• What is Header Node?

• How a Linked List is different from Header linked list?

• What is Grounded Header list and circular header list?

Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)

You might also like