Home Topic 5 Last Next

Linked lists

Linked lists will be examined at the level of diagrams and descriptions. Students are not expected to construct linked list algorithms using pseudocode.


Describe the features and characteristics of a dynamic data structure.


Teaching Note:

Students should understand the concepts of nodes and pointer.


JSR Notes:


Feature & Characteristic of dynamic data structures # 1 - they are dynamic:

Dynamic, not Static

Recall that a dynamic data structure is one in which it can grow or shrink in size. Lists and trees are examples of dynamic structures.

The programming term, which describes the opposite of a dynamic structure -i.e. a data structure that cannot change size - is static. So in terms of data structures, static means non changeable size, and dynamic means changeable size.

Remember, don't get confused with the other general programming usage of the word static; in other contexts, static means only one copy. So any static method, such as public static void main, cannot have a second copy of it made; there can be one and only one main method in the same class. This is opposed to methods and variables that are part of template classes; multiple copies of, for example, the Student constructor, and name instance variable, and getName( ) accessor method can be made - so we can say that they are all non-static.

But back to this sense of the word, static means not able to change size. The array data structure is the primary static, i.e. non-dynamic, data structure in Java. And dynamic data structures can change size.


Feature & Characteristic of dynamic data structures # 2 - they don't waste memory:

Main Advantage of Dynamic Structures: don't waste memory

As will be gone into more detail in coming assessment statements, there are distinct advantages to dynamic data structures, and disadvantages also. For now, note that the main advantage of dynamic data structures is that since they can change size, they do not waste memory. If a dynamic data structure holds, for example,182 things, it only takes up just enough computer memory (RAM) to accommodate those 182 things.

Meantime arrays often waste memory by having many elements that are unused. Arrays are static in size, and so even when completely empty, they take up all of the memory they were allocated at their creation.


Feature & Characteristic of dynamic data structures # 3 - they use of nodes & pointers:

Nodes & Pointers For Linking

At this point, you have to wait for the "full story" of how nodes and pointers work until after you learn about referential classes (which, if doing the OOP Option, is done to a good level in D.4.5, and D.4.6), and also the following Topic 5 assessment statement, 5.1.12. But it is here that two crucial terms are introduced: Nodes, and Pointers.

And, generally, the way that dynamic structures are able to change their size dynamically is through the use of nodes and pointers.


Each individual part of a dynamic structure, is called a node, and it contains two general parts:


So the pointer, as an object reference type, is, at a literal level, an address. And it can therefore act as the directions to the next node in a chain, or list of similar nodes.

In this way, all of the nodes of a dynamic structure are able find each other, and can together make up one linked structure.