Remove the first value for a doubly linked list

Question

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:

using void function and ref
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; }
    }
}

the6p4c · Accepted Answer · 2018-08-08 13:26:53Z

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

t3chb0t · Accepted Answer · 2018-08-08 09:22:19Z

7

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.

answered Aug 8, 2018 at 9:22

t3chb0t

44.7k9 gold badges84 silver badges191 bronze badges

\$\begingroup\$ I must lend my support for this answer... I do rather focus on the public interface, and honestly I hadn't even noticed the variables were shortened... (arguably the bigger problem is that the members of Node are shortened... these most definitely should not be!) \$\endgroup\$

VisualMelon
– VisualMelon

2018-08-08 09:24:29 +00:00
Commented Aug 8, 2018 at 9:24
\$\begingroup\$ @t3chb0t I had about 15 minutes to write the code, you seem like a harsh judge of code, since my goal is to learn, Can you please explain except the Generic Node what else would you expect from a senior developer to do in 15 minutes? \$\endgroup\$

Gilad
– Gilad

2018-08-08 18:09:09 +00:00
Commented Aug 8, 2018 at 18:09
1

\$\begingroup\$ @Gilad from a senior-developer I wouldn't expect a working solution at all because I assume he can already write code. What I want to see is design/architecture - even pseudocode but clean, (maybe) modular, extendable (where appropriate), testable, resuable, with a clean API. In 15 minutes you cannot do anything but present a rough draft. Next time you have to share more information about your interview. \$\endgroup\$

t3chb0t
– t3chb0t

2018-08-08 18:19:18 +00:00
Commented Aug 8, 2018 at 18:19

Add a comment |

Stack Exchange Network

Remove the first value for a doubly linked list

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Remove the first value for a doubly linked list

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions