OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 8

40 marks · Hard difficulty · Extended Response

Describe linked list data structures, implement OOP methods for node and linkedList classes, design an algorithm to traverse, add, and remove nodes, identify computational methods, and evaluate OOP versus 2D array implementations in a 12-mark essay.

Practise this question

Question

Question text

8 A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

(a) Describe the features of a linked list data structure.

… [3]

(b) The class design for node is shown here.

attributes:

private value : integer

private nextNode : node

methods:

new()

getValue()

getNextNode()

setValue()

setNextNode()

new() is the constructor method. The constructor method takes a parameter and assigns this to

the value attribute.

(i) The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

… [2]

(ii) The method setValue() takes an integer as a parameter and assigns this to the attribute value.

Write the method setValue() using pseudocode or program code.

… [3]

attributes:

private headNode : node

methods:

new()

insertNode()

outputList()

new() is the constructor method. The constructor initialises the attribute headNode to a null

value.

(i) Write the constructor method using pseudocode or program code.

… [2]

The class design for node and linkedList are shown again here for your reference.

attributes: attributes:

private value : integer private headNode : node

private nextNode : node

methods:

methods: new()

new() insertNode()

getValue() outputList()

getNextNode()

setValue()

setNextNode()

(ii) The method getValue() will return the value of a node. The method getNextNode() will

return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method

joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

function outputList()

returnValue = ""

start = …

while start … null

returnValue = returnValue + start … () + " "

start = start … ()

endwhile

return …

endfunction

[5]

(d) The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it

into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the

linked list.

The program needs to store the following data items in the linked list in the order they are given:

10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

… [5]

(e) A new method is needed to remove a node from the linked list. The method needs to take the

data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in

the method to remove the correct node.

… [5]

(f) The program developer made use of computational methods when designing the object-oriented

programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

1 …

2 …

3 …

[3]

(g)* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the

data and the second element stores the index of the next data item. Array elements not currently

used are also linked together to form a chain of empty values to identify where the next data item

can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list. [12]

Mark scheme

Show the mark scheme

Question Answer Mark Guidance

8 (a) 1 mark each to max 3 3 Accept other valid features such as linked

lists are mutable, a tail pointer can be used to

• A start/head pointer pointing to the first node in the list keep track of the tail of the list, nodes can be

• Each node contains a data item and a pointer to the deleted at any position in the list.

next node

• Data can only be accessed following the pointer to the

next node

• The last node has a null pointer to indicate the end of

the list

• It is a dynamic structure

• Allows data to be prepended, appended or inserted at

any position

• Data accessed in the order they are located in the list

• Data items cannot be directly accessed/indexed

8 (b) (i) 1 mark each to max 2 2 Allow coded solutions.

• Method header getNextNode with no parameters

• Returns attribute nextNode Must return class attribute nextNode, do not

allow an input or over-written value

e.g.

function getNextNode()

return nextNode

endfunction

8 (b) (ii) 1 mark each to max 3 3 Allow coded solutions

• Method header setValue

• …taking one parameter

• Assigning parameter to attribute value

e.g.

procedure setValue(newValue)

value = newValue

endprocedure

8 (c) (i) 1 mark each 2 Allow coded solutions

• Constructor header taking no parameter

• Assigning an appropriate null/none value to headNode Appropriate null values do not include

integers – the list stores integers.

e.g.

procedure new()

headNode = null

endprocedure

8 (c) (ii) 1 mark for each completed statement to max 5 5 Exact answers only, do not accept incorrectly

formed relational operators such as =!

function outputList() Instead of !=

returnValue = "" Accept <> instead of !=

Accept self.__headNode if Python has been

start = headNode used

while start != null

returnValue = returnValue +

start.getValue() + " "

start = start.getNextNode()

endwhile

return returnValue

endfunction

8 (d) 1 mark each to max 5 5 Allow createList = linkedList() for

instantiation or other valid program syntax

• Creation of new object of type linkedList assigned to a

variable 25

• Using insertNode to correctly insert each node…

