[go: up one dir, main page]
Scribd
Upload
896 views13 pages

Header Linked List

A header linked list contains a special node called the header node at the beginning of the list that does not represent the same data type as other nodes, with advantages including accessing all node data and types including grounded lists where the last node points to null and circular lists where the last node points to the header node again. Header linked lists are commonly used to store polynomials in memory with the header node traversing the list.

Uploaded by

Sai Karthik
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
896 views13 pages

Header Linked List

A header linked list contains a special node called the header node at the beginning of the list that does not represent the same data type as other nodes, with advantages including accessing all node data and types including grounded lists where the last node points to null and circular lists where the last node points to the header node again. Header linked lists are commonly used to store polynomials in memory with the header node traversing the list.

Uploaded by

Sai Karthik
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: Header Linked List

By
Arvind Kumar
Asst. Professor

Lovely Professional University, Punjab


Outlines
• Introduction
• Header Linked List
• Advantages of Header Linked List
• Types of Header Linked List
• Review Questions
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
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
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.
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.
START
Ø

HEADER NODE

Grounded Header List


START

HEADER NODE

Circular Header List


• If Link [START] = NULL,
then, Grounded Header List is Empty.

• If Link [START] = START,


then, Circular Header List is Empty.
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
Use of Header Linked List
• Header Linked lists are frequently used for maintaining
Polynomials in memory.
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?

You might also like