Logout

Home OOP HL Last Next

D.4.9

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:

sdfsdfsf

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 is to an algorithmic, coding level. But.... for this assessment statement, see the note below.

5.1.10

Array as Static Stack at a diagramatic level:

Array as Static Queue at a diagramatic level:

And here - Array as Static Stack & Queue at an algoritmic/coding level

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.

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

Never-the-less, for what it's worth, here is a link to a static implementation of a list, in Java. And from that, 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 firs 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.