Doubly Linked List - Delete odd nodes
Deleting odd nodes of a doubly linked list requires traverse through the list and deleting odd nodes one by one. If the list is not null then release the head and make next of head as new head. If the new head is not null then make the next of head as null and create two nodes - evenNode and oddNode. Make evenNode to the first even node of list and oddNode to second odd node of the list (3rd node in the original list). If both are not null, delete the oddNode and adjust links. Move both nodes to next set of even-odd nodes. Repeat the process till the any or both nodes become null.
The function deleteOddNodes is created for this purpose. It is a 5-step process.
void deleteOddNodes() { if(head != NULL) { //1. if head is not null, make next of head as // new head and delete previous head Node* temp = head; head = head->next; free(temp); if(head != NULL) { //2. if the new head is not make prev of head as // null and create nodes - evenNode and oddNode head->prev = NULL; Node* evenNode = head; Node* oddNode = head->next; while(evenNode != NULL && oddNode != NULL) { //3. while evenNode and oddNode are not null // make next of evenNode as next of oddNode // and free oddNode evenNode->next = oddNode->next; free(oddNode); //4. and make temp as evenNode and evenNode as // next of evenNode temp = evenNode; evenNode = evenNode->next; //5. Update prev link, evenNode and oddNode if(evenNode != NULL) { evenNode->prev = temp; oddNode = evenNode->next; } } } } }
void deleteOddNodes(struct Node** head_ref) { if(*head_ref != NULL) { //1. if head is not null, make next of head as // new head and delete previous head struct Node* temp = *head_ref; *head_ref = (*head_ref)->next; free(temp); if(*head_ref != NULL) { //2. if the new head is not make prev of head as // null and create nodes - evenNode and oddNode (*head_ref)->prev = NULL; struct Node* evenNode = *head_ref; struct Node* oddNode = (*head_ref)->next; while(evenNode != NULL && oddNode != NULL) { //3. while evenNode and oddNode are not null // make next of evenNode as next of oddNode // and free oddNode evenNode->next = oddNode->next; free(oddNode); //4. and make temp as evenNode and evenNode as // next of evenNode temp = evenNode; evenNode = evenNode->next; //5. Update prev link, evenNode and oddNode if(evenNode != NULL) { evenNode->prev = temp; oddNode = evenNode->next; } } } } }
def deleteOddNodes(self): if (self.head != None): #1. if head is not null, make next of head as # new head and delete previous head temp = self.head self.head = self.head.next temp = None if (self.head != None): #2. if the new head is not make prev of head as # null and create nodes - evenNode and oddNode self.head.prev = None evenNode = self.head oddNode = self.head.next while(evenNode != None and oddNode != None): #3. while evenNode and oddNode are not null # make next of evenNode as next of oddNode # and free oddNode evenNode.next = oddNode.next oddNode = None #4. and make temp as evenNode and evenNode as # next of evenNode temp = evenNode evenNode = evenNode.next #5. Update prev link, evenNode and oddNode if(evenNode != None): evenNode.prev = temp oddNode = evenNode.next
void deleteOddNodes() { if(this.head != null) { //1. if head is not null, make next of head as // new head and delete previous head Node temp = this.head; this.head = this.head.next; temp = null; if(this.head != null) { //2. if the new head is not make prev of head as // null and create nodes - evenNode and oddNode this.head.prev = null; Node evenNode = this.head; Node oddNode = this.head.next; while(evenNode != null && oddNode != null) { //3. while evenNode and oddNode are not null // make next of evenNode as next of oddNode // and free oddNode evenNode.next = oddNode.next; oddNode = null; //4. and make temp as evenNode and evenNode as // next of evenNode temp = evenNode; evenNode = evenNode.next; //5. Update prev link, evenNode and oddNode if(evenNode != null) { evenNode.prev = temp; oddNode = evenNode.next; } } } } }
public void deleteOddNodes() { if(this.head != null) { //1. if head is not null, make next of head as // new head and delete previous head Node temp = this.head; this.head = this.head.next; temp = null; if(this.head != null) { //2. if the new head is not make prev of head as // null and create nodes - evenNode and oddNode this.head.prev = null; Node evenNode = this.head; Node oddNode = this.head.next; while(evenNode != null && oddNode != null) { //3. while evenNode and oddNode are not null // make next of evenNode as next of oddNode // and free oddNode evenNode.next = oddNode.next; oddNode = null; //4. and make temp as evenNode and evenNode as // next of evenNode temp = evenNode; evenNode = evenNode.next; //5. Update prev link, evenNode and oddNode if(evenNode != null) { evenNode.prev = temp; oddNode = evenNode.next; } } } } }
public function deleteOddNodes() { if($this->head != null) { //1. if head is not null, make next of head as // new head and delete previous head $temp = $this->head; $this->head = $this->head->next; $temp = null; if($this->head != null) { //2. if the new head is not make prev of head as // null and create nodes - evenNode and oddNode $this->head->prev = null; $evenNode = $this->head; $oddNode = $this->head->next; while($evenNode != null && $oddNode != null) { //3. while evenNode and oddNode are not null // make next of evenNode as next of oddNode // and free oddNode $evenNode->next = $oddNode->next; $oddNode = null; //4. and make temp as evenNode and evenNode as // next of evenNode $temp = $evenNode; $evenNode = $evenNode->next; //5. Update prev link, evenNode and oddNode if($evenNode != null) { $evenNode->prev = $temp; $oddNode = $evenNode->next; } } } } }
The below is a complete program that uses above discussed concept of deleting odd nodes of a doubly linked list.
#include <iostream> using namespace std; //node structure struct Node { int data; Node* next; Node* prev; }; class LinkedList { private: Node* head; public: LinkedList(){ head = NULL; } //Add new element at the end of the list void push_back(int newElement) { Node* newNode = new Node(); newNode->data = newElement; newNode->next = NULL; newNode->prev = NULL; if(head == NULL) { head = newNode; } else { Node* temp = head; while(temp->next != NULL) temp = temp->next; temp->next = newNode; newNode->prev = temp; } } //delete odd nodes of the list void deleteOddNodes() { if(head != NULL) { Node* temp = head; head = head->next; free(temp); if(head != NULL) { head->prev = NULL; Node* evenNode = head; Node* oddNode = head->next; while(evenNode != NULL && oddNode != NULL) { evenNode->next = oddNode->next; free(oddNode); temp = evenNode; evenNode = evenNode->next; if(evenNode != NULL) { evenNode->prev = temp; oddNode = evenNode->next; } } } } } //display the content of the list void PrintList() { Node* temp = head; if(temp != NULL) { cout<<"The list contains: "; while(temp != NULL) { cout<<temp->data<<" "; temp = temp->next; } cout<<"\n"; } else { cout<<"The list is empty.\n"; } } }; // test the code int main() { LinkedList MyList; //Add five elements in the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.push_back(40); MyList.push_back(50); //Display the content of the list. MyList.PrintList(); //delete odd nodes of the list MyList.deleteOddNodes(); cout<<"After deleting odd nodes.\n"; //Display the content of the list. MyList.PrintList(); return 0; }
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40
#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; struct Node* prev; }; //Add new element at the end of the list void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement; newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) { *head_ref = newNode; } else { temp = *head_ref; while(temp->next != NULL) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } } //delete odd nodes of the list void deleteOddNodes(struct Node** head_ref) { if(*head_ref != NULL) { struct Node* temp = *head_ref; *head_ref = (*head_ref)->next; free(temp); if(*head_ref != NULL) { (*head_ref)->prev = NULL; struct Node* evenNode = *head_ref; struct Node* oddNode = (*head_ref)->next; while(evenNode != NULL && oddNode != NULL) { evenNode->next = oddNode->next; free(oddNode); temp = evenNode; evenNode = evenNode->next; if(evenNode != NULL) { evenNode->prev = temp; oddNode = evenNode->next; } } } } } //display the content of the list void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) { printf("The list contains: "); while (temp != NULL) { printf("%i ",temp->data); temp = temp->next; } printf("\n"); } else { printf("The list is empty.\n"); } } // test the code int main() { struct Node* MyList = NULL; //Add five elements in the list. push_back(&MyList, 10); push_back(&MyList, 20); push_back(&MyList, 30); push_back(&MyList, 40); push_back(&MyList, 50); //Display the content of the list. PrintList(MyList); //delete odd nodes of the list deleteOddNodes(&MyList); printf("After deleting odd nodes.\n"); //Display the content of the list. PrintList(MyList); return 0; }
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40
# node structure class Node: def __init__(self, data): self.data = data self.next = None self.prev = None #class Linked List class LinkedList: def __init__(self): self.head = None #Add new element at the end of the list def push_back(self, newElement): newNode = Node(newElement) if(self.head == None): self.head = newNode return else: temp = self.head while(temp.next != None): temp = temp.next temp.next = newNode newNode.prev = temp #delete odd nodes of the list def deleteOddNodes(self): if (self.head != None): temp = self.head self.head = self.head.next temp = None if (self.head != None): self.head.prev = None evenNode = self.head oddNode = self.head.next while(evenNode != None and oddNode != None): evenNode.next = oddNode.next oddNode = None temp = evenNode evenNode = evenNode.next if(evenNode != None): evenNode.prev = temp oddNode = evenNode.next #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (temp != None): print(temp.data, end=" ") temp = temp.next print() else: print("The list is empty.") # test the code MyList = LinkedList() #Add five elements in the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.push_back(40) MyList.push_back(50) #Display the content of the list. MyList.PrintList() #delete odd nodes of the list MyList.deleteOddNodes() print("After deleting odd nodes.") #Display the content of the list. MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40
//node structure class Node { int data; Node next; Node prev; }; class LinkedList { Node head; LinkedList(){ head = null; } //Add new element at the end of the list void push_back(int newElement) { Node newNode = new Node(); newNode.data = newElement; newNode.next = null; newNode.prev = null; if(head == null) { head = newNode; } else { Node temp = new Node(); temp = head; while(temp.next != null) temp = temp.next; temp.next = newNode; newNode.prev = temp; } } //delete odd nodes of the list void deleteOddNodes() { if(this.head != null) { Node temp = this.head; this.head = this.head.next; temp = null; if(this.head != null) { this.head.prev = null; Node evenNode = this.head; Node oddNode = this.head.next; while(evenNode != null && oddNode != null) { evenNode.next = oddNode.next; oddNode = null; temp = evenNode; evenNode = evenNode.next; if(evenNode != null) { evenNode.prev = temp; oddNode = evenNode.next; } } } } } //display the content of the list void PrintList() { Node temp = new Node(); temp = this.head; if(temp != null) { System.out.print("The list contains: "); while(temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } else { System.out.println("The list is empty."); } } }; // test the code public class Implementation { public static void main(String[] args) { LinkedList MyList = new LinkedList(); //Add five elements in the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.push_back(40); MyList.push_back(50); //Display the content of the list. MyList.PrintList(); //delete odd nodes of the list MyList.deleteOddNodes(); System.out.println("After deleting odd nodes."); //Display the content of the list. MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40
using System; //node structure class Node { public int data; public Node next; public Node prev; }; class LinkedList { Node head; public LinkedList(){ head = null; } //Add new element at the end of the list public void push_back(int newElement) { Node newNode = new Node(); newNode.data = newElement; newNode.next = null; newNode.prev = null; if(head == null) { head = newNode; } else { Node temp = new Node(); temp = head; while(temp.next != null) temp = temp.next; temp.next = newNode; newNode.prev = temp; } } //delete odd nodes of the list public void deleteOddNodes() { if(this.head != null) { Node temp = this.head; this.head = this.head.next; temp = null; if(this.head != null) { this.head.prev = null; Node evenNode = this.head; Node oddNode = this.head.next; while(evenNode != null && oddNode != null) { evenNode.next = oddNode.next; oddNode = null; temp = evenNode; evenNode = evenNode.next; if(evenNode != null) { evenNode.prev = temp; oddNode = evenNode.next; } } } } } //display the content of the list public void PrintList() { Node temp = new Node(); temp = this.head; if(temp != null) { Console.Write("The list contains: "); while(temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } else { Console.WriteLine("The list is empty."); } } }; // test the code class Implementation { static void Main(string[] args) { LinkedList MyList = new LinkedList(); //Add five elements in the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.push_back(40); MyList.push_back(50); //Display the content of the list. MyList.PrintList(); //delete odd nodes of the list MyList.deleteOddNodes(); Console.WriteLine("After deleting odd nodes."); //Display the content of the list. MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40
<?php //node structure class Node { public $data; public $next; public $prev; } class LinkedList { public $head; public function __construct(){ $this->head = null; } //Add new element at the end of the list public function push_back($newElement) { $newNode = new Node(); $newNode->data = $newElement; $newNode->next = null; $newNode->prev = null; if($this->head == null) { $this->head = $newNode; } else { $temp = new Node(); $temp = $this->head; while($temp->next != null) { $temp = $temp->next; } $temp->next = $newNode; $newNode->prev = $temp; } } //delete odd nodes of the list public function deleteOddNodes() { if($this->head != null) { $temp = $this->head; $this->head = $this->head->next; $temp = null; if($this->head != null) { $this->head->prev = null; $evenNode = $this->head; $oddNode = $this->head->next; while($evenNode != null && $oddNode != null) { $evenNode->next = $oddNode->next; $oddNode = null; $temp = $evenNode; $evenNode = $evenNode->next; if($evenNode != null) { $evenNode->prev = $temp; $oddNode = $evenNode->next; } } } } } //display the content of the list public function PrintList() { $temp = new Node(); $temp = $this->head; if($temp != null) { echo "The list contains: "; while($temp != null) { echo $temp->data." "; $temp = $temp->next; } echo "\n"; } else { echo "The list is empty.\n"; } } }; // test the code $MyList = new LinkedList(); //Add five elements in the list. $MyList->push_back(10); $MyList->push_back(20); $MyList->push_back(30); $MyList->push_back(40); $MyList->push_back(50); //Display the content of the list. $MyList->PrintList(); //delete odd nodes of the list $MyList->deleteOddNodes(); echo "After deleting odd nodes.\n"; //Display the content of the list. $MyList->PrintList(); ?>
The above code will give the following output:
The list contains: 10 20 30 40 50 After deleting odd nodes. The list contains: 20 40