C# – Single Linked List : remove method

c

I am writing a single linked list in C#, could you please suggest to me if there any way to write a better remove method than the one I have:

using System;

class Node
{
    public int data = int.MinValue;
    public Node m_NextNode;

    public Node(int data_in)
    {
        data = data_in;
    }

    public Node()
    {
    }
}

class LinkedList
{
    private Node m_HeadNode;

    public void InsertData(int data)
    {
        Node aCurrentNode = m_HeadNode;
        if(m_HeadNode == null)
        {
            m_HeadNode = new Node();
            m_HeadNode.data = data;
        }
        else
        {
            while(aCurrentNode.m_NextNode != null)
                aCurrentNode = aCurrentNode.m_NextNode;

            aCurrentNode.m_NextNode = new Node();
            aCurrentNode.m_NextNode.data = data;
        }
    }

    public void DisplayData()
    {
        Node aCurrentNode = m_HeadNode;

        while (aCurrentNode != null)
        {
            Console.WriteLine("the value is {0}", aCurrentNode.data);
            aCurrentNode = aCurrentNode.m_NextNode;
        }    
    }

    public void RemoveData(int data)
    {
        Node aCurrentNode = m_HeadNode;

        while (aCurrentNode != null)
        {
            //if the data is present in head
            //remove the head and reset the head
            if (m_HeadNode.data == data)
            {
                m_HeadNode = null;
                m_HeadNode = aCurrentNode.m_NextNode;
            }
            else
            {
                //else save the previous node
                Node previousNode = aCurrentNode;
                if (aCurrentNode != null)
                {
                    //store the current node
                    Node NextNode = aCurrentNode.m_NextNode;
                    if (NextNode != null)
                    {
                        //store the next node
                        Node tempNode = NextNode.m_NextNode;

                        if (NextNode.data == data)
                        {
                            previousNode.m_NextNode = tempNode;
                            NextNode = null;
                        }
                    }

                    aCurrentNode = aCurrentNode.m_NextNode;
                }
            }            
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        LinkedList aLinkedList = new LinkedList();
        aLinkedList.InsertData(10);
        aLinkedList.InsertData(20);
        aLinkedList.InsertData(30);
        aLinkedList.InsertData(40);
        aLinkedList.DisplayData();

        aLinkedList.RemoveData(10);
        aLinkedList.RemoveData(40);

        aLinkedList.RemoveData(20);
        aLinkedList.RemoveData(30);

        aLinkedList.DisplayData();

        Console.Read();
    }
}

Best Answer

I would pull the 'if removing the head node' out of the while loop, and make the while loop simpler. Just keep track of the current and previous nodes, and switch the reference when you find the node to remove.

public void RemoveData(int data)
{
    if (m_HeadNode == null)
        return;

    if (m_HeadNode.data == data)
    {
        m_HeadNode = m_HeadNode.m_NextNode;
    }
    else
    {
        Node previous = m_HeadNode;
        Node current = m_HeadNode.m_NextNode;

        while (current != null)
        {
            if (current.data == data)
            {
                // If we're removing the last entry in the list, current.Next
                // will be null. That's OK, because setting previous.Next to 
                // null is the proper way to set the end of the list.
                previous.m_NextNode = current.m_NextNode;
                break;
            }

            previous = current;
            current = current.m_NextNode;
        } 
    }
}

Is RemoveData supposed to remove one instance of that integer from the list, or all instances? The previous method removes just the first one, here's one that removes all of them.

public void RemoveAllData(int data)
{
    while (m_HeadNode != null && m_HeadNode.data == data)
    {
        m_HeadNode = m_HeadNode.m_NextNode;
    }

    if(m_HeadNode != null)
    {
        Node previous = m_HeadNode;
        Node current = m_HeadNode.m_NextNode;

        while (current != null)
        {
            if (current.data == data)
            {
                // If we're removing the last entry in the list, current.Next
                // will be null. That's OK, because setting previous.Next to 
                // null is the proper way to set the end of the list.
                previous.m_NextNode = current.m_NextNode;
                // If we remove the current node, then we don't need to move
                // forward in the list. The reference to previous.Next, below,
                // will now point one element forward than it did before.
            }
            else
            {
                // Only move forward in the list if we actually need to, 
                // if we didn't remove an item.
                previous = current;
            }

            current = previous.m_NextNode;
        } 
    }
}
Related Topic