q2.py

def show(linked_list):
    current_node = linked_list.head # Start with the head of the list
    while current_node != None: # Keep going until there is no data in the current node
        print(current_node.data)
        current_node = current_node.next # Update the current node to the next one

def cat(linked_list_a, linked_list_b):
    current_node = linked_list_a.head
    if current_node == None:
        return linked_list_b # If there is no data in list A, return list B
    while current_node.next != None:
        current_node = current_node.next # Change the current node to the last node in list A with data
    node_to_add = linked_list_b.head # Set the node to concatenate as the first node in list B
    while node_to_add != None:
        current_node.next = node_to_add # Concatenate list A and the node
        current_node = current_node.next # Change the current node to the new last node in list A
        node_to_add = node_to_add.next # Update the node to concatenate to the next node in list B
    linked_list_a.size += linked_list_b.size
    return linked_list_a # Return the concatenated list

def smart_cat(linked_list_a, linked_list_b):
    if linked_list_a.head == None:
        return linked_list_b # If there is no data in list A, return list B
    node_to_add = linked_list_b.head # Set the node to concatenate as the first node in list B
    while node_to_add != None:
        linked_list_a.tail.next = node_to_add # Add the node to the end of list A
        linked_list_a.tail = node_to_add # Update the tail of list A
        node_to_add = node_to_add.next # Update the node to concatenate to the next node in list B
    linked_list_a.size += linked_list_b.size
    return linked_list_a # Return the concatenated list

def make_queue():
    N5 = Node(21) # Set tail first, with no next node
    N4 = Node(3, N5)
    N3 = Node(18, N4)
    N2 = Node(9, N3)
    N1 = Node(4, N2) # Set head
    linked_list_with_tail = LinkedListWithTail(N1, N5, 5) # Create LLWT with head, tail and size
    return linked_list_with_tail

def enqueue(ll_queue, value):
    node = Node(value) # Set the node to be enqueued with the data as value and no next
    if ll_queue.head == None:
        ll_queue.head = node # If the list is empty, set the new node as the head
    else:
        ll_queue.tail.next = node # Set the node as the last node if the list is not empty
    ll_queue.tail = node # Set the node as the new tail
    ll_queue.size += 1
    return ll_queue

def convert_to_array_queue(ll_queue):
    A = [None] * 10 # Initialise array A with 10 empty indexes
    f = 0 # Set the front of the queue to the first index in A
    r = 0
    current_node = ll_queue.head # Set the current node to the first node in the list
    while r < 10 and current_node != None: # Iterate until A is full or the last node is reached
        A[r] = current_node.data # Add the current node to array A
        current_node = current_node.next # Update the current node to the next node in the list
        r += 1 # Update the rear of the queue
    if r != 0:
        r -= 1 # Set the rear of the queue to the last index in A which has an item
    return (A, f, r)