Data Structures and Algorithm: Distributed doubly linked list sum

Data Structures and Algorithm: Distributed doubly linked list sum

You are given a doubly linked list whose nodes are distributed. Every node has next, previous pointers and a method send(integer). A node can talk to its next and previous nodes only. Different instances of same  threads are running in them. 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 from right to left and then propagate the sum from left to right.

1. Every node except the right most node will wait for a first send call. Right node will send its value immediately to its left node.
2. After receiving the number from right side each node will add it with its own value and send it to its left.
3. The left most node, after receiving the send call, add its own number and send the complete sum to its right node.
4. All nodes will wait for a second send call.
5. After receiving the second send call each node will print the sum.
6. After printing each node will propagate the sum to its right node.

The threads will start running as soon as the nodes are created. But the doubly linked list may not be completely formed by then. So we will use a shared flag which will signal all the threads to start working.

public class DistributedDoublyLinkedListSum
{
 public static volatile boolean startFlag = 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.prev = d;
  d.prev = c;
  c.prev = b;
  b.prev = a;
  startFlag = true;
 }

 private static class Node
 {
  Node next;
  Node prev;
  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)
   {
   }
   if (node.next == null)
   {
    node.prev.send(node.value);
   } else
   {
    while (node.data == null)
    {
     try
     {
      Thread.sleep(10);
     } catch (InterruptedException e)
     {
     }
    }
    int sum = node.data + node.value;
    if (node.prev != null)
    {
     node.data = null;
     node.prev.send(sum);
    }
   }
   while (node.data == null)
   {
    try
    {
     Thread.sleep(10);
    } catch (InterruptedException e)
    {
    }
   }
   System.out.println("id:" + id + " sum:" + node.data);
   if (node.next != null)
   {
    node.next.send(node.data);
   }

  }
 }
}

Read full article from Data Structures and Algorithm: Distributed doubly linked list sum