algorithmsingly-linked-list

Which of these implementations is canonical: storing the head and size variables, or storing the head, tail, and size?

For a singly linked list, should I store the head and size variables, or the head, tail, and size?

Solution

  • Only the head field is a canonical. You can trivially implement getSize() and getTailNode() methods with only the head node available.

    Storing size and tail as fields is optional, they are not a fundamental part of the "linked list" concept. Having them does benefit the complexity of certain operations though, at the cost of having to store and correctly update them.