+1 678 648 4277 
Table Of Contents
  • Circular Linked List Real Word Uses

Circular Linked List Real Word Uses

The following are some real-world uses of a Circularly Linked List:
1. In some systems there’s what we call a round-robin scheduling in a queue. This is also popular on operating systems called time-sharing systems. The concept of time sharing is that since there are only few resource available, anybody who wants to use that resource can use it if it is their turn and they can use it only for a limited amount of time. Once the time is up, they go back to the queue and give the resource to the next item on the queue. So in a sense it is a circular queue.
2. A circular linked list is also useful if we need to rewind something. For instance, a play list of music or videos that plays one after the other. Once the last play list is finished, it will rewind to the first and play it again.
3. Circular linked lists are also useful when we need to go back and forward of a state. This is usually common in applications like when we do “undo” and “redo” action (e.g. Microsoft Word or Photoshop) or a website’s “back” and “forward” navigation.
 

A NumberList Linked List

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
NumberListadd(NumberList list1, NumberList list2) {
int carry = 0;
int list1Index = list1.size() – 1;
int list2Index = list2.size() – 1;
NumberListsumList = new NumberList();
    // Solve right to left until one of the list digits are fully processed
while(list1Index >= 0 && list2Index >= 0) {
int sum = carry + list1.get(list1Index) + list2.get(list2Index);
if(sum >= 10) {
carry = sum / 10;
sum = sum % 10;
        }
        // Accumulate result left to right too, push in front of list
sumList.add(0, sum);
        list1Index = list1Index - 1;
        list2Index = list2Index - 1;
    }
    // Bring down whatever is left on first list or from the second list
if(list1Index >= 0) {
while(list1Index >= 0) {
int sum = carry + list1.get(list1Index);
if(sum >= 10) {
carry = sum / 10;
sum = sum % 10;
            }
            // Accumulate result right to left too, push in front of list
sumList.add(0, sum);
            list1Index = list1Index - 1;
        }
    } else if(list2Index >= 0) {
while(list2Index >= 0) {
int sum = carry + list2.get(list2Index);
if(sum >= 10) {
carry = sum / 10;
sum = sum % 10;
            }
            // Accumulate result right to left too, push in front of list
sumList.add(0, sum);
            list2Index = list2Index - 1;
        }
    }
    // Add the last carry if it exists
if(carry > 0) {
sumList.add(0, carry);
    }
returnsumList;
}
Linked List with Small Modification
    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:

Linked List with Small Modification
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]
// Find the number of steps going deepest child, recursive method
intfindDeepestChildLength(Node current) {
if(current == null)
return 0;
intonTheNext = findDeepestChildLength(current.next);
intonTheChild = 0;
if(current.child != null)
onTheChild = 1;
onTheChild += findDeepestChildLength(current.child);
if(onTheNext>onTheChild)
returnonTheNext;
returnonTheChild;
}
// Put the node values on the appropriate list level, recursive method
voidsortNodesByLevel(Node current, intcurrentLevel, List[] listsByLevel) {
if(current == null)
return;
listsByLevel[currentLevel].add(current.element);
    // Scan those on the next, levels remain the same
sortNodesByLevel(current.next, currentLevel, listsByLevel);
    // Scan those going to child, levels increase
sortNodesByLevel(current.child, currentLevel + 1, listsByLevel);
}
// Entry point of the program, we assume we have the
// start node declared somewhere
void main() {
intnumLevels = findDeepestChildLength(startNode);
    // This is an array of lists
List[] listsByLevel = new List[numLevels];
for(inti = 0; i
listsByLevel[i] = new List();
    // Put each node's element on the appropriate level
sortNodesByLevel(startNode, 0, listsByLevel);
    // Put the levels all together as one flat list
    List flattenedList = new List();
for(inti = 0; i
        List listOnLevel = listsByLevel[i];
for(int j = 0; j
flattenedList.add(listOnlevel.get(j));
    }
returnflattenedList;
}
Algorithm Pseudocode to Flatten a Binary Tree
    Write the pseudo-code for an algorithm to flatten the binary tree to a linked list in place,
  such that this tree would become:    
 
Linked List with Small Modification

and this tree is flattened to this:
Linked List with Small Modification
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.
// Member function of the LinkedBinaryTree
List flatten() {
    List numbers = new List();
    // Root is assumed to be a member of LinkedBinaryTree
flattenHelper(numbers, root);
return numbers;
}
// Member function of the LinkedBinaryTree to
// traverse the binary tree and put it on a flat list
voidflattenHelper(List numbers, Node current) {
if(current == null)
return;
numbers.add(current.element);
flattenHelper(numbers, current.left);
flattenHelper(numbers, current.right);
}
Recursive Implementation of a Function
  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:    

Linked List with Small Modification

Write a recursive function which returns True if a tree is a valid DiskUsage tree and False otherwise.

// Recursively check if the sum of child nodes

// equates to the parent node's element

booleanisValidDiskUsage(Node currentNode) {

if(currentNode == null)

return true;

    // Do bottom-up approach

for(inti = 0; i

if(!isValidDiskUsage(currentNode.childNodes.get(i)))

return false;

    // Case for non-leaf nodes

if(currentNode.childNodes.size() > 0) {

int sum = 0;

for(inti = 0; i

sum = sum + currentNode.childNodes.get(i).element;

        // non-leaf nodes should have matching sum

if(currentNode.element != sum)

return false;

    }

    // Case for leaf nodes, no validations needed

return true;

}

Two Nodes Function in a Binary Tree

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:

Linked List with Small Modification

checkCousins("D", "C") = False

checkCousins("D", "F") = True

checkCousins("D", "B") = False

// Recursive method to find the parent of a key

Node findParentNode(Node current, String key) {

if(current == null)

return null;

if(current.left != null &¤t.left.element == key)

return current;

if(current.right != null &¤t.right.element == key)

return current;

    Node parent = findParentNode(current.left, key);

if(parent != null)

return parent;

returnfindParentNode(current.right, key);

}

// Find which level a node is located in tree

intfindNodeLevel(Node current, String key, currentLevel) {

if(current == null)

return -1;

if(current.element == key)

returncurrentLevel;

intsubLevel = findNodeLevel(current.left, key, currentLevel + 1);

if(subLevel != -1)

returnsubLevel;

returnfindNodeLevel(current.right, key, currentLevel + 1);

}

// Check if 2 elements are cousins

// We assume rootNode is the start of the tree

booleancheckCousins(String key1, String key2) {

    Node key1Parent = findParentNode(rootNode, key1);

    Node key2Parent = findParentNode(rootNode, key2);

    // Both key must exist in the tree

if(key1Parent == null || key2Parent == null)

return false;

    // Both key must not have the same parent

if(key1Parent == key2Parent)

return false;

    // Both key must be on the save level to be cousins

int key1Level = findNodeLevel(rootNode, key1, 0);

int key2Level = findNodeLevel(rootNode, key2, 0);

if(key1Level == key2Level)

return true;

return false;

}