What are the advantage of header linked list?

Answer 1

Header linked list contains a special node at the top,this header node need not represent the same type of data that succeding nodes do,it can have data like,no. of nodes,any data...

header node can access the data of all your nodes

Answer 2

Header node in linked list is used to keep the address of the first node of the linked so that when some operations are performed on list like insert or delete, it can be done with the reference of header node.

Answer 3

Linked lists maintain a pointer to the first node in the list. A doubly-linked list may also maintain a pointer to the last node in the list. Initially both will be NULL, because the list is initially empty. As a result, the list must handle much of the implementation, because it must ensure nodes actually exist before any operations can be carried out, including the major methods to insert, extract and traverse nodes.

By including a sentinel or dummy node to mark the head of the list, the implementation can be simplified by delegating all the work to the nodes themselves. That is, the nodes can sort themselves out far more easily than the list can, because all nodes are intrinsically the same, and the head node is guaranteed to exist at all times.

For example, suppose we have a singly-linked list and we want the nodes to be automatically sorted as they are inserted (insertion sort). When the list receives data to be inserted, it simply calls the head node's Insert(data) method. It doesn't have to check if the head node exists because the head node always exists, and never changes. The head node knows it is the head node and nothing comes before it, so it calls Next = Next.Insert(data). If the next node is the tail node (as it will be initially), the tail node knows it is the tail node and nothing comes after it, so it create a new node for the data, points it to itself, and returns a pointer to the new node. The head node receives the pointer to the new node and sets its next node to the new node.

It gets more interesting when the second node is inserted. Again, the call is passed to the head node which passes it on to the next node (the node we just inserted). That node knows it is a data node so it performs a comparison with its own data. If the given data is greater or equal, it calls Next = Next.Insert(data), and the tail creates the new node and returns it, just as it did before. However, if it is less, the node instantiates a new node, points it to itself and returns the new node to the head node, which becomes its next node.

Granted, it's a bit of a mouthful to explain, but hopefully you can appreciate just how simple and elegant the algorithm is. No node does more work than it has to and the list itself does absolutely nothing, other than to delegate to the head node. The head node automatically updates its next node, the last node always inserts before it, and the individual data nodes can work out between them where new data will be inserted, updating their links automatically according to the return value.

Note also that, although it is a singly linked list, the calls from one node's Insert(data) method to its next node's method automatically reverses the traversal when a new node is inserted, thus updating the previous node's next pointer, but leaving all others exactly as they were.

Although you could implement this algorithm in a normal linked list (without sentinels) the list must check if the list has any nodes before it can proceed, and if there are no nodes, the list itself must perform the insertion. That being the case, it might as well perform the comparisons as well. But that's a lot of work for an object who's sole concern should be to maintain a pointer to the first node (or a head node!). The problem is the first node may be NULL, which means work that should really be delegated to the nodes (because they have intimate knowledge of each other) must instead be handled by the list, and that's a very definite sign of poor design and inherent inefficiency.