|3.7 Dynamic Lists|
Up until now, we've considered only lists whose contents are fixed and unchanging, that is, static (see static) lists. But in real programs, many lists are dynamic (see dynamic), with their contents changing rapidly and unpredictably. For the case of dynamic lists, we need to reconsider some of the attributes of the types of lists that we've examined.1
Specifically, we want to know how long it takes to insert a new element into a list and to remove an existing element from a list. Think about it for each type of list examined so far:
Removing an item from the list is almost as simple. If the item to
delete happens to be located at the very end of the array, just reduce
the size of the list by one. If it's located at any other spot, you must
also copy the element that is located at the very end onto the location
that the deleted element used to occupy.
Clearly, binary search trees are superior to ordered or unordered arrays in situations that require insertion and deletion in random positions. But insertion and deletion operations in binary search trees require a bit of explanation if you've never seen them before. This is what the next chapter is for, so read on.