• … with all 3 data values inserted in correct order

• Calling outputList for the object …

• …and outputting the return value

e.g.

createList = new linkedList()

createList.insertNode(10)

createList.insertNode(25)

createList.insertNode(39)

print(createList.outputList())

8 (e) 1 mark each to max 5 5 For BP4 allow nodes traversed until item

found/end of list

• Description of accessing node at head pointer

• …and comparing to the parameter

• If it is not equal, accessing node head pointer points to

• Repeated steps until found or until end of list

• When node to delete is found the pointer of previous

node should be set to point at next node

8 (f) 1 mark each e.g. 3 Allow alternatives such as pattern matching;

algorithmic thinking; automation; logical

• Problem recognition reasoning

• Problem decomposition

• Abstraction Allow thinking abstractly, thinking ahead,

• Backtracking thinking procedurally, thinking logically,

• Data mining thinking concurrently.

• Heuristics

• Performance modelling Allow OOP modelling techniques such as

inheritance, polymorphism etc.

• Pipelining

• Visualisation

Do not accept programming constructs such

as sequence, selection and iteration.

8 (g) Mark Band 3 – High level 12 Answers may include, but are not limited to,

(9-12 marks) some of the points below:

The candidate demonstrates a thorough knowledge and AO1: Knowledge

understanding of OOP and arrays; the material is generally

accurate and detailed. • OOP allows any number of elements

• …new object created each time

The candidate is able to apply their knowledge and • ...do not need to declare number of

understanding directly and consistently to the context provided. elements

Evidence/examples will be explicitly relevant to the • Array need to know number of elements

explanation. • OOP can be reused in other programs for

other lists without having to make

The candidate provides a thorough discussion which is well significant changes

balanced. Evaluative comments are consistently relevant and • Array would need more changes for other

well-considered. programs such as size of array

• Array needs a way to indicate which

There is a well-developed line of reasoning which is clear and27 elements have been used and which are

logically structured. The information presented is relevant and empty

substantiated.

AO2: Application

Mark Band 2 – Mid level

(5-8 marks) • OOP allow use of dynamic memory

• …can work for any number of elements

The candidate demonstrates reasonable knowledge and • …do not need to know before hand

understanding of OOP and arrays; the material is generally • Array has static memory allocation

accurate but at times underdeveloped. • …need to know maximum number

• …memory wastage if not all used

The candidate is able to apply their knowledge and • …can run out of memory

understanding directly to the context provided although one or • Array can be more complicated to assign

two opportunities are missed. new elements as use of free list is needed

to identify/track where data can be stored

Evidence/examples are for the most part implicitly relevant to

the explanation.

The candidate provides a reasonable discussion, the majority AO3: Evaluation

of which is focused. Evaluative comments are, for the most

part appropriate, although one or two opportunities for • Allow either approach as long as justified

development are missed. E.g. OOP is more appropriate because a

linked list would only need to be created once

There is a line of reasoning presented with some structure. as a class and can then be used in other

The information presented is in the most part relevant and programs with small adaptations. It is a more

supported by some evidence. efficient use of memory because a node is

created when needed and deleted when not

Mark Band 1 – Low Level needed so space in memory does not need

(1-4 marks) to be reserved.

The candidate demonstrates a basic knowledge of OOP and

arrays with limited understanding shown; the material is basic

and contains some inaccuracies. The candidates makes a

limited attempt to apply acquired knowledge and understanding

to the context provided.

The candidate provides a limited discussion which is narrow in

focus. Judgements if made are weak and unsubstantiated.

The information is basic and comunicated in an unstructured

way. The information is supported by limited evidence and the

relationship to the evidence may not be clear.

0 marks

No attempt to answer the question or response is not worthy of

credit.

How to answer it

Linked Lists: OOP Implementation, Traversal & Evaluation

📋 What this question tests

This question assesses key Object-Oriented Programming (OOP) concepts and dynamic data structures: defining class attributes/methods (getters, setters, constructors), writing linked list traversal and modification logic, manipulating pointers during node deletion, recalling computational methods, and evaluating OOP dynamic implementations against 2D static array implementations (12-mark extended response).

