Clever Geek Handbook

What are the performance benefits of storing a head node without data in a linked list?

What are the performance benefits of storing a head node with wasted data in a linked list?

I've read some implementation of linked list operations using the head node, which only stores a pointer to the first node (the data in the head node is useless).

But I cannot determine even one advantage of using a head node instead of a head pointer.

Can someone please clarify the issue with 1 issue and 2 implementations, one with a head node and another with a head pointer and a performance / complexity tradeoff?

+3


source to share


2 answers


For these reasons, empty space header nodes are used:

  • To satisfy the requirement that each node has a previous node (simplifies / unifies methods)
  • Do not deal with special cases of insertion and removal from the head. It looks like any other node


Other than that, no, they do not provide any performance / memory advantage.

+7


source


Among other things, another benefit is that you can keep the number of currently available nodes in the linked list, as nodes are added and removed frequently, so you keep a very close eye on the number of nodes in the head of a linked list node.



+1


source






More articles:


All Articles