Solution Review: Deletion by Value
Explore how to delete a node by value in a linked list through a clear step-by-step algorithm. Learn to manage nodes efficiently by tracking current and previous nodes and understand the time complexity involved. This lesson teaches practical manipulation of linked lists to prepare you for coding interviews.
We'll cover the following...
We'll cover the following...
Solution #
C#
using System;namespace chapter_3{public class LinkedList{public class Node{internal int data; //Data to store (could be int,string,object etc)internal Node nextElement; //Pointer to next elementpublic Node(){//Constructor to initialize nextElement of newlyCreated NodenextElement = null;}};Node head;public LinkedList(){head = null;}public Node GetHead(){return head;}bool IsEmpty(){if (head == null) //Check whether the head points to nullreturn true;elsereturn false;}public bool PrintList(){if (IsEmpty()){Console.Write("List is Empty!");return false;}Node temp = head;Console.Write("List : ");while (temp != null){Console.Write(temp.data + "->");temp = temp.nextElement;}Console.WriteLine("null ");return true;}public void InsertAtHead(int value){Node newNode = new Node();newNode.data = value;newNode.nextElement = head; //Linking newNode to head's nextNodehead = newNode;Console.Write(value + " Inserted! ");}public string Elements(){string elementsList = "";Node start = head;while (start != null){elementsList += start.data.ToString();elementsList += "->";start = start.nextElement;}elementsList += "null";return elementsList;}public void InsertAtTail(int value){if (IsEmpty()){ // inserting first element in listInsertAtHead(value); // head will point to first element of the list}else{Node newNode = new Node(); // creating new nodeNode last = head; // last pointing at the head of the listwhile (last.nextElement != null){ // traversing through the listlast = last.nextElement;}newNode.data = value;Console.Write(value + " Inserted! ");newNode.nextElement = null; // point last's nextElement to nullptrlast.nextElement = newNode; // adding the newNode at the end of the list}}// function to check if element exists in the listpublic bool Search(int value){Node temp = head; // pointing temp to the headwhile (temp != null){if (temp.data == value){ // if passed value matches with temp's datareturn true;}temp = temp.nextElement; // pointig to temp's nextElement}return false; // if not found}public bool Delete(int value){bool deleted = false; //returns true if the node is deleted, false otherwiseif (IsEmpty()){ //check if the list is emptyConsole.WriteLine("List is Empty");return deleted; //deleted will be false}//if list is not empty, start traversing it from the headNode currentNode = head; //currentNode to traverse the listNode previousNode = null; //previousNode starts from nullif (currentNode.data == value){ // deleting value of headdeleted = DeleteAtHead();Console.WriteLine(value + " deleted!");deleted = true; // true because value found and deletedreturn deleted; //returns true if the node is deleted}previousNode = currentNode;currentNode = currentNode.nextElement; // pointing current to current's nextElement//Traversing/Searching for Node to Deletewhile (currentNode != null){//Node to delete is foundif (value == currentNode.data){// pointing previousNode's nextElement to currentNode's nextElementpreviousNode.nextElement = currentNode.nextElement;// delete currentNode;currentNode = previousNode.nextElement;deleted = true;break;}previousNode = currentNode;currentNode = currentNode.nextElement; // pointing current to current's nextElement}//deleted is true only when value is found and deletedif (deleted == false){Console.WriteLine(value + " does not exist!");}else{Console.WriteLine(value + " deleted!");}return deleted;} //end of delete()bool DeleteAtHead(){if (IsEmpty()){ // check if list is emptyConsole.WriteLine("List is Empty");return false;}//if list is not empty, start traversing it from the headhead = head.nextElement; //nextNode point to head's nextElementreturn true;}}}
The algorithm is similar to DeleteAtHead. The ...