Part (a) — Features of a Linked List

Describing key structural characteristics [3 Marks]

✅ Mark Scheme Points (Any 3)

Contains a start / head pointer pointing to the first node.
Each node contains a data item and a pointer to the next node.
Data is accessed sequentially following pointers (no direct/indexed random access).
The last node contains a null pointer indicating the end of the list.
It is a dynamic data structure (can grow or shrink in size during execution).
Nodes can be easily inserted, appended, or deleted without shifting other elements.

🧠 Exam Technique

Always state what each node contains (data + next pointer) and identify the special pointers (head pointer and terminating null pointer). Mentioning that it is dynamic or lacks direct index-based access provides an easy third mark.

❌ Common Errors

Vague statements like "it connects data together" without specifying pointers or nodes.
Confusing a linked list with an array by claiming elements are accessed directly by index.

Part (b) — Implementing Node Class Methods

Writing Getters and Setters [5 Marks Total]

(i) Getter: getNextNode() [2 Marks]

✅ Model Solution

function getNextNode() return nextNode endfunction

Mark Breakdown:
• [1] Method header named getNextNode with no parameters.
• [1] Returning the class attribute nextNode .

❌ Common Errors

Passing a parameter into a getter (e.g. getNextNode(node) ). Getters take no arguments.
Overwriting or reading into the attribute instead of returning it.

(ii) Setter: setValue() [3 Marks]

✅ Model Solution

procedure setValue(newValue) value = newValue endprocedure

Mark Breakdown:
• [1] Method header named setValue .
• [1] Accepting exactly one parameter (e.g., newValue ).
• [1] Assigning the parameter value to the private attribute value .

🧠 Exam Technique

OCR accepts either OCR pseudocode ( procedure / endprocedure ) or valid high-level programming language syntax (like Python def setValue(self, newValue): self.value = newValue ). Keep it minimal and avoid extra unnecessary lines.

Part (c) — Implementing the LinkedList Class

Constructor and Traversal Logic [7 Marks Total]

(i) Constructor Method: new() [2 Marks]

✅ Model Solution

procedure new() headNode = null endprocedure

Mark Breakdown:
• [1] Constructor header taking no parameters.
• [1] Assigning an appropriate null / none value to headNode .

❌ Common Errors

Assigning 0 or -1 to headNode . headNode holds a reference to a node object, not an integer value!

(ii) Completing outputList() [5 Marks]

✅ Completed Code

function outputList() returnValue = "" start = headNode while start != null returnValue = returnValue + start.getValue() + " " start = start.getNextNode() endwhile return returnValue endfunction

🧠 Step-by-Step Traversal Logic

Initialise pointer: Set start to the beginning of the list ( headNode ).
Condition: Continue looping as long as start != null (or <> null ).
Extract data: Call the accessor method start.getValue() .
Advance pointer: Move to the next node with start = start.getNextNode() .
Return: Return the accumulated string returnValue .

❌ Strict Examiner Guidance

Exact answers only: Do NOT write poorly formed relational operators such as =! . Write != or <> .
Remember parentheses are already given outside the blank for method calls: write getValue , not getValue() inside the blank.

Part (d) — Instantiating & Using the Linked List

Object instantiation, method calls, and I/O [5 Marks]

✅ Model Solution

createList = new linkedList() createList.insertNode(10) createList.insertNode(25) createList.insertNode(39) print(createList.outputList())

🧠 Mark Allocation Checklist

[1] Instantiating object: createList = new linkedList() .
[1] Using insertNode() method call correctly.
[1] All 3 data values ( 10, 25, 39 ) inserted in the correct order.
[1] Calling outputList() on the object.
[1] Outputting the returned value (e.g. using print(...) ).

❌ Common Errors

Forgetting to print: Writing createList.outputList() alone does not output anything because outputList() is a function that returns a string, not a procedure that prints.
Calling methods statically (e.g. linkedList.insertNode(10) ) instead of using the instance createList .

