Describe 3 real-world uses for the CircularlyLinkedList.
For each description describe how the CircularlyLinkedList is used in that application, and what the benefits are of using the CircularlyLinkedList.
A NumberList is a linked list used to represent the digits of a number. For example 983 is represented as:
[ Node(9), Node(8), Node(3) ]
Write the pseudocode for an algorithm which performs addition on 2 NumberLists, such that:
[ Node(9), Node(8), Node(3) ] + [ Node(1), Node(0), Node(4), Node(3)] = [ Node(2), Node(0), Node(2), Node(6)]
Your pseudocode should use only the methods of the List ADT.
Take care to deal with lists of different sizes. If you are using recursion, highlight the base cases.
You are given a linked list with a small modification: in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list.
These child lists may have one or more children of their own, and so on.
The result is a multilevel linked data structure and an example is shown here: see image.
Write the pseudcode for an algorithm which take the head of the first level (level=0) of the multilevel list and returns a flattened singly linked list.
You need to flatten the list in way that all nodes at first level should come first, then nodes of second level, and so on.
For the example above, the flattened singly linked list would be:
[9, 8, 4, 7, 13, 5, 12, 3, 16, 21, 10, 14, 23, 41, 9, 34, 30]
Write the pseudo-code for an algorithm to flatten the binary tree to a linked list in place, such that this tree would become: see image.
and this tree is flattened to this: see image.
The binary tree must be flattened in place, meaning that no additional data structures are to be used. The flatten() method should be implemented as a member function of the LinkedBinaryTree class (just include the necessary function). The result of calling the function is that the left child of each node points to null and the right child of each node points to the next element in the list.
In the lectures we discussed the recursive implementation of a function which computes the disk usage of a file system tree. In this DiskUsage tree, each node should hold the sum of the disk usage of all of its descendant nodes. The size of an empty DiskUsage tree is 0, and a leaf node is also considered a DiskUsage tree.
Here is an example: see image.
Write a recursive function which returns True if a tree is a valid DiskUsage tree and False otherwise.
You are familiar with the parent -> child relationship in a binary tree.
Write a function which determines if two nodes in a binary tree are cousins.
Two nodes are cousins if they are on the same level and have different parents. In the following example: see image.
checkCousins("D", "C") = False
checkCousins("D", "F") = True
checkCousins("D", "B") = False