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
- Start iterating through the linked list from the front.
- Calculate the digit sum of the current node's key using the
digitSum
function. - 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.
- Move to the next node.
- 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>
struct LinkNode
{
int key;
struct LinkNode *back;
struct LinkNode *next;
};
struct DoublyLL
{
struct LinkNode *front;
struct LinkNode *rear;
};
// Returns a new linked list
struct DoublyLL *createLinkedList()
{
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
struct LinkNode *newNode(int key, struct LinkNode *back)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
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;
}
// Display linked list element
void display(struct DoublyLL *dll)
{
if (dll->front == NULL)
{
printf("\n Empty linked list\n");
return;
}
printf(" Front to back \n");
struct LinkNode *temp = dll->front;
// iterating linked list elements
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)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = NULL;
struct LinkNode *auxiliary = dll->front;
// iterate linked list node
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()
{
struct DoublyLL *dll = createLinkedList();
addNode(dll, 17);
addNode(dll, 4);
addNode(dll, 23);
addNode(dll, 1);
addNode(dll, 13);
addNode(dll, 10);
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
*/
class LinkNode
{
public int key;
public LinkNode back;
public LinkNode next;
public LinkNode(int key, LinkNode back)
{
this.back = back;
this.key = key;
this.next = null;
}
}
public class DoublyLL
{
public LinkNode front;
public LinkNode rear;
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
public void addNode(int data)
{
// Create dynamic node
LinkNode 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 linked list element
public void display()
{
if (this.front == null)
{
System.out.print("\n Empty linked list\n");
return;
}
System.out.print(" Front to back \n");
LinkNode temp = this.front;
// iterating linked list elements
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)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = null;
LinkNode auxiliary = this.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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
*/
class LinkNode
{
public: int key;
LinkNode *back;
LinkNode *next;
LinkNode(int key, LinkNode *back)
{
this->back = back;
this->key = key;
this->next = NULL;
}
};
class DoublyLL
{
public: LinkNode *front;
LinkNode *rear;
DoublyLL()
{
this->front = NULL;
this->rear = NULL;
}
// Handles the request to add new node at the end of linked list
void addNode(int data)
{
// Create dynamic node
LinkNode *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 linked list element
void display()
{
if (this->front == NULL)
{
cout << "\n Empty linked list\n";
return;
}
cout << " Front to back \n";
LinkNode *temp = this->front;
// iterating linked list elements
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;
}
LinkNode *temp = NULL;
LinkNode *auxiliary = this->front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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 class LinkNode
{
public int key;
public LinkNode back;
public LinkNode next;
public LinkNode(int key, LinkNode back)
{
this.back = back;
this.key = key;
this.next = null;
}
}
public class DoublyLL
{
public LinkNode front;
public LinkNode rear;
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
public void addNode(int data)
{
// Create dynamic node
LinkNode 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 linked list element
public void display()
{
if (this.front == null)
{
Console.Write("\n Empty linked list\n");
return;
}
Console.Write(" Front to back \n");
LinkNode temp = this.front;
// iterating linked list elements
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)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = null;
LinkNode auxiliary = this.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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
*/
class LinkNode
{
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
public function addNode($data)
{
// Create dynamic node
$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 linked list element
public function display()
{
if ($this->front == null)
{
echo "\n Empty linked list\n";
return;
}
echo " Front to back \n";
$temp = $this->front;
// iterating linked list elements
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)
{
echo "\n Empty linked list\n";
return;
}
$temp = null;
$auxiliary = $this->front;
// iterate linked list node
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();
$dll->addNode(17);
$dll->addNode(4);
$dll->addNode(23);
$dll->addNode(1);
$dll->addNode(13);
$dll->addNode(10);
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
*/
class LinkNode
{
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
addNode(data)
{
// 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 linked list element
display()
{
if (this.front == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
process.stdout.write(" Front to back \n");
var temp = this.front;
// iterating linked list elements
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)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = null;
var auxiliary = this.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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
class LinkNode :
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
def addNode(self, data) :
# Create dynamic node
node = LinkNode(data, self.rear)
if (self.front == None) :
self.front = node
self.rear = node
else :
self.rear.next = node
self.rear = node
# Display linked list element
def display(self) :
if (self.front == None) :
print("\n Empty linked list")
return
print(" Front to back ")
temp = self.front
# iterating linked list elements
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) :
print("\n Empty linked list")
return
temp = None
auxiliary = self.front
# iterate linked list node
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()
dll.addNode(17)
dll.addNode(4)
dll.addNode(23)
dll.addNode(1)
dll.addNode(13)
dll.addNode(10)
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
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :key, :back, :next
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_reader :front, :rear
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
def addNode(data)
# Create dynamic node
node = LinkNode.new(data, self.rear)
if (self.front == nil)
self.front = node
self.rear = node
else
self.rear.next = node
end
self.rear = node
end
# Display linked list element
def display()
if (self.front == nil)
print("\n Empty linked list\n")
return
end
print(" Front to back \n")
temp = self.front
# iterating linked list elements
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)
print("\n Empty linked list\n")
return
end
temp = nil
auxiliary = self.front
# iterate linked list node
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()
dll.addNode(17)
dll.addNode(4)
dll.addNode(23)
dll.addNode(1)
dll.addNode(13)
dll.addNode(10)
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
*/
class LinkNode(var key: Int , var back: LinkNode , var next: LinkNode)
{
def this(key: Int, back: LinkNode)
{
this(key, back, null);
}
}
class DoublyLL(var front: LinkNode , var rear: LinkNode)
{
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
var node: LinkNode = new LinkNode(data, this.rear);
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear.next = node;
}
this.rear = node;
}
// Display linked list element
def display(): Unit = {
if (this.front == null)
{
print("\n Empty linked list\n");
return;
}
print(" Front to back \n");
var temp: LinkNode = this.front;
// iterating linked list elements
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)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = null;
var auxiliary: LinkNode = this.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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
*/
class LinkNode
{
var key: Int;
var back: LinkNode? ;
var next: LinkNode? ;
init(_ key: Int, _ back: LinkNode? )
{
self.back = back;
self.key = key;
self.next = nil;
}
}
class DoublyLL
{
var front: LinkNode? ;
var rear: LinkNode? ;
init()
{
self.front = nil;
self.rear = nil;
}
// Handles the request to add new node at the end of linked list
func addNode(_ data: Int)
{
// Create dynamic node
let node: LinkNode? = LinkNode(data, self.rear);
if (self.front == nil)
{
self.front = node;
self.rear = node;
}
else
{
self.rear!.next = node;
}
self.rear = node;
}
// Display linked list element
func display()
{
if (self.front == nil)
{
print("\n Empty linked list");
return;
}
print(" Front to back ");
var temp: LinkNode? = self.front;
// iterating linked list elements
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)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = nil;
var auxiliary: LinkNode? = self.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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
*/
class LinkNode
{
var key: Int;
var back: LinkNode ? ;
var next: LinkNode ? ;
constructor(key: Int, back: LinkNode ? )
{
this.back = back;
this.key = key;
this.next = null;
}
}
class DoublyLL
{
var front: LinkNode ? ;
var rear: LinkNode ? ;
constructor()
{
this.front = null;
this.rear = null;
}
// Handles the request to add new node at the end of linked list
fun addNode(data: Int): Unit
{
// Create dynamic node
var node: LinkNode ? = LinkNode(data, this.rear);
if (this.front == null)
{
this.front = node;
this.rear = node;
}
else
{
this.rear?.next = node;
}
this.rear = node;
}
// Display linked list element
fun display(): Unit
{
if (this.front == null)
{
print("\n Empty linked list\n");
return;
}
print(" Front to back \n");
var temp: LinkNode ? = this.front;
// iterating linked list elements
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)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ?;
var auxiliary: LinkNode ? = this.front;
// iterate linked list node
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();
dll.addNode(17);
dll.addNode(4);
dll.addNode(23);
dll.addNode(1);
dll.addNode(13);
dll.addNode(10);
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.
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