Part (e) — Algorithm to Remove a Node

Pointer manipulation and algorithmic decisions [5 Marks]

📐 Step-by-Step Algorithm (Traverse & Relink)

Start at the head: Initialise a current pointer to headNode and a previous pointer to null .
Compare value: Compare the value of the current node to the search parameter.
Decision — Match found at head: If the target is the first node ( headNode ), update headNode to point to headNode.getNextNode() .
Decision — Match found downstream: If target is found further in the list, set the nextNode pointer of the previous node to point directly to the current node's next node, bypassing and unlinking the target node.
Loop / Traverse: If values do not match, set previous = current, current = current.getNextNode(), and repeat until either the item is found or the current pointer equals null (end of list / item not found).

🧠 Pointer Diagram Concept

When removing node B from A → B → C :

Set A.nextNode = B.getNextNode() (which is C ).
Now the list is A → C . Node B is unlinked and reclaimed by garbage collection.

❌ Common Errors

Forgetting to track the previous node during traversal. In a singly linked list, you cannot step backwards once you locate the node!
Failing to specify the terminating condition when an item does not exist in the list ( null pointer).

Part (f) — Computational Methods

Identifying computational thinking approaches [3 Marks]

✅ Any 3 of the following:

Problem decomposition
Abstraction / Thinking abstractly
Backtracking
Data mining
Heuristics
Performance modelling
Pipelining
Visualisation
Thinking ahead / Thinking procedurally / Thinking concurrently

❌ Examiner Warning

Do NOT write programming constructs! Words like sequence, selection, and iteration receive 0 marks. Also, divide-and-conquer is given in the question stem, so it cannot be credited again.

Part (g)* — Extended Essay: OOP vs 2D Array Linked List

Comparing dynamic OOP vs static 2D array implementations [12 Marks]

💡 Synthesis: Comparing the Two Implementations

Feature	OOP Implementation (Classes/Pointers)	2D Array Implementation
Memory Allocation	Dynamic: Nodes are instantiated from heap memory as needed and deallocated when removed.	Static: Fixed size declared upfront (e.g. array[100][2] ). Memory is occupied whether used or not.
Memory Efficiency & Limits	Cannot overflow until all physical system memory is exhausted. No wasted unused memory.	Can result in stack/array overflow if size is exceeded, or wasted memory if list contains few items.
Free Space Management	Handled automatically by the system / garbage collector.	Requires a manual free list pointer and empty slot linking to track available rows for new insertions.
Reusability & Encapsulation	High: Encapsulated into classes ( node , linkedList ). Can be easily imported into any program without side effects.	Low: Code is tightly coupled to specific array variables and dimensions; harder to repurpose across multiple programs.

🧠 Structuring a Level 3 Response (9–12 Marks)

AO1 (Knowledge): Define both methods clearly. Explain nodes/pointers vs array index pointers and the free list.
AO2 (Application): Discuss reusability (OOP modularity vs array rigidity) and runtime operational efficiency (memory waste vs dynamic overhead).
AO3 (Evaluation): Provide a justified conclusion weighing which method is more appropriate in modern software engineering.

✅ Model Evaluative Conclusion

"While a 2D array approach may be easier to implement in low-level languages that lack dynamic memory or pointer support, the OOP approach is vastly superior for general software development. OOP offers true dynamic memory allocation, preventing arbitrary size limits and eliminating memory wastage. Crucially, the encapsulation of the node and linkedList classes provides exceptional code reusability across multiple applications with zero dependency on global state."

Topics

1.2 Software and software development · 1.4 Data types, data structures and algorithms · 2.1 Elements of computational thinking · 2.2 Problem solving and programming · 2.3 Algorithms · 1.2.4 Types of Programming Language · 1.4.2 Data Structures · 2.1.2 Thinking ahead · 2.2.1 Programming techniques · 2.2.2 Computational methods · 2.3.1 Algorithms

Question and mark scheme from the OCR A-Level Computer Science examination, Algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.