listsstacksand queues in considering the designwe will need to provide four classes the list class itselfwhich contains links to both endsthe size of the listand host of methods the node classwhich is likely to be private nested class node contains the data and pointers to the previous and next nodesalong with appropriate constructors the const_iterator classwhich abstracts the notion of positionand is public nested class the const_iterator stores pointer to "currentnodeand provides implementation of the basic iterator operationsall in the form of overloaded operators such as ===!=and + the iterator classwhich abstracts the notion of positionand is public nested class the iterator has the same functionality as const_iteratorexcept that operatorreturns reference to the item being viewedrather than constant reference to the item an important technical issue is that an iterator can be used in any routine that requires const_iteratorbut not vice versa in other wordsiterator is- const_iterator because the iterator classes store pointer to the "current node,and the end marker is valid positionit makes sense to create an extra node at the end of the list to represent the endmarker furtherwe can create an extra node at the front of the listlogically representing the beginning marker these extra nodes are sometimes known as sentinel nodesspecificallythe node at the front is sometimes known as header nodeand the node at the end is sometimes known as tail node the advantage of using these extra nodes is that they greatly simplify the coding by removing host of special cases for instanceif we do not use header nodethen removing the first node becomes special casebecause we must reset the list' link to the first node during the remove and because the remove algorithm in general needs to access the node prior to the node being removed (and without header nodethe first node does not have node prior to itfigure shows doubly linked list with header and tail nodes figure shows an empty list figure and figure show the outline and partial implementation of the list class we can see at line the beginning of the declaration of the private nested node class rather than using the class keywordwe use struct in ++the struct is relic from the programming language struct in +is essentially class in which the members default to public recall that in classthe members default to private clearly the struct head tail figure doubly linked list with header and tail nodes