Data Structures and Algorithm: Distributed Circular linked list sum
Read full article from Data Structures and Algorithm: Distributed Circular linked list sum
You are given a circular linked list whose nodes are distributed. Every node has next pointer and a method send(integer). A node can talk to its next node only. Different instances of same threads are running in the nodes. How would you implement the run method of the thread class so that each node prints the sum of complete linked list.
We will accumulate the number along the next pointer circularly and then propagate it in the same direction in second iteration.
The trick of this problem is that in a circular linked list every node is equal and there is no starting and ending node. For this, we have taken a flag object, Every thread will try to acquire its lock, and whoever wins in this race will become a decisive node and it changes the value of the flag so that no other thread can become decisive. So there will be only one node randomly chosen in the linked list which will start the operation. It will send its value to the next node. All other nodes will wait for its first send call. After that it adds its own value and send it to the next node. In this way the decisive node will be the first to know the complete sum. It will then send it to the next node. So again every node will wait for second send call. Then it will print the total sum and propagate it to its next node and exits.
public class DistributedCircularListSum
{
public static volatile boolean startFlag = false;
private static Boolean flag = false;
public static void main(String[] args)
{
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
Node e = new Node(5);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
e.next = a;
startFlag = true;
}
private static class Node
{
Node next;
int value;
Integer data;
public Node(int value)
{
this.value = value;
new Thread(new NodeRunner(this, value)).start();
}
public synchronized void send(int data)
{
this.data = data;
}
}
private static class NodeRunner implements Runnable
{
Node node;
int id;
public NodeRunner(Node node, int id)
{
this.node = node;
this.id = id;
}
@Override
public void run()
{
while (!startFlag)
{
}
boolean isFirst = false;
synchronized (flag)
{
if (flag == false)
{
flag = true;
isFirst = true;
}
}
if (isFirst)
node.next.send(node.value);
else
{
while (node.data == null)
{
try
{
Thread.sleep(10);
} catch (InterruptedException e)
{
}
}
int sum = node.value + node.data;
node.data = null;
node.next.send(sum);
}
while (node.data == null)
{
try
{
Thread.sleep(10);
} catch (InterruptedException e)
{
}
}
System.out.println("id:" + id + "sum:" + node.data);
node.next.send(node.data);
}
}
}
