-
Homepage
-
Credible Data Structures Homework Help
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 a few resources 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 playlist of music or videos that plays one after the other. Once the last playlist 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: |
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: |
|
|
and this tree is flattened to this:
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: |
|
|
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:
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;
}
