Identify the features of the abstract data type (ADT) list.


Teaching Note:

Students should understand the nature of an ADT—where no implementation details are known but the actions/methods are standard.


Sample Question:


JSR Notes:

This was covered in Topic 5 in an algorithmic way, but it applies here too:

5.1.11 Describe the features and characteristics of a dynamic data structure

5.1.12 Describe how linked lists operate logically.

5.1.13 Sketch linked lists (single, double and circular). Straight-forward, good exam question

But in terms of this assessment statement the way it's phrased, here are the features of lists:

- The ADT list uses self referential Node objects to link up with each other, thus creating a chain of Nodes.

- Access to the chain, or the list, is from one end only, but with this access, since all nodes are linked, any node can be found by going from node to node until the one searched for is found (or not, if it is not there).

- Lists therefore have an efficiency, expressed in Big O of Big O n.

- 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; these are all accomplished though re-direction of the node's "pointers" (the part of each node that knows the address of the next node in the list).