Posted on by Kalkicode

# Remove all the even digit sum nodes from a doubly linked list

The problem at hand involves manipulating a doubly linked list to remove nodes that have an even digit sum in their key. A doubly linked list is a data structure in which each node contains a key, a reference to the next node, and a reference to the previous node. The objective is to develop a program that identifies nodes with an even digit sum in their keys and removes them from the linked list.

## Problem Statement

The problem requires creating a program that accepts a doubly linked list as input, scans each node's key, calculates the digit sum of each key, and removes nodes whose digit sum is even. The task includes handling the adjustments in the linked list to maintain connectivity after removal.

## Example

Given a sample doubly linked list:

``Input: 17 <-> 4 <-> 23 <-> 1 <-> 13 <-> 10``

Remove all nodes witch node digit sum is even. The digit sum of a number is the sum of its digits.

17 digit 1 + 7 = 8 and 8 is even.

4 is even.

13 digit 1 + 3 = 4 is even.

After removing nodes with even digit sum:

``Output: 23 <-> 1 <-> 10``

## Idea to Solve

To solve this problem, we need to implement a function that iterates through the doubly linked list, calculates the digit sum of each key, and removes nodes that have an even digit sum. The algorithm should account for various cases such as removing the head node, updating pointers, and maintaining the integrity of the list.

## Pseudocode

Here's the pseudocode representation of the algorithm to remove nodes with an even digit sum from the doubly linked list:

``````function deleteEvenDigitSum(dll):
auxiliary = dll.front
while auxiliary is not null:
if digitSum(auxiliary.key) is even:
temp = auxiliary
auxiliary = temp.next
if temp is dll.front:
dll.front = auxiliary
if dll.rear is temp:
dll.rear = temp.back
if temp.back is not null:
temp.back.next = auxiliary
if auxiliary is not null:
auxiliary.back = temp.back
free(temp)
else:
auxiliary = auxiliary.next``````

## Explanation of Algorithm

1. Start iterating through the linked list from the front.
2. Calculate the digit sum of the current node's key using the `digitSum` function.
3. If the digit sum is even, handle several cases:
• Remove the current node.
• Update pointers to maintain connectivity in the linked list.
• Free the memory of the removed node.
4. Move to the next node.
5. Repeat steps 2-4 until all nodes are traversed.

## Program List

``````// C Program
// Remove all the even digit sum nodes from a doubly linked list
#include <stdio.h>
#include <stdlib.h>

