Home Topic 5 Last Next (D.4.5)

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:

Preview summary of features and characteristics of dynamic data structures:


Feature # 1 of dynamic data structures:
Dynamic, not Static

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

Meantime, the programming term, which describes the opposite of a dynamic structure - i.e. a data structure that cannot change size - is static. The array data structure is the primary static data structure in Java.

The Java abstract data structures (ADTs) lists and trees are dynamic data structures, so they are ones that can change size.


Feature # 2:
They 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. As mentioned in a previous assessment statement, 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 do 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.


Characteristic # 1 of dyanmic data structures:
Nodes, which are made of payload & pointer

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, you'll find in D.4.5, and D.4.6, and also 5.1.12. But it is here, that two crucial terms are introduced: Nodes, and Pointers.

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

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


Characteristic # 2:
Pointers, in order to link nodes

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.


(Repeat of) Features and characteristics of dynamic data structures: