Singly Linked List Implementation using C# - RemoveLast Method

Question

I've implemented Singly linked list using C# . Can anyone please look into the following code and suggest where I'm wrong?

public int RemoveLast()
{
    if (Head != null)
    {
         var curNode = Head;

         while (curNode.Next != null)
         {
              curNode = curNode.Next;
         }

         var lastNodeValue = curNode.Value;

         curNode = null;
         Size--;
         return lastNodeValue;
     }

     return -1;
}

This function does not remove the last node. I'm unable to figure out what's wrong. When while loop ends, we have the reference of node in curNode whose next is null. It means this is the last node. At the end, I'm setting this node to null. But when I use Display function. It displays the last node as well. This is not deleting the last node.

Here is my display function:

    public string Display()
    {
        if (Head == null)
        {
            return string.Empty;
        }

        var curNode = Head;
        var builder = new StringBuilder();

        while (curNode.Next != null)
        {
            builder.Append($"{curNode.Value} ");
            curNode = curNode.Next;
        }

        builder.Append($"{curNode.Value} ");

        return builder.ToString();
    }

Answer 1

okay guys, after your help, I've rewritten this method that meets all the requirements and set to HeadNode null if there is only one node in linked list. So here we go:

    public int RemoveLast()
    {
        if (HeadNode != null)
        {
            var currNode = HeadNode;
            var prevNode = HeadNode;

            if (HeadNode.Next == null)
            {
                HeadNode = null;
                Size--;
                return currNode.Value;
            }

            while (currNode.Next != null)
            {
                prevNode = currNode;
                currNode = currNode.Next;
            }

            prevNode.Next = null;
            Size--;
            return currNode.Value;
        }

        return -1;
    }

Thank you everyone who contributed in this thread. Happy Coding :)

Answer 2

[x] -> [x] -> [x] -> null
               ^
               curNode (becomes null)
           ^
           this reference still exists

When doing curNode = null you do not change any reference in the list. curNode variable is changed only, it is pointing to the last element before operation and becomes null afterwards.

Try always keep reference to the node before last:

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;
        // Corner case when there is only one node in the list
        if (Head.Next == null)
        {
            Head = null;
            Size--;
            return curNode.value;
        }

        var beforeLastNode = curNode;
        curNode = curNode.Next;
        while (curNode.Next != null)
        {
            beforeLastNode = curNode;
            curNode = curNode.Next;
        }

        var lastNodeValue = curNode.Value;

        beforeLastNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

Answer 3

You need to make the curNode.Next value null on the previous node. 'curNode' is a local variable, setting it null doesn't do anything except maybe extend its GC life.

public int RemoveLast()
{
    if (Head != null)
    {
         var curNode = Head;
         var previousNode = null;

         while (curNode.Next != null)
         {
              previousNode = curNode;
              curNode = curNode.Next;
         }

         var lastNodeValue = curNode.Value;

         if (previousNode == null)
             Head = null;
         else
             previousNode.Next = null;
         Size--;
         return lastNodeValue;
     }

     return -1;
}

Answer 4

You need to go to the last-but-one node, and change its Next to null:

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;

        while (curNode.Next?.Next != null)
        {
            curNode = curNode.Next;
        }

        var lastNodeValue = curNode.Next?.Value ?? -1;
        curNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

Note that if you also want Head to be set to null if its the only node, then you can do that like so:

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;

        while (curNode.Next?.Next != null)
        {
            curNode = curNode.Next;
        }

        int lastNodeValue;

        if (Head.Next == null)
        {
            lastNodeValue = Head.Value;
            Head = null;
        }
        else
        {
            lastNodeValue = curNode.Next?.Value ?? -1;
        }
        curNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

I have to say though, this Head property looks a bit dubious - it should perhaps belong to a different class.