forward list question, tail node?

[DonnaPin]

I am reading an stl book about forward lists. I understand that they are implemented using a singly linked list. the book says " The anchor of a forward list has no pointer to the last element. For this reason, a forward list does
not provide the special member functions to deal with the last element, back(), push_back(), and pop_back()."

Does this mean it doesnt have, what would normally be the tail node? And if so does that mean all singly linked lists do not have tail nodes, or is that just specific to forward_list?

[keskiverto]

Depends what you mean by "tail node". I would assume that tail node is the last node in a non-empty list. Therefore, only empty list would not have a tail node.

What you more likely mean is a pointer to last node.

class List {
  Node* head; // points to first node of the list
  Node* tail; // points to last node of the list
  // ...
};

The tail pointer makes it trivial to reach the last node.

The forward_list does not have that pointer:

class Forward {
  Node* head; // points to first node of the list
  // ...
};

You can still get to the last, "tail" node, but only by iterating through the list. Therefore, it is more complex.

Whether there is tail pointer is up to the writer of the list. forward_list chose to not have it. Some other singly-linked lists do have it.

[George P]

A std::forward_list does have a tail node, the last node in a populated forward list. You can't access it as you can in a std::list. There are no member functions defined that allow access to the tail node.*

https://daveparillo.github.io/intermediate-cpp/containers/sequence-containers.html


*Using iterators (std::forward_list::end) you potentially could access the last/tail node directly using "pointer math.

[keskiverto]

@Furry Guy: Forward iterators do not have operator-

[George P]

So the potential is an impossibility. Got it.