Sample Question:

From Sample Paper 1 2014: (continued from the 2d array question started on 5.1.5)

JSR Notes:

The story so far... and the story to come

At this point in the story, you now have an awareness of dynamic data structures, and their main advantage of memory conservation. And you also have a general awareness of the basic mechanism used to connect/link lists together - namely nodes with self-referential pointers. So the next step that we can look at here is how, generally, we take advantage of these dynamic capabilities, specifically with a linked list.

Though, BTW, there are still more details so come, for example with the Option D list topics, and also 5.1.7 and its video, but for now if you were asked in a sentence or two to describe what lists are and how they logically operate, this is what follows.

Lists & Trees

Lists are one of the two main categories of dynamic ADTs; there are lists and there are trees. We'll get to trees a little later on. Lists are collections of nodes which contain both data and a pointer to the next node. Because they do not have to occupy contiguous locations in memory, as arrays do, they are able to be dynamic structures, meaning, unlike an arrays, they can grow and shrink in size.

How Lists Fundamentally Operate

"The tools":

Each list is made up of a series of linked nodes. As we have seen, each individual node has two main parts, its associated data (so for example the specific details of a specific student), plus a single "pointer" attributed, which is a node of the same type as the node itself. (Keep in mind that a node is an object/reference type, and a reference type is, literally, an address reference.)

"The process":

- Lists have a "head node" which gives access to the list. (And some ADT lists, maintain access to the "tail", too).

- Access to all other nodes is via the head through a series of links from the head to the next node, from that node to the next, and so on and so on.

- Each node knows where the next node in the list is located, via storing that node, i.e. that node's object reference (the memory address of that next node) as the pointer.

- The end of the list is reached when the pointer of one of the nodes is null.

 

Diagraming this:

The diagrams below use the same way of depicting nodes, with their data and pointers, as appeared in the 2014 sample paper marking scheme (see above).