Modify a Circular Doubly Linked List such that each node stores the sum of all nodes except itself

  

#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    int data;

    struct Node* next;

    struct Node* prev;

};

  

void insertEnd(struct Node** start,

               int value)

{

    

    

    

    if (*start == NULL) {

  

        

        struct Node* new_node = new Node();

  

        

        

        new_node->data = value;

        new_node->next = new_node;

        new_node->prev = new_node;

  

        

        *start = new_node;

        return;

    }

  

    

    

    Node* last = (*start)->prev;

  

    

    struct Node* new_node = new Node;

    new_node->data = value;

  

    

    new_node->next = *start;

  

    

    (*start)->prev = new_node;

  

    

    new_node->prev = last;

  

    

    last->next = new_node;

}

  

void display(struct Node* start)

{

    

    struct Node* temp = start;

  

    printf("Traversal in forward "

           "direction \n");

    while (temp->next != start) {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("%d ", temp->data);

  

    

    printf("\nTraversal in reverse"

           " direction \n");

    Node* last = start->prev;

    temp = last;

  

    

    while (temp->prev != last) {

  

        

        printf("%d ", temp->data);

        temp = temp->prev;

    }

  

    

    printf("%d ", temp->data);

}

  

int findSum(Node*& start)

{

    

    int sum = 0;

  

    Node* temp = start;

  

    

    

    while (temp->next != start) {

  

        

        sum += temp->data;

  

        

        temp = temp->next;

    }

  

    

    sum += temp->data;

  

    

    return sum;

}

  

void updateNodeValue(Node*& start)

{

    

    

    int sum = findSum(start);

  

    Node* temp = start;

  

    

    

    while (temp->next != start) {

  

        

        temp->data = sum - temp->data;

  

        

        temp = temp->next;

    }

  

    

    temp->data = sum - temp->data;

}

  

Node* formLinkedList(Node* start)

{

    

    

    insertEnd(&start, 4);

    insertEnd(&start, 5);

    insertEnd(&start, 6);

    insertEnd(&start, 7);

    insertEnd(&start, 8);

  

    

    

    return start;

}

  

int main()

{

    

    struct Node* start = NULL;

    start = formLinkedList(start);

  

    

    display(start);

  

    

    updateNodeValue(start);

  

    

    

    cout << "\nAfter updating "

         << "the node values:\n";

  

    

    display(start);

  

    return 0;

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets