Грокаем структуры данных

Notice that there are no methods to remove or search elements. These two operations would normally be expected in a container, so bags are kind of borderline—a container with restrictions.
<…>
This is the same for a bag data structure: to compute statistics about the content of a bag (say, a set of marbles, or our daily orders),
<…>
—all those statistics where the order doesn’t matter, like daily total or daily breakdown by type.
<…>
a bag becomes a special variant of a list, implementing only a subset of its instructions. It means that we can use any implementation of the list ADT
<…>
So, the best option to implement a Bag class seems to be using a singly linked list to store the elements—we don’t need a doubly linked list because we won’t be deleting elements, nor will we need to traverse the list from tail to head.
<…>
The Bag class is just a wrapper around the linked list with the elements. We need this wrapper because we want the Bag class to have only two public methods with which clients can interact:

when it comes to finding the predecessor of a node N in the whole tree, <…>:
•If N has a left subtree, then yes, its predecessor is the maximum of that subtree.
•If N does not have a left subtree and it’s a right child, then its parent is also its predecessor.
•If N does not have a left subtree and it’s a left child, we have to climb up the tree until we find node M that is a right child—its parent is the predecessor of N.
•If we reach the root before finding such a node, then it means that N is the minimum of the tree, and it has no predecessor.