Date | November 2019 | Marks available | 4 | Reference code | 19N.2.HL.TZ0.17 |
Level | HL | Paper | 2 | Time zone | no time zone |
Command term | Explain | Question number | 17 | Adapted from | N/A |
Question
The array line
in POSline
is now replaced by a singly linked list
of CartNode
objects. The class CartNode
has been defined as follows.
public class CartNode
{
private Cart myCart;
private CartNode next;
public CartNode(Cart aCart)
{
this.myCart = aCart;
this.next = null;
}
public Cart getCart(){ return this.myCart; }
public CartNode getNext(){ return this.next; }
public void setNext(CartNode nextNode)
{
this.next = nextNode;
}
}
The class POSlist
has been implemented with the standard list methods addLast
and removeFirst
that act on list
.
A method leaveList(int n)
is required in the class POSlist
, similar to the method leaveLine(int n)
that was added to the class POSline
.
Define the term object reference.
Using object references, construct the method public Cart removeFirst()
that removes the first CartNode
object from list
. The method must return the Cart
object in that node or null
if list
is empty.
Sketch the linked list list
after running the following code fragment where cart1, cart2, cart3, cart4
and cart5
have been instantiated as objects of the class Cart
.
POSlist queueList = new POSlist()
queueList.addLast(cart2);
queueList.addLast(cart1);
queueList.addLast(cart4);
queueList.removeFirst();
queueList.addLast(cart5);
queueList.addLast(cart3);
queueList.removeFirst();
Outline one feature of the abstract data structure queue that makes it unsuitable to implement customers waiting in line.
Using object references, construct the method public Cart leaveList(int n)
that removes the nth CartNode
object from list
. The method must return the Cart
object in that node.
You may assume that the nth CartNode
object exists in the list.
You may use any method declared or developed.
Explain the importance of using coding style and naming conventions when programming.
Markscheme
Award [2 max].
A pointer to a memory location;
where the object is stored;
Award [4 max].
Award [1] for declaring a result
variable (or similar)
Award [1] for correct use of .getCart()
Award [1] for reassigning the head of the list
Award [1] for returning the correct result (either the Cart or null)
public Cart removeFirst()
{
Cart result = null;
if (head != null)
{
result = head.getCart();
head = head.getNext();
}
return result;
}
Award [2 max].
Award [1] for a three nodes in order.
Award [1] root pointer (with or without identifier) and null pointer.
Award [2 max].
The abstract data structure queue is a FIFO structure / only allows addition at the end and removal from the front;
this is not sufficient because customers can change lines at any time;
Has no fixed length;
Which could lead to unmanageable/very long queues;
Note: do not award marks for responses that focus on dynamic vs static, since queues can be implemented either way.
Award [6 max].
Award [1] for declaring all variables used (including loop variable i
);
Award [1] for initialising variable(s) for list traversal;
Award [1] for dealing separately with the case where n equals 1;
Award [1] for attempted looping through the linked list until the correct position;
Award [1] for correct loop using curr = curr.getNext()
; (or similar)
Award [1] for correctly rearranging references to unhook the nth node;
Award [1] for returning the correct result;
Example answer using two CartNode
variables:
public Cart leaveList(int n){
Cart result = null; // explicit default result
CartNode prev = null;
CartNode curr = head;
if (n==1){
result = removeFirst();
}
else{
int i=1;
while (i<n){ // no need to check for null
prev = curr;
curr = curr.getNext();
i++;
}
result = curr.getCart();
prev.setNext(curr.getNext());
}
return result;
}
Example answer using one CartNode
variable:
public Cart leaveList(int n){
Cart result = null;
CartNode curr = head;
if (n==1){
result = removeFirst();
}
else{
int i=1;
while (i<n-1){ // no need to check for null
curr = curr.getNext();
i++;
} // curr points to node (n-1)
result = curr.getNext.getCart();
curr.setNext(curr.getNext().getNext());
}
return result;
}
Award [2 max] for including any of the following elements on the discussion
Indentation / Use of white space
Annotations
Meaningful identifiers
Capitalization conventions
Award [2 max] for including any of the following reasons in the discussion
Helps understanding / reading;
For easer maintenance / extension;
For better team-work / collaboration / development;
To help with de-bugging;
Mark as [2] and [2].
Examiners report
This was a straight-forward definition.
Required candidates to show their understanding of the use of pointers for moving through a linked list. Many were unprepared for this, although it is an established part of the course, and incorrectly attempted to make use of the Linked List library class along with associated methods.
Many missed out the use of both head and null pointers in sketching the linked list.
This was well-answered.
Required candidates to show their understanding of the use of pointers for moving through a linked list. Many were unprepared for this, although it is an established part of the course, and incorrectly attempted to make use of the Linked List library class along with associated methods.
This was a question that demanded specific examples which were not always given.