Posted on by Kalkicode
Code Doubly linked list

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>

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.

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