ADTs and linked lists (HL)

A singly linked list stores the nodes A, B, C and D as shown. Each node contains a data value and a pointer to the next node, and head points to node A.

(a) Describe the steps required to delete node C from the list. [3]

(b) State one advantage of a linked list over an array when many deletions and insertions are needed. [1]

A program stores a to-do list. The programmer uses a list abstract data type (ADT) that provides the operations add(item), remove(item), isEmpty() and size().

(a) Define the term abstract data type. [2]

(b) The list ADT is first implemented using an array and is later re-implemented using a linked list. Explain why the rest of the to-do program does not need to be changed. [2]

The diagram shows three linked lists, each holding the values X, Y and Z.

(a) Identify the type of linked list shown in each of List 1, List 2 and List 3. [3]

(b) State one disadvantage of List 3 compared with List 1. [1]

Consider the following Python code.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = None
for v in [2, 9, 4, 7]:
    n = Node(v)
    n.next = head
    head = n

cur = head
while cur.next is not None:
    if cur.next.data < cur.data:
        cur.data, cur.next.data = cur.next.data, cur.data
    cur = cur.next

p = head
out = ""
while p is not None:
    out = out + str(p.data) + " "
    p = p.next
print(out)

(a) State the order of the values in the linked list, from head, immediately after the for loop has finished. [1]

(b) State the output of the program. [2]

(c) Explain why the condition of the first while loop is cur.next is not None rather than cur is not None. [1]

A linked list of names is kept in alphabetical order. It is stored in two arrays, Data and Next, where Next[i] holds the index of the node that follows node i, and -1 means there is no next node. The variable head holds 2. Unused positions form a separate free list that starts at the index held in free, which is currently 1.

(a) State the names in the order in which they are visited when the list is traversed from head. [1]

(b) The name Leo is inserted into the list so that it stays in alphabetical order, using the first free position. State every value in Data, Next, head and free that changes, and its new value. [4]

A singly linked list of integers is built from objects of a class Node, which has the attributes data and next. The last node's next is None.

Construct a function position_of(head, target) in Python or Java that returns the position (counting the first node as 1) of the first node whose data equals target, or returns -1 if no node holds target. For example, for the list 14 → 6 → 21 → 6 → 9, position_of(head, 6) returns 2. [5]

A collaborative text editor stores each line of a document as one element. Users frequently insert and delete lines in the middle of long documents, and the editor also has a Go to line n feature that jumps directly to any line number.

Evaluate the use of a singly linked list, rather than an array (fixed-size or dynamic), to store the lines. [6]

The diagram shows a doubly linked list. Each node has the attributes prev, data and next, and the list object keeps references head and tail.

(a) Node Q is to be deleted. Describe the two pointer changes that must be made. [2]

(b) Complete the method remove so that it deletes any given node, including when the node is the head, the tail, or the only node in the list. [4]

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def remove(self, node):
        # node is a reference to a node that is in this list
        ...

Six players in a party game are stored in a circular singly linked list, as shown. The variable start refers to the node holding Ana. The function below removes players from the circle until one is left.

def eliminate(start, k):
    prev = start
    while prev.next is not start:
        prev = prev.next
    cur = start
    while cur.next is not cur:
        for i in range(k - 1):
            prev = cur
            cur = cur.next
        print(cur.data)
        prev.next = cur.next
        cur = cur.next
    return cur.data

(a) Explain why the first while loop uses the condition prev.next is not start, rather than testing for None as in a linear (non-circular) linked list. [2]

(b) The call eliminate(start, 3) is made. State the five names printed, in order, and the value returned. [3]

(c) Explain why the condition cur.next is not cur stops the second loop when exactly one player remains. [1]

A singly linked list is built from Node objects with attributes data and next. Variable head refers to the first node, and the last node's next is None.

(a) Construct a function reverse(head), in Python or Java, that reverses the order of the nodes in place (by changing pointers only, without creating new nodes or using another data structure) and returns the new head. For example, 1 → 2 → 3 → 4 becomes 4 → 3 → 2 → 1. The function must also work for an empty list. [5]

(b) State the time complexity of your algorithm in Big O notation, for a list of $n$ nodes. [1]