a stackIn order to extract the maximum reuse benefit of our writing a specific program, we try to factor out common elements between classes. This process is often called abstraction.
One major source for abstraction are classes that deal with collections of other classes. These classes are called container classes. These classes to not deal with the contained objects themselves, but rather with operations like:
A different distinction can be made according to the access methods used to manipulate objects in the container. This yields (again, see [Booch], Ch.9):
Next Section |
Previous Section
Arrays
An array is both the simplest and the oldest container class. You take
your objects and simply line them up.
The array is by nature a bounded container. If your array is full, that that was it.
Adding elements to an array is easy as long as you add them at the beginning or at the end. Arrays are therefore very suitable to implement stacks, rings, decks and queues.
a stack
a deck, queue or ring
On the other hand, inserting elements in the middle of an array is fairly costly. You have to shift a lot of elements.
Accessing an element is blazingly fast. Most processors do it with one machine instruction. The boundedness of arrays means that the storage allocated remains fixed. If the array overflows, then this can be detected. Arrays are the prime choice for time critical or mission critical applications where failures can be costly.
Next Section |
Previous Section
Linked Lists
The linked list is practically the opposite of an array. Operations
that are hard to do on an array are trivial on a linked list:
inserting
deleting
On the other hand, Linked lists are unbounded. Care has to be taken when allocating and freeing memory. Bugs in this process lead to memory leaks, which are often hard to detect and to isolate.
The concept of arrays and linked lists can be combined into a hybrid container. This is basically equivalent to writing your own memory manager.
Previous Section |
Contents
Application to our Monopoly Engine
When analysing the kinds of collections used in the monopoly project,
one tends towards using arrays. The number of objects is limited, and the
access is well defined.
On the other hand, looking closely reveals that we do not have collections of identical objects. The objects are similar enough to be derived from the same base class, but still are too different to be stored in an array - which requires all objects to be eactly the same size.
Linked lists do not care about the size of the objects. As long as every object has a link to it's neighbors, it works:
Of course, you can also implement heterogenous arrays by using arrays of pointers, like this:
It is arguable which structure suits the project better. Probably, arrays have a slight edge. I chose to use linked lists because in general, you will need dynamic structures more often, and it pays to learn how to make them.
Another advantage of linked lists is that we can implement it in a very symetric way. Since a some of our collections will be loops (the spaces on the board, the players), we do not have to worry about "wrapping" over at the end of the array. This is what it will look like in the monopoly project:
Here we link the last element to the first, and our links go both ways. Insertions and deletions are totally symetric operations. We check to see if we are at the last element by checking if it's successor is the first element, which is also the element pointed at by the List object.
Note the way the two pointers are added via inheritance.