Home OOP HL Last Next


Construct algorithms using a static implementation of a list.


Teaching Note:

Lists will be restricted to singly linked types. Methods that should be known are add (head and tail), insert (in order), delete, list, isEmpty, isFull.


Sample Question:


JSR Notes:

List ADT C.: Coding List as Static Arrays

A Repeat here in the Option at a Deeper Level

A lot of this you have recently seen in Topic 5. Remember that for Topic 5, it is to a level of diagramatic understanding, but with the OOP Option Extension, it will be to an algorithmic, coding level (next assessment statement). But.... for this assessment statement, see the "Beyond what is needed" note below.

Topic 5.1.10 (green below indicates diagrams that apply to the methods mentioned here)

5.1.10 Array as Static Stack at a diagramatic level diagrams:

5.1.10 Array as Static Queue at a diagramatic level diagrams:

And here (D.4.9) - Array as Static Stack & Queue at an algoritmic/coding level, from the Teaching Note:

When reproducing algorithms, do make sure you remember the importance if isFull( ) when trying to add to add or insert to lists made from arrays.

Beyond what is needed

This is in all likelihood going beyond what we need to cover. And, the Topic 5.1.10 notes do a very good job at describing several of the methods mentioned here anyway.

And furthermore, the focus for lists (i.e. most often, stacks and queues) should be on dynamic implementations, not static ones. Yes, you can make static implementations of lists, using the array structure, but the main point to lists is that they can indeed be dynamic. If you understand the general approach (from 5.1.10), then on the off chance of a question to get you to code these, you should be able to problem-solve your way to an adequate respones. But again, here, now, it's not worth the likelihood of that happening to spend time on it.

Never-the-less, for what it's worth, here is a link to a static implementation of a list, in Java. And from another example, here is a taste of the code. It's a good little method to look at because you can see how the array structure is working. We are just "appending" (i.e. pushing) our object to the next element to be populated. And the one check that is dones first is to make sure that the listSize at this point is not greater than the maxSize, i.e. the size of the array.

  // Append "obj" to list
  public boolean append(Object obj) {
    if (listSize >= maxSize) return false;
    listArray[listSize++] = obj;
    return true;

The next assessment statement is list algorithms using object references, so with that, I"ll go into the full details.