Posted on by Kalkicode
Code Doubly linked list

Find the sum of all nodes which is divisible by K in doubly linked list

The problem discussed here involves finding the sum of all nodes in a doubly linked list that are divisible by a given key. A doubly linked list is a data structure where each node contains a value and two pointers, one pointing to the next node (in the forward direction) and another pointing to the previous node (in the backward direction). The task is to iterate through the linked list, identify the nodes with values divisible by the given key, and compute their sum.

Problem Statement

Given a doubly linked list and a key, the objective is to find the sum of all node values in the list that are divisible by the given key.

Idea to Solve

The idea to solve this problem is to iterate through the linked list, calculate the sum of values that satisfy the divisibility condition, and return the final sum.

Pseudocode

Here's the pseudocode that outlines the algorithm to find the sum of nodes divisible by a given key in a doubly linked list:

class LinkNode:
    int data
    LinkNode next
    LinkNode prev

class DoublyLinkedList:
    LinkNode head

    function addNode(value):
        Create a new node with the given value
        If head is null:
            Set head to the new node
        Else:
            Initialize a temp node with head
            While temp's next is not null:
                Move temp to temp's next
            Set temp's next to the new node
            Set new node's prev to temp

    function sumDivisibleByKey(key):
        Initialize result to 0
        Initialize a node with head
        While node is not null:
            If node's data is divisible by key:
                Add node's data to result
            Move node to node's next
        Return result

Create a DoublyLinkedList object
Add nodes to the object
Call sumDivisibleByKey function with a key and print the result

Algorithm Explanation

  • The addNode function adds a new node to the end of the linked list. If the list is empty, it updates the head pointer. Otherwise, it traverses the list to find the last node and then adds the new node.
  • The sumDivisibleByKey function initializes a result variable to 0 and iterates through the linked list. For each node, it checks if the node's data is divisible by the given key. If it is, the node's data is added to the result. Finally, the function returns the result.

Program List

Time Complexity

  • Adding a node at the end of the linked list takes O(N) time in the worst case, where N is the number of nodes in the list.
  • Calculating the sum of nodes divisible by the key also takes O(N) time since all nodes are traversed.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment