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

0 0 14 minutes read

Given a circular doubly linked list consisting of N nodes, the task is to modify every node of the given Linked List such that each node contains the sum of all nodes except that node.

Examples:

Input: 4 ↔ 5 ↔ 6 ↔7 ↔ 8
Output: 26 ↔ 25 ↔ 24 ↔ 23 ↔ 22
Explanation:
1^st Node: Sum of all nodes except itself = (5 + 6 + 7 + 8) = 26.
2^nd Node: Sum of all nodes except itself = (4 + 6 + 7 + 8) = 25.
3^rd Node: Sum of all nodes except itself = (4 + 5 + 7 + 8) = 24.
4^th Node: Sum of all nodes except itself = (4 + 5 + 6 + 8) = 23.
5^th Node: Sum of all Nodes except itself = (4 + 5 + 6 + 7) = 25.

Input: 1 ↔ 2
Output:2 ↔ 1

Naive Approach: The simplest approach to solve the problem is to traverse the given circular doubly linked list and for every node, traverse all the nodes and update that node with the sum of all the nodes except that node. After updating all the nodes, print the updated list.

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by storing the sum of data of all the nodes in a variable, say S, and then update the given linked list.
Follow the steps below to solve the problem:

Store the sum of the given linked list in a variable, say S.
Initialize a pointer, temp at the head of the linked list.
Iterate a loop until the temp→next does not become equal to the head and perform the following steps:
- Update the value of temp → data as (S – temp→data).
- Update temp to temp→next.
After completing the above steps, update the value of the last node to (S – temp→data) and print the updated linked list.

Below is the implementation of the above approach:

C

// C program for the above approach
 
#include<stdio.h>
#include<stdlib.h>
// Structure of a Node
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
// Function to insert a node at the
// end of the given Linked List
void insertEnd(struct Node** start,
            int value)
{
    // If the list is empty, then
    // create a single node
    // circular and doubly list
    if (*start == NULL) {
 
        // Create a new Node
        struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
        // Add values and links to
        // the next & the previous
        new_node->data = value;
        new_node->next = new_node;
        new_node->prev = new_node;
 
        // Update the start
        *start = new_node;
        return;
    }
 
    // If list is not empty, then
    // find last node
    struct Node* last = (*start)->prev;
 
    // Create Node dynamically
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = value;
 
    // Start is the next of new_node
    new_node->next = *start;
 
    // Make new node previous of start
    (*start)->prev = new_node;
 
    // Make last previous of new node
    new_node->prev = last;
 
    // Make new node next of old last
    last->next = new_node;
}
 
// Function to print the linked list
void display(struct Node* start)
{
    // Forward traversal
    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);
    // Backward traversal
    printf("\nTraversal in reverse"
        " direction \n");
    struct Node* last = start->prev;
    temp = last;
 
    // Traverse the Linked List
    while (temp->prev != last) {
 
        // Print the data
        printf("%d  ",temp->data);
        temp = temp->prev;
    }
 
    // Print the data
    printf("%d  ",temp->data);
}
 
// Function to find the sum of all
// nodes in the given Linked List
int findSum(struct Node* start)
{
    // Stores the sum of all the nodes
    int sum = 0;
 
    struct Node* temp = start;
 
    // Traverse the linked list and
    // update the sum
    while (temp->next != start) {
 
        // Update the sum
        sum += temp->data;
 
        // Update the temp
        temp = temp->next;
    }
 
    // Update the sum
    sum += temp->data;
 
    // Return the sum
    return sum;
}
 
// Function to update the data of
// every node with the sum of data
// of all nodes except itself
void updateNodeValue(struct Node* start)
{
    // Stores the total sum
    // of all the nodes
    int sum = findSum(start);
 
    struct Node* temp = start;
 
    // Traverse the linked list
    // and update each node's data
    while (temp->next != start) {
 
        // Update the temp->data
        temp->data = sum - temp->data;
 
        // Update the temp
        temp = temp->next;
    }
 
    // Update the temp->data
    temp->data = sum - temp->data;
}
 
// Function to construct a
// circular doubly linked list
struct Node* formLinkedList(struct Node* start)
{
    // Given linked list as:
    // 4 <-> 5 <-> 6 <-> 7 <-> 8
    insertEnd(&start, 4);
    insertEnd(&start, 5);
    insertEnd(&start, 6);
    insertEnd(&start, 7);
    insertEnd(&start, 8);
 
    // Return the head of the
    // constructed Linked List
    return start;
}
 
// Driver Code
int main()
{
    // Linked list formation
    struct Node* start = NULL;
    start = formLinkedList(start);
 
    // Display the linked list
    display(start);
 
    // Function Call
    updateNodeValue(start);
 
    // Display the linked list
    // after updating nodes
    printf("\nAfter updating the node values:\n");
 
    // Print the Linked List
    display(start);
 
    return 0;
}

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Node
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
// Function to insert a node at the
// end of the given Linked List
void insertEnd(struct Node** start,
               int value)
{
    // If the list is empty, then
    // create a single node
    // circular and doubly list
    if (*start == NULL) {
 
        // Create a new Node
        struct Node* new_node = new Node();
 
        // Add values and links to
        // the next & the previous
        new_node->data = value;
        new_node->next = new_node;
        new_node->prev = new_node;
 
        // Update the start
        *start = new_node;
        return;
    }
 
    // If list is not empty, then
    // find last node
    Node* last = (*start)->prev;
 
    // Create Node dynamically
    struct Node* new_node = new Node;
    new_node->data = value;
 
    // Start is the next of new_node
    new_node->next = *start;
 
    // Make new node previous of start
    (*start)->prev = new_node;
 
    // Make last previous of new node
    new_node->prev = last;
 
    // Make new node next of old last
    last->next = new_node;
}
 
// Function to print the linked list
void display(struct Node* start)
{
    // Forward traversal
    struct Node* temp = start;
 
    cout << "Traversal in forward "
           "direction \n";
    while (temp->next != start) {
        cout << temp->data << " ";
        temp = temp->next;
    }
   cout <<  temp->data << " " ;
 
    // Backward traversal
    cout <<  "\nTraversal in reverse"
           " direction \n";
    Node* last = start->prev;
    temp = last;
 
    // Traverse the Linked List
    while (temp->prev != last) {
 
        // Print the data
        cout << temp->data << " " ;
        temp = temp->prev;
    }
 
    // Print the data
    cout <<  temp->data << " ";
}
 
// Function to find the sum of all
// nodes in the given Linked List
int findSum(Node*& start)
{
    // Stores the sum of all the nodes
    int sum = 0;
 
    Node* temp = start;
 
    // Traverse the linked list and
    // update the sum
    while (temp->next != start) {
 
        // Update the sum
        sum += temp->data;
 
        // Update the temp
        temp = temp->next;
    }
 
    // Update the sum
    sum += temp->data;
 
    // Return the sum
    return sum;
}
 
// Function to update the data of
// every node with the sum of data
// of all nodes except itself
void updateNodeValue(Node*& start)
{
    // Stores the total sum
    // of all the nodes
    int sum = findSum(start);
 
    Node* temp = start;
 
    // Traverse the linked list
    // and update each node's data
    while (temp->next != start) {
 
        // Update the temp->data
        temp->data = sum - temp->data;
 
        // Update the temp
        temp = temp->next;
    }
 
    // Update the temp->data
    temp->data = sum - temp->data;
}
 
// Function to construct a
// circular doubly linked list
Node* formLinkedList(Node* start)
{
    // Given linked list as:
    // 4 <-> 5 <-> 6 <-> 7 <-> 8
    insertEnd(&start, 4);
    insertEnd(&start, 5);
    insertEnd(&start, 6);
    insertEnd(&start, 7);
    insertEnd(&start, 8);
 
    // Return the head of the
    // constructed Linked List
    return start;
}
 
// Driver Code
int main()
{
    // Linked list formation
    struct Node* start = NULL;
    start = formLinkedList(start);
 
    // Display the linked list
    display(start);
 
    // Function Call
    updateNodeValue(start);
 
    // Display the linked list
    // after updating nodes
    cout << "\nAfter updating "
         << "the node values:\n";
 
    // Print the Linked List
    display(start);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
static Node start;
static class Node 
{
    int data;
    Node next;
    Node prev;
}
 
// Function to insert a node at the
// end of the given Linked List
// Function to insert at the end
static void insertEnd(int value)
{
 
    // If the list is empty, create a single
    // node circular and doubly list
    if (start == null) 
    {
        Node new_node = new Node();
        new_node.data = value;
        new_node.next = new_node.prev = new_node;
        start = new_node;
        return;
    }
 
    // If list is not empty
 
    // Find last node
    Node last = (start).prev;
 
    // Create Node dynamically
    Node new_node = new Node();
    new_node.data = value;
 
    // Start is going to be
    // next of new_node
    new_node.next = start;
 
    // Make new node previous of start
    (start).prev = new_node;
 
    // Make last previous of new node
    new_node.prev = last;
 
    // Make new node next of old last
    last.next = new_node;
}
 
// Function to print the linked list
static void display()
{
    Node temp = start;
 
    System.out.printf("\nTraversal in " + 
                      "forward direction \n");
    while (temp.next != start) 
    {
        System.out.printf("%d ", temp.data);
        temp = temp.next;
    }
    System.out.printf("%d ", temp.data);
 
    System.out.printf("\nTraversal in reverse " +
                     "direction \n");
    Node last = start.prev;
    temp = last;
     
    while (temp.prev != last) 
    {
        System.out.printf("%d ", temp.data);
        temp = temp.prev;
    }
    System.out.printf("%d ", temp.data);
}
 
// Function to update the data of
// every node with the sum of data
// of all nodes except itself
static void updateNodeValue()
{
     
    // Stores the total sum
    // of all the nodes
    int sum = findSum(start);
 
    Node temp = start;
 
    // Traverse the linked list
    // and update each node's data
    while (temp.next != start)
    {
         
        // Update the temp->data
        temp.data = sum - temp.data;
 
        // Update the temp
        temp = temp.next;
    }
 
    // Update the temp->data
    temp.data = sum - temp.data;
}
 
static Node formLinkedList(Node start)
{
     
    // Given linked list as:
    // 4 <-> 5 <-> 6 <-> 7 <-> 8
    insertEnd(4);
    insertEnd(5);
    insertEnd(6);
    insertEnd(7);
    insertEnd(8);
 
    // Return the head of the
    // constructed Linked List
    return start;
}
 
// Function to find the sum of all
// nodes in the given Linked List
static int findSum(Node head)
{
    Node temp = head;
     
    // Stores the sum of all the nodes
    int sum = 0;
     
    if (head != null)
    {
         
        // Traverse the linked list and
        // update the sum
        do
        {
            temp = temp.next;
            sum += temp.data;
        } while (temp != head);
    }
     
    // Return the sum
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    Node start = null;
    start = formLinkedList(start);
 
    // Display the linked list
    display();
 
    // Function call
    updateNodeValue();
 
    // Display the linked list
    // after updating nodes
    System.out.print("\nAfter updating " +
                     "the node value:\n");
 
    // Print the Linked List
    display();
}
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Structure of a Node
class Node:
     
    def __init__(self, d):
         
        self.data = d
        self.next = None
        self.prev = None
 
# Function to insert a node at the
# end of the given Linked List
def insertEnd(start, value):
     
    # If the list is empty, then
    # create a single node
    # circular and doubly list
    if (start == None):
 
        # Create a new Node
        new_node = Node(value)
 
        new_node.next = new_node
        new_node.prev = new_node
 
        # Update the start
        start = new_node
        return start
 
    # If list is not empty, then
    # find last node
    last = start.prev
 
    # Create Node dynamically
    new_node = Node(value)
    new_node.data = value
 
    # Start is the next of new_node
    new_node.next = start
 
    # Make new node previous of start
    start.prev = new_node
 
    # Make last previous of new node
    new_node.prev = last
 
    # Make new node next of old last
    last.next = new_node
 
    return start
 
# Function to print the linked list
def display(start):
     
    # Forward traversal
    temp = start
 
    print("Traversal in forward direction")
    while (temp and temp.next != start):
        print(temp.data, end = " ")
        temp = temp.next
         
    print(temp.data, end = " ")
 
    # Backward traversal
    print("\nTraversal in reverse direction")
    last = start.prev
    temp = last
 
    # Traverse the Linked List
    while (temp.prev != last):
 
        # Print the data
        print(temp.data, end = " ")
        temp = temp.prev
 
    # Print the data
    print(temp.data, end = " ")
 
# Function to find the sum of all
# nodes in the given Linked List
def findSum(start):
     
    # Stores the sum of all the nodes
    sum = 0
 
    temp = start
 
    # Traverse the linked list and
    # update the sum
    while (temp.next != start):
 
        # Update the sum
        sum += temp.data
 
        # Update the temp
        temp = temp.next
 
    # Update the sum
    sum += temp.data
 
    # Return the sum
    return sum
 
# Function to update the data of
# every node with the sum of data
# of all nodes except itself
def updateNodeValue(start):
     
    # Stores the total sum
    # of all the nodes
    sum = findSum(start)
 
    temp = start
 
    # Traverse the linked list
    # and update each node's data
    while (temp.next != start):
 
        # Update the temp.data
        temp.data = sum - temp.data
 
        # Update the temp
        temp = temp.next
 
    # Update the temp.data
    temp.data = sum - temp.data
 
# Function to construct a
# circular doubly linked list
def formLinkedList(start):
     
    # Given linked list as:
    # 4 <. 5 <. 6 <. 7 <. 8
    start = insertEnd(start, 4)
    start = insertEnd(start, 5)
    start = insertEnd(start, 6)
    start = insertEnd(start, 7)
    start = insertEnd(start, 8)
 
    # Return the head of the
    # constructed Linked List
    return start
 
# Driver Code
if __name__ == '__main__':
     
    # Linked list formation
    start = None
    start = formLinkedList(start)
 
    # Display the linked list
    display(start)
 
    # Function Call
    updateNodeValue(start)
 
    # Display the linked list
    # after updating nodes
    print("\nAfter updating the node values:")
 
    # Print the Linked List
    display(start)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
static Node start;
public class Node 
{
    public int data;
    public Node next;
    public Node prev;
}
 
// Function to insert a node at the
// end of the given Linked List
// Function to insert at the end
static void insertEnd(int value)
{
    Node new_node;
     
    // If the list is empty, create a single
    // node circular and doubly list
    if (start == null) 
    {
        new_node = new Node();
        new_node.data = value;
        new_node.next = new_node.prev = new_node;
        start = new_node;
        return;
    }
 
    // If list is not empty
 
    // Find last node
    Node last = (start).prev;
 
    // Create Node dynamically
    new_node = new Node();
    new_node.data = value;
 
    // Start is going to be
    // next of new_node
    new_node.next = start;
 
    // Make new node previous of start
    (start).prev = new_node;
 
    // Make last previous of new node
    new_node.prev = last;
 
    // Make new node next of old last
    last.next = new_node;
}
 
// Function to print the linked list
static void display()
{
    Node temp = start;
 
    Console.Write("\nTraversal in " + 
                  "forward direction \n");
                   
    while (temp.next != start) 
    {
        Console.Write("{0} ", temp.data);
        temp = temp.next;
    }
    Console.Write("{0} ", temp.data);
 
    Console.Write("\nTraversal in reverse " +
                     "direction \n");
    Node last = start.prev;
    temp = last;
     
    while (temp.prev != last) 
    {
        Console.Write("{0} ", temp.data);
        temp = temp.prev;
    }
    Console.Write("{0} ", temp.data);
}
 
// Function to update the data of
// every node with the sum of data
// of all nodes except itself
static void updateNodeValue()
{
     
    // Stores the total sum
    // of all the nodes
    int sum = findSum(start);
 
    Node temp = start;
 
    // Traverse the linked list
    // and update each node's data
    while (temp.next != start)
    {
         
        // Update the temp->data
        temp.data = sum - temp.data;
 
        // Update the temp
        temp = temp.next;
    }
 
    // Update the temp->data
    temp.data = sum - temp.data;
}
 
static Node formList(Node start)
{
     
    // Given linked list as:
    // 4 <-> 5 <-> 6 <-> 7 <-> 8
    insertEnd(4);
    insertEnd(5);
    insertEnd(6);
    insertEnd(7);
    insertEnd(8);
 
    // Return the head of the
    // constructed Linked List
    return start;
}
 
// Function to find the sum of all
// nodes in the given Linked List
static int findSum(Node head)
{
    Node temp = head;
     
    // Stores the sum of all the nodes
    int sum = 0;
     
    if (head != null)
    {
         
        // Traverse the linked list and
        // update the sum
        do
        {
            temp = temp.next;
            sum += temp.data;
        } while (temp != head);
    }
     
    // Return the sum
    return sum;
}
 
// Driver code
public static void Main(String []args)
{
    Node start = null;
    start = formList(start);
 
    // Display the linked list
    display();
 
    // Function call
    updateNodeValue();
 
    // Display the linked list
    // after updating nodes
    Console.Write("\nAfter updating " +
                  "the node value:\n");
 
    // Print the Linked List
    display();
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Structure of a Node
class Node {
 
    constructor()
    {
        this.data = 0;
        this.next = null;
        this.prev = null;
    }
};
 
// Function to insert a node at the
// end of the given Linked List
function insertEnd(start, value)
{
    // If the list is empty, then
    // create a single node
    // circular and doubly list
    if (start == null) {
 
        // Create a new Node
        var new_node = new Node();
 
        // Add values and links to
        // the next & the previous
        new_node.data = value;
        new_node.next = new_node;
        new_node.prev = new_node;
 
        // Update the start
        start = new_node;
        return start;
    }
 
    // If list is not empty, then
    // find last node
    var last = start.prev;
 
    // Create Node dynamically
    var new_node = new Node;
    new_node.data = value;
 
    // Start is the next of new_node
    new_node.next = start;
 
    // Make new node previous of start
    start.prev = new_node;
 
    // Make last previous of new node
    new_node.prev = last;
 
    // Make new node next of old last
    last.next = new_node;
 
    return start;
}
 
// Function to print the linked list
function display(start)
{
    // Forward traversal
    var temp = start;
 
    document.write("Traversal in forward "+
           "direction <br>");
    while (temp.next != start) {
        document.write(temp.data + " ");
        temp = temp.next;
    }
    document.write(temp.data  + " ");
 
    // Backward traversal
    document.write("<br>Traversal in reverse"+
           " direction <br>");
    var last = start.prev;
    temp = last;
 
    // Traverse the Linked List
    while (temp.prev != last) {
 
        // Print the data
        document.write( temp.data + " ");
        temp = temp.prev;
    }
 
    // Print the data
    document.write( temp.data + " ");
}
 
// Function to find the sum of all
// nodes in the given Linked List
function findSum(start)
{
    // Stores the sum of all the nodes
    var sum = 0;
 
    var temp = start;
 
    // Traverse the linked list and
    // update the sum
    while (temp.next != start) {
 
        // Update the sum
        sum += temp.data;
 
        // Update the temp
        temp = temp.next;
    }
 
    // Update the sum
    sum += temp.data;
 
    // Return the sum
    return sum;
}
 
// Function to update the data of
// every node with the sum of data
// of all nodes except itself
function updateNodeValue(start)
{
    // Stores the total sum
    // of all the nodes
    var sum = findSum(start);
 
    var temp = start;
 
    // Traverse the linked list
    // and update each node's data
    while (temp.next != start) {
 
        // Update the temp.data
        temp.data = sum - temp.data;
 
        // Update the temp
        temp = temp.next;
    }
 
    // Update the temp.data
    temp.data = sum - temp.data;
}
 
// Function to construct a
// circular doubly linked list
function formLinkedList(start)
{
    // Given linked list as:
    // 4 <. 5 <. 6 <. 7 <. 8
    start = insertEnd(start, 4);
    start = insertEnd(start, 5);
    start = insertEnd(start, 6);
    start = insertEnd(start, 7);
    start = insertEnd(start, 8);
 
    // Return the head of the
    // constructed Linked List
    return start;
}
 
// Driver Code
// Linked list formation
var start = null;
start = formLinkedList(start);
 
// Display the linked list
display(start);
 
// Function Call
updateNodeValue(start);
 
// Display the linked list
// after updating nodes
document.write( "<br>After updating "
     + "the node values:<br>");
      
// Print the Linked List
display(start);
 
// This code is contributed by rrrtnx.
</script>

Output:

Traversal in forward direction 
4 5 6 7 8 
Traversal in reverse direction 
8 7 6 5 4 
After updating the node values:
Traversal in forward direction 
26 25 24 23 22 
Traversal in reverse direction 
22 23 24 25 26

Time Complexity: O(N), where N is the total number of nodes in the circular doubly linked list.
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!