Gfilui

You need to remove the first element which contains a given value from a doubly linked list.

I created two solutions since I find the edge case of removing the first element to be problematic. So I solved it using 2 approaches:

1. using void function and ref


2. using return value

using System;
using System.Diagnostics;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LinkedListQuestions

 //remove the first element in the list which equals to value

 [TestClass]
 public class DoublyLinkedListTest
 
 private Node head;
 [TestInitialize]
 public void InitList()
 
 head = new Node();
 Node two = new Node();
 Node three = new Node();
 Node four = new Node();
 head.Value = 1;
 head.Next = two;

 two.Value = 2;
 two.Prev = head;
 two.Next = three;

 three.Value = 3;
 three.Next = four;
 three.Prev = two;

 four.Value = 4;
 four.Prev = three;

 

 [TestMethod]
 public void RemoveValueRefFromMiddleOfListTest()
 

 DoublyLinkedListHelper.RemoveRefElement(ref head, 3);
 Assert.AreEqual(1, head.Value);
 Assert.AreEqual(2, head.Next.Value);
 Assert.AreEqual(4, head.Next.Next.Value);
 

 [TestMethod]
 public void RemoveValueFromMiddleOfListTest()
 

 head = DoublyLinkedListHelper.RemoveElement(head, 3);
 Assert.AreEqual(1,head.Value);
 Assert.AreEqual(2, head.Next.Value);
 Assert.AreEqual(4, head.Next.Next.Value);
 

 [TestMethod]
 public void RemoveValueRefFromTopOfListTest()
 

 DoublyLinkedListHelper.RemoveRefElement(ref head, 1);
 Assert.AreEqual(2, head.Value);
 Assert.AreEqual(3, head.Next.Value);
 Assert.AreEqual(4, head.Next.Next.Value);
 

 [TestMethod]
 public void RemoveValueFromTopOfListTest()
 

 head = DoublyLinkedListHelper.RemoveElement(head, 1);
 Assert.AreEqual(2, head.Value);
 Assert.AreEqual(3, head.Next.Value);
 Assert.AreEqual(4, head.Next.Next.Value);
 
 

 public class DoublyLinkedListHelper
 
 public static void RemoveRefElement(ref Node head, int value)
 
 if (head == null)
 
 return;
 
 Node curr = head;
 Node prev = null;
 Node next = head.Next;
 while (curr != null)
 
 if (curr.Value == value)
 
 if (prev != null)
 
 prev.Next = next;
 
 if (next != null)
 
 next.Prev = prev;
 
 curr.Next = null;
 curr.Prev = null;
 if (curr == head)
 
 head = next;
 

 break;
 
 prev = curr;
 curr = next;
 next = curr.Next;
 
 

 public static Node RemoveElement(Node head, int value)
 
 if (head == null)
 
 return null;
 
 Node curr = head;
 Node prev = null;
 Node next = head.Next;
 while (curr != null)
 
 if (curr.Value == value)
 
 if (prev != null)
 
 prev.Next = next;
 
 if (next != null)
 
 next.Prev = prev;
 
 curr.Next = null;
 curr.Prev = null;
 if (curr == head)
 
 return next;
 
 else
 
 return head;
 
 break;
 
 prev = curr;
 curr = next;
 next = curr.Next;
 
 return head;
 
 
 public class Node
 
 public int Value get; set; 
 public Node Prev get; set; 
 public Node Next get; set; 
 

The methods look fine to me. Reasonable variable names; no confusing control-flow; sensible enough signatures for what they are doing. (see t2chb0t's answer as to why I am wrong)

The tests could be more comprehensive. They should probably check the length of the list, and since the whole data-structure is exposed, you ought verify that the list isn't otherwise malformed (e.g. head.prev should always be null, especially worth checking in the special case of removing the head from the list).

The 'edge case' you have is because you've got a quick-and-nasty definition of a linked list as just 'the head node' (or null). The effect is that you are exposing a highly mutable data-structure which is easy to misuse. Much much better, would be to hide the Nodes away under a LinkedList type, which provides a simple interface (e.g. Add(T), Remove(T), GetEnumerator()) without exposing any implementation details.

public class LinkedList

 private Node Head; // keep track of the head

 public LinkedList()
 // start empty...
 Head = null;
 

 Remove(int value)
 
 RemoveRefElement(ref Head, value);
 

 // some more public methods and helper methods...

Having such an interface solves your 'edge case' interface problem, because the edge case is now an implementation detail, and instead you have a nice interface. I'd argue that your Ref version is better, because it is modifying the data-structure passed to it, which the return version doesn't make entirely clear. Having a LinkedList class with a nice Remove member that returns nothing serves the same purpose, and allows you to pass the LinkedList around (you can't pass the Head node around as a mutable list, because if it is removed from the list, then everyone except the caller suddenly has a list with exactly one element in it). Having a well-defined interface also makes writing tests easier, because you don't have to think about whether the data-structure is 'correct' or not, just whether it does the job.

As an implementation detail, I'd maintain that the Ref version would be better, but once something is private it matters less what it looks like.

Petty stuff:

• Inline documentation (///) is always appreciated




• The break is redundant in RemoveElement, and I'd personally make the break in RemoveRefElement a return (just makes it clearer that the method has ended)




• Personally I'd appreciate more empty lines. The back-to-back ifs, for example, would be easier for me to scan if they were separated, since they are separate pieces of logic.




• A generic implementation would always be nice, and gives you a chance to demonstrate awareness of how to do comparisons effectively.

Since this is an interview-question here's how I see it.

I'd accept your code for a position of a junior-developer without much criticism but I would reject it for anything higher than that.

If you were applying for a senior-developer position then I'm of a quite different opinion than @VisualMelon. The methods don't make a good impression on me because they do too much. Your task is to remove an item but what you are doing is not only that. You are also searching for it. The searching part should be moved to its own method. I also find the variable names should not be abbreviated and instead you should use full words like current and previous. I agree with other suggestions by @VisualMelon.