{
int key;
};
struct DoublyLL
{
};
// Returns a new linked list
{
struct DoublyLL *dll = (struct DoublyLL *) malloc(sizeof(struct DoublyLL));
if (dll == NULL)
{
printf("\n Memory overflow , When creating a new linked list");
}
else
{
// Set initial value of linked list
dll->front = NULL;
dll->rear = NULL;
}
return dll;
}
// Returns a new node of linked list
{
// Create dynamic node
if (node != NULL)
{
node->key = key;
node->back = back;
node->next = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
// Handles the request to add new node at the end of linked list
void addNode(struct DoublyLL *dll, int data)
{
// Create dynamic node
struct LinkNode *node = newNode(data, dll->rear);
if (dll->front == NULL)
{
dll->front = node;
dll->rear = node;
}
else
{
dll->rear->next = node;
}
dll->rear = node;
}
void display(struct DoublyLL *dll)
{
if (dll->front == NULL)
{
return;
}
printf(" Front to back \n");
while (temp != NULL)
{
printf(" %d →", temp->key);
// Visit to next node
temp = temp->next;
}
printf(" NULL");
temp = dll->rear;
printf("\n Back to front\n");
while (temp != NULL)
{
printf(" %d →", temp->key);
// Visit to back node
temp = temp->back;
}
printf(" NULL\n");
}
// Digit sum
int digitSum(int num)
{
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
return sum;
}
// Delete all nodes which digit sum is an even value
void deleteEvenDigitSum(struct DoublyLL *dll)
{
if (dll->front == NULL)
{
return;
}
while (auxiliary != NULL)
{
if (digitSum(auxiliary->key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp->next;
if (temp == dll->front)
{
// When removing first node
dll->front = auxiliary;
}
if (dll->rear == temp)
{
// When deleting a last node
dll->rear = temp->back;
}
if (temp->back != NULL)
{
temp->back->next = auxiliary;
}
if (auxiliary != NULL)
{
auxiliary->back = temp->back;
}
// Free node
free(temp);
temp = NULL;
}
else
{
// Visit to next node
auxiliary = auxiliary->next;
}
}
}
int main()
{
printf(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
display(dll);
deleteEvenDigitSum(dll);
printf(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
display(dll);
return 0;
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````/*
Java Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
public int key;
{
this.back = back;
this.key = key;
this.next = null;
}
}
public class DoublyLL
{
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear.next = node;
}
this.rear = node;
}
public void display()
{
if (this.front == null)
{
return;
}
System.out.print(" Front to back \n");
while (temp != null)
{
System.out.print(" " + temp.key + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL");
temp = this.rear;
System.out.print("\n Back to front\n");
while (temp != null)
{
System.out.print(" " + temp.key + " →");
// Visit to back node
temp = temp.back;
}
System.out.print(" NULL\n");
}
// Digit sum
public int digitSum(int num)
{
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
return sum;
}
// Delete all nodes which digit sum is an even value
public void deleteEvenDigitSum()
{
if (this.front == null)
{
return;
}
while (auxiliary != null)
{
if (digitSum(auxiliary.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp.next;
if (temp == this.front)
{
// When removing first node
this.front = auxiliary;
}
if (this.rear == temp)
{
// When deleting a last node
this.rear = temp.back;
}
if (temp.back != null)
{
temp.back.next = auxiliary;
}
if (auxiliary != null)
{
auxiliary.back = temp.back;
}
temp = null;
}
else
{
// Visit to next node
auxiliary = auxiliary.next;
}
}
}
public static void main(String[] args)
{
DoublyLL dll = new DoublyLL();
System.out.print(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
System.out.print(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
dll.display();
}
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
public: int key;
{
this->back = back;
this->key = key;
this->next = NULL;
}
};
class DoublyLL
{
DoublyLL()
{
this->front = NULL;
this->rear = NULL;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (this->front == NULL)
{
this->front = node;
this->rear = node;
}
else
{
this->rear->next = node;
}
this->rear = node;
}
void display()
{
if (this->front == NULL)
{
cout << "\n Empty linked list\n";
return;
}
cout << " Front to back \n";
while (temp != NULL)
{
cout << " " << temp->key << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL";
temp = this->rear;
cout << "\n Back to front\n";
while (temp != NULL)
{
cout << " " << temp->key << " →";
// Visit to back node
temp = temp->back;
}
cout << " NULL\n";
}
// Digit sum
int digitSum(int num)
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
return sum;
}
// Delete all nodes which digit sum is an even value
void deleteEvenDigitSum()
{
if (this->front == NULL)
{
cout << "\n Empty linked list\n";
return;
}
while (auxiliary != NULL)
{
if (this->digitSum(auxiliary->key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp->next;
if (temp == this->front)
{
// When removing first node
this->front = auxiliary;
}
if (this->rear == temp)
{
// When deleting a last node
this->rear = temp->back;
}
if (temp->back != NULL)
{
temp->back->next = auxiliary;
}
if (auxiliary != NULL)
{
auxiliary->back = temp->back;
}
delete temp;
temp = NULL;
}
else
{
// Visit to next node
auxiliary = auxiliary->next;
}
}
}
};
int main()
{
DoublyLL dll = DoublyLL();
cout << " Before Deleting Even digit sum nodes\n";
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
cout << " After Delete even digit sum nodes \n";
//  23 → 1 → 10 → NULL
dll.display();
return 0;
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````// Include namespace system
using System;
/*
C# Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
public int key;
{
this.back = back;
this.key = key;
this.next = null;
}
}
public class DoublyLL
{
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear.next = node;
}
this.rear = node;
}
public void display()
{
if (this.front == null)
{
return;
}
Console.Write(" Front to back \n");
while (temp != null)
{
Console.Write(" " + temp.key + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL");
temp = this.rear;
Console.Write("\n Back to front\n");
while (temp != null)
{
Console.Write(" " + temp.key + " →");
// Visit to back node
temp = temp.back;
}
Console.Write(" NULL\n");
}
// Digit sum
public int digitSum(int num)
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
return sum;
}
// Delete all nodes which digit sum is an even value
public void deleteEvenDigitSum()
{
if (this.front == null)
{
return;
}
while (auxiliary != null)
{
if (digitSum(auxiliary.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp.next;
if (temp == this.front)
{
// When removing first node
this.front = auxiliary;
}
if (this.rear == temp)
{
// When deleting a last node
this.rear = temp.back;
}
if (temp.back != null)
{
temp.back.next = auxiliary;
}
if (auxiliary != null)
{
auxiliary.back = temp.back;
}
temp = null;
}
else
{
// Visit to next node
auxiliary = auxiliary.next;
}
}
}
public static void Main(String[] args)
{
DoublyLL dll = new DoublyLL();
Console.Write(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
Console.Write(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
dll.display();
}
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````<?php
/*
Php Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
public \$key;
public \$back;
public \$next;

function __construct(\$key, \$back)
{
\$this->back = \$back;
\$this->key = \$key;
\$this->next = null;
}
}
class DoublyLL
{
public \$front;
public \$rear;

function __construct()
{
\$this->front = null;
\$this->rear = null;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (\$this->front == null)
{
\$this->front = \$node;
\$this->rear = \$node;
}
else
{
\$this->rear->next = \$node;
}
\$this->rear = \$node;
}
public	function display()
{
if (\$this->front == null)
{
return;
}
echo " Front to back \n";
\$temp = \$this->front;
while (\$temp != null)
{
echo " ". \$temp->key ." →";
// Visit to next node
\$temp = \$temp->next;
}
echo " NULL";
\$temp = \$this->rear;
echo "\n Back to front\n";
while (\$temp != null)
{
echo " ". \$temp->key ." →";
// Visit to back node
\$temp = \$temp->back;
}
echo " NULL\n";
}
// Digit sum
public	function digitSum(\$num)
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
\$n = \$num;
\$sum = 0;
if (\$n < 0)
{
\$n = -\$n;
}
while (\$n > 0)
{
\$sum += (\$n % 10);
\$n = intval(\$n / 10);
}
return \$sum;
}
// Delete all nodes which digit sum is an even value
public	function deleteEvenDigitSum()
{
if (\$this->front == null)
{
return;
}
\$temp = null;
\$auxiliary = \$this->front;
while (\$auxiliary != null)
{
if (\$this->digitSum(\$auxiliary->key) % 2 == 0)
{
// Get the deleted node
\$temp = \$auxiliary;
// Visit to next node
\$auxiliary = \$temp->next;
if (\$temp == \$this->front)
{
// When removing first node
\$this->front = \$auxiliary;
}
if (\$this->rear == \$temp)
{
// When deleting a last node
\$this->rear = \$temp->back;
}
if (\$temp->back != null)
{
\$temp->back->next = \$auxiliary;
}
if (\$auxiliary != null)
{
\$auxiliary->back = \$temp->back;
}
\$temp = null;
}
else
{
// Visit to next node
\$auxiliary = \$auxiliary->next;
}
}
}
}

function main()
{
\$dll = new DoublyLL();
echo " Before Deleting Even digit sum nodes\n";
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
\$dll->display();
\$dll->deleteEvenDigitSum();
echo " After Delete even digit sum nodes \n";
//  23 → 1 → 10 → NULL
\$dll->display();
}
main();``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````/*
Node Js Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
constructor(key, back)
{
this.back = back;
this.key = key;
this.next = null;
}
}
class DoublyLL
{
constructor()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
var node = new LinkNode(data, this.rear);
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear.next = node;
}
this.rear = node;
}
display()
{
if (this.front == null)
{
return;
}
process.stdout.write(" Front to back \n");
var temp = this.front;
while (temp != null)
{
process.stdout.write(" " + temp.key + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL");
temp = this.rear;
process.stdout.write("\n Back to front\n");
while (temp != null)
{
process.stdout.write(" " + temp.key + " →");
// Visit to back node
temp = temp.back;
}
process.stdout.write(" NULL\n");
}
// Digit sum
digitSum(num)
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
var n = num;
var sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = parseInt(n / 10);
}
return sum;
}
// Delete all nodes which digit sum is an even value
deleteEvenDigitSum()
{
if (this.front == null)
{
return;
}
var temp = null;
var auxiliary = this.front;
while (auxiliary != null)
{
if (this.digitSum(auxiliary.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp.next;
if (temp == this.front)
{
// When removing first node
this.front = auxiliary;
}
if (this.rear == temp)
{
// When deleting a last node
this.rear = temp.back;
}
if (temp.back != null)
{
temp.back.next = auxiliary;
}
if (auxiliary != null)
{
auxiliary.back = temp.back;
}
temp = null;
}
else
{
// Visit to next node
auxiliary = auxiliary.next;
}
}
}
}

function main()
{
var dll = new DoublyLL();
process.stdout.write(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
process.stdout.write(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
dll.display();
}
main();``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````#   Python 3 Program
#   Remove all the even digit sum nodes from a doubly linked list

def __init__(self, key, back) :
self.back = back
self.key = key
self.next = None

class DoublyLL :

def __init__(self) :
self.front = None
self.rear = None

#  Handles the request to add new node at the end of linked list
#  Create dynamic node
if (self.front == None) :
self.front = node
self.rear = node
else :
self.rear.next = node

self.rear = node

def display(self) :
if (self.front == None) :
return

print(" Front to back ")
temp = self.front
while (temp != None) :
print("", temp.key ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL", end = "")
temp = self.rear
print("\n Back to front")
while (temp != None) :
print("", temp.key ,"→", end = "")
#  Visit to back node
temp = temp.back

print(" NULL")

#  Digit sum
def digitSum(self, num) :
n = num
sum = 0
if (n < 0) :
n = -n

while (n > 0) :
sum += (n % 10)
n = int(n / 10)

#  Return sum of each digit
#  Example (123) = 1 + 2 + 3 = 6
return sum

#  Delete all nodes which digit sum is an even value
def deleteEvenDigitSum(self) :
if (self.front == None) :
return

temp = None
auxiliary = self.front
while (auxiliary != None) :
if (self.digitSum(auxiliary.key) % 2 == 0) :
#  Get the deleted node
temp = auxiliary
#  Visit to next node
auxiliary = temp.next
if (temp == self.front) :
#  When removing first node
self.front = auxiliary

if (self.rear == temp) :
#  When deleting a last node
self.rear = temp.back

if (temp.back != None) :
temp.back.next = auxiliary

if (auxiliary != None) :
auxiliary.back = temp.back

temp = None
else :
#  Visit to next node
auxiliary = auxiliary.next

def main() :
dll = DoublyLL()
print(" Before Deleting Even digit sum nodes")
#  17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display()
dll.deleteEvenDigitSum()
print(" After Delete even digit sum nodes ")
#   23 → 1 → 10 → NULL
dll.display()

if __name__ == "__main__": main()``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````#   Ruby Program
#   Remove all the even digit sum nodes from a doubly linked list

attr_accessor :key, :back, :next

def initialize(key, back)
self.back = back
self.key = key
self.next = nil
end

end

class DoublyLL
# Define the accessor and reader of class DoublyLL
attr_accessor :front, :rear

def initialize()
self.front = nil
self.rear = nil
end

#  Handles the request to add new node at the end of linked list
#  Create dynamic node
if (self.front == nil)
self.front = node
self.rear = node
else
self.rear.next = node
end

self.rear = node
end

def display()
if (self.front == nil)
return
end

print(" Front to back \n")
temp = self.front
while (temp != nil)
print(" ", temp.key ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL")
temp = self.rear
print("\n Back to front\n")
while (temp != nil)
print(" ", temp.key ," →")
#  Visit to back node
temp = temp.back
end

print(" NULL\n")
end

#  Digit sum
def digitSum(num)
n = num
sum = 0
if (n < 0)
n = -n
end

while (n > 0)
sum += (n % 10)
n /= 10
end

#  Return sum of each digit
#  Example (123) = 1 + 2 + 3 = 6
return sum
end

#  Delete all nodes which digit sum is an even value
def deleteEvenDigitSum()
if (self.front == nil)
return
end

temp = nil
auxiliary = self.front
while (auxiliary != nil)
if (self.digitSum(auxiliary.key) % 2 == 0)
#  Get the deleted node
temp = auxiliary
#  Visit to next node
auxiliary = temp.next
if (temp == self.front)
#  When removing first node
self.front = auxiliary
end

if (self.rear == temp)
#  When deleting a last node
self.rear = temp.back
end

if (temp.back != nil)
temp.back.next = auxiliary
end

if (auxiliary != nil)
auxiliary.back = temp.back
end

temp = nil
else
#  Visit to next node
auxiliary = auxiliary.next
end

end

end

end

def main()
dll = DoublyLL.new()
print(" Before Deleting Even digit sum nodes\n")
#  17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display()
dll.deleteEvenDigitSum()
print(" After Delete even digit sum nodes \n")
#   23 → 1 → 10 → NULL
dll.display()
end

main()``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL
``````
``````/*
Scala Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
{
this(key, back, null);
}
}
{
def this()
{
this(null, null);
}
// Handles the request to add new node at the end of linked list
def addNode(data: Int): Unit = {
// Create dynamic node
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear.next = node;
}
this.rear = node;
}
def display(): Unit = {
if (this.front == null)
{
return;
}
print(" Front to back \n");
while (temp != null)
{
print(" " + temp.key + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL");
temp = this.rear;
print("\n Back to front\n");
while (temp != null)
{
print(" " + temp.key + " →");
// Visit to back node
temp = temp.back;
}
print(" NULL\n");
}
// Digit sum
def digitSum(num: Int): Int = {
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = (n / 10).toInt;
}
return sum;
}
// Delete all nodes which digit sum is an even value
def deleteEvenDigitSum(): Unit = {
if (this.front == null)
{
return;
}
while (auxiliary != null)
{
if (this.digitSum(auxiliary.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp.next;
if (temp == this.front)
{
// When removing first node
this.front = auxiliary;
}
if (this.rear == temp)
{
// When deleting a last node
this.rear = temp.back;
}
if (temp.back != null)
{
temp.back.next = auxiliary;
}
if (auxiliary != null)
{
auxiliary.back = temp.back;
}
temp = null;
}
else
{
// Visit to next node
auxiliary = auxiliary.next;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var dll: DoublyLL = new DoublyLL();
print(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
print(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
dll.display();
}
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````/*
Swift 4 Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
var key: Int;
init(_ key: Int, _ back: LinkNode? )
{
self.back = back;
self.key = key;
self.next = nil;
}
}
class DoublyLL
{
init()
{
self.front = nil;
self.rear = nil;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (self.front == nil)
{
self.front = node;
self.rear = node;
}
else
{
self.rear!.next = node;
}
self.rear = node;
}
func display()
{
if (self.front == nil)
{
return;
}
print(" Front to back ");
while (temp  != nil)
{
print("", temp!.key ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL", terminator: "");
temp = self.rear;
print("\n Back to front");
while (temp  != nil)
{
print("", temp!.key ,"→", terminator: "");
// Visit to back node
temp = temp!.back;
}
print(" NULL");
}
// Digit sum
func digitSum(_ num: Int)->Int
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
return sum;
}
// Delete all nodes which digit sum is an even value
func deleteEvenDigitSum()
{
if (self.front == nil)
{
return;
}
while (auxiliary  != nil)
{
if (self.digitSum(auxiliary!.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp!.next;
if (temp === self.front)
{
// When removing first node
self.front = auxiliary;
}
if (self.rear === temp)
{
// When deleting a last node
self.rear = temp!.back;
}
if (temp!.back  != nil)
{
temp!.back!.next = auxiliary;
}
if (auxiliary  != nil)
{
auxiliary!.back = temp!.back;
}
temp = nil;
}
else
{
// Visit to next node
auxiliary = auxiliary!.next;
}
}
}
}
func main()
{
let dll: DoublyLL = DoublyLL();
print(" Before Deleting Even digit sum nodes");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
print(" After Delete even digit sum nodes ");
//  23 → 1 → 10 → NULL
dll.display();
}
main();``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````
``````/*
Kotlin Program
Remove all the even digit sum nodes from a doubly linked list
*/
{
var key: Int;
constructor(key: Int, back: LinkNode ? )
{
this.back = back;
this.key = key;
this.next = null;
}
}
class DoublyLL
{
constructor()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
{
// Create dynamic node
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear?.next = node;
}
this.rear = node;
}
fun display(): Unit
{
if (this.front == null)
{
return;
}
print(" Front to back \n");
var temp: LinkNode ? = this.front;
while (temp != null)
{
print(" " + temp.key + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL");
temp = this.rear;
print("\n Back to front\n");
while (temp != null)
{
print(" " + temp.key + " →");
// Visit to back node
temp = temp.back;
}
print(" NULL\n");
}
// Digit sum
fun digitSum(num: Int): Int
{
// Return sum of each digit
// Example (123) = 1 + 2 + 3 = 6
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n /= 10;
}
return sum;
}
// Delete all nodes which digit sum is an even value
fun deleteEvenDigitSum(): Unit
{
if (this.front == null)
{
return;
}
var auxiliary: LinkNode ? = this.front;
while (auxiliary != null)
{
if (this.digitSum(auxiliary.key) % 2 == 0)
{
// Get the deleted node
temp = auxiliary;
// Visit to next node
auxiliary = temp.next;
if (temp == this.front)
{
// When removing first node
this.front = auxiliary;
}
if (this.rear == temp)
{
// When deleting a last node
this.rear = temp.back;
}
if (temp.back != null)
{
temp.back?.next = auxiliary;
}
if (auxiliary != null)
{
auxiliary.back = temp.back;
}
}
else
{
// Visit to next node
auxiliary = auxiliary.next;
}
}
}
}
fun main(args: Array <String> ): Unit
{
var dll: DoublyLL = DoublyLL();
print(" Before Deleting Even digit sum nodes\n");
// 17 → 4 → 23 → 1 → 13 → 10 → NULL
dll.display();
dll.deleteEvenDigitSum();
print(" After Delete even digit sum nodes \n");
//  23 → 1 → 10 → NULL
dll.display();
}``````

#### Output

`````` Before Deleting Even digit sum nodes
Front to back
17 → 4 → 23 → 1 → 13 → 10 → NULL
Back to front
10 → 13 → 1 → 23 → 4 → 17 → NULL
After Delete even digit sum nodes
Front to back
23 → 1 → 10 → NULL
Back to front
10 → 1 → 23 → NULL``````

## Time Complexity

• The `digitSum` function takes O(log(n)) time to calculate the digit sum of a number n.
• The `deleteEvenDigitSum` function iterates through the entire linked list, and for each node, it performs constant time operations to adjust pointers and free memory.
• Overall, the time complexity of removing nodes with even digit sums from the linked list is O(n * log(n)), where n is the number of nodes in the linked list.

## 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.

Categories
Relative Post