Search⌘ K
AI Features

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

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 element
public Node()
{
//Constructor to initialize nextElement of newlyCreated Node
nextElement = null;
}
};
Node head;
public LinkedList()
{
head = null;
}
public Node GetHead()
{
return head;
}
bool IsEmpty()
{
if (head == null) //Check whether the head points to null
return true;
else
return 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 nextNode
head = 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 list
InsertAtHead(value); // head will point to first element of the list
}
else
{
Node newNode = new Node(); // creating new node
Node last = head; // last pointing at the head of the list
while (last.nextElement != null)
{ // traversing through the list
last = last.nextElement;
}
newNode.data = value;
Console.Write(value + " Inserted! ");
newNode.nextElement = null; // point last's nextElement to nullptr
last.nextElement = newNode; // adding the newNode at the end of the list
}
}
// function to check if element exists in the list
public bool Search(int value)
{
Node temp = head; // pointing temp to the head
while (temp != null)
{
if (temp.data == value)
{ // if passed value matches with temp's data
return 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 otherwise
if (IsEmpty())
{ //check if the list is empty
Console.WriteLine("List is Empty");
return deleted; //deleted will be false
}
//if list is not empty, start traversing it from the head
Node currentNode = head; //currentNode to traverse the list
Node previousNode = null; //previousNode starts from null
if (currentNode.data == value)
{ // deleting value of head
deleted = DeleteAtHead();
Console.WriteLine(value + " deleted!");
deleted = true; // true because value found and deleted
return deleted; //returns true if the node is deleted
}
previousNode = currentNode;
currentNode = currentNode.nextElement; // pointing current to current's nextElement
//Traversing/Searching for Node to Delete
while (currentNode != null)
{
//Node to delete is found
if (value == currentNode.data)
{
// pointing previousNode's nextElement to currentNode's nextElement
previousNode.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 deleted
if (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 empty
Console.WriteLine("List is Empty");
return false;
}
//if list is not empty, start traversing it from the head
head = head.nextElement; //nextNode point to head's nextElement
return true;
}
}
}

The algorithm is similar to DeleteAtHead. The ...