Sample Question:

sdfsdfsf

JSR Notes:

List ADT A.: Features

ADTs at a Programming vs. a Usage Level

Before going into the features and applications of the list ADT, it is important to focus in on the Teaching Note. It points out that with all ADTs we don't necessarily need to know how they were implemented (i.e. coded) to use them. We just need to recognize their standard methods/actions, and know how they should work. And what is this an example of??? Our old friend abstraction, again!

In fact, for IB CS, you need to be able to work with ADTs on both levels:

1. Algorithmic construction of lists and trees
   • In Topic 5, that was limited to diagrams
   • Here in the OOP Extension includes is actual Java code implementations
2. But also - as focused on here - simply how to apply them

The Features & Application of ADTs

"Simply" applying ADT is, in fact fairly straight-forward, but it still has to be learned, and it is based on what a certain ADT can do; i.e. its features.

A good example here, which we already have experience with, is classes which specialize in doing user input and output. To you, by now, it is obvious how we apply the Scanner and/or BufferedReader classes. When we go Scanner s = new Scanner( ), and then go s. and see the list of functions that comes up, we are pretty familiar with some of the functional capabilities of Scanner. But, in fact, there are many more that we are not familiar with.

Whether or not we know all of the ways an ADT can be applied, it is the general features of classes like BufferedReader and Scanner which, in the first place, lead to what they can do; how they can be applied.

What are the general features of BufferedReader and Scanner? Well, they can take in streams of input from various sources, including the keyboard. And, in the case of BufferedReader, an additional feature is that it can store up input one piece at a time, in a "buffer", and then process that input all at once in a batch way. That makes it really efficient. Scanner lacks that capability, but a very useful feature is that it has ways to, by itself, parse input data types other than String, such as int and boolean.

 

Understanding Features of the ADT List before we can apply it

So before we can see a bunch of specific methods to use from a List class (as in the picture above for the Scanner class), we need to fully appreciate the general features of lists. A lot of this was covered various places in Topic 5.

Features Shared with other Dynamic Structures

The features that ADT List has starts with the fact that lists are dynamic data structures, as opposed to their static counterparts, namely the Java array. The features of dynamic data structures in general (as seen in 5.1.1 - and do be sure to look at the details there) are:

- They are dynamic, not static; i.e. they can grow and shrink in size.

- They are made up of nodes, which are self-referential types, composed of the data itself, and a pointer to the next node.

- Because they are dynamic, they do not waste memory; they only take up as much memory as is the number of nodes in the list

Further Features of Lists

- Access to the chain, or the list, is from one end only.

- This beginning node is usually identified as Head (or first). The last node in the chain is usually identified as the Tail (or last).

- With access to the Head, since all nodes are linked, any node can be found by going from node to node until the one searched for is located (or not, if it is not there).

- Lists therefore have a searching efficiency which is directly proportional to their size; not a bad efficiency, but not as good as other structures.
(This efficiency can expressed in what computer scientist usually use to measure relative efficiency, "Big O". Lists have a Big O of Big On, with n being the number of nodes in the structure.)

- Specific algorithms can be implemented to add to the list, at either end, to effectively delete nodes from the list, or to add additional nodes at any point along the chain (accomplished though re-direction of the nodes' "pointers").