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.¹

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:

Unordered array

Adding items to the list is easy and fast, unless the array grows too large for the block and has to be copied into a new area of memory. Just copy the new item to the end of the list and increase the size by one.

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.

Ordered array

In terms of inserting and removing elements, ordered arrays are mechanically the same as unordered arrays. The difference is that insertions and deletions can only be at one end of the array if the item in question is the largest or smallest in the list. The practical upshot is that dynamic ordered arrays are only efficient if items are added and removed in sorted order.

Binary search tree

Insertions and deletions are where binary search trees have their chance to shine. Insertions and deletions are efficient in binary search trees whether they're made at the beginning, middle, or end of the lists.

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.