listsstacksand queues figure insertion into linked list first last figure doubly linked list the special case of adding at the end ( making the new item the last itemcan be constant-timeas long as we maintain link to the last node thusa typical linked list keeps links to both ends of the list removing the last item is trickierbecause we have to find the next-to-last itemchange its next link to nullptrand then update the link that maintains the last node in the classic linked listwhere each node stores link to its next nodehaving link to the last node provides no information about the next-to-last node the obvious idea of maintaining third link to the next-to-last node doesn' workbecause it too would need to be updated during remove insteadwe have every node maintain link to its previous node in the list this is shown in figure and is known as doubly linked list vector and list in the stl the +language includesin its libraryan implementation of common data structures this part of the language is popularly known as the standard template library (stlthe list adt is one of the data structures implemented in the stl we will see some others in and in generalthese data structures are called collections or containers there are two popular implementations of the list adt the vector provides growable array implementation of the list adt the advantage of using the vector is that it is indexable in constant time the disadvantage is that insertion of new items and removal of existing items is expensiveunless the changes are made at the end of the vector the list provides doubly linked list implementation of the list adt the advantage of using the