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.


Sample Question:

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

JSR Notes:

(Much more on these topics in the OOP option, but for now...)

Dynamic structures are able to grow and shrink in size in the memory of a computer. This is beneficial in that they do not occupy any more memory than they need to store their data. This is in comparison to arrays, which are a static size, and so even when empty take up all of the memory they were allocated at their creation.

The way dynamic structures are able to change their size dynamically is through the use of nodes and pointers. Each individual part of a dynamic structure, called a node, contains the data as one attribute, but it also contains an attribute called a pointer, which is the memory address of the next part of the dynamic structure. That way all of the nodes of a dynamic structure are able find each other, and can together make up one linked structure.