0

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();
    }
}
3
  • Your code blocks are really busted up, but would this help? stackoverflow.com/questions/1432818/… Commented Apr 5, 2011 at 19:03
  • 1
    What do you mean by 'better'? More readable, more performant, less code, etc? Commented Apr 5, 2011 at 19:09
  • Is this just a programming exercise? C# already has a type-safe doubly linked list built-in. Commented Apr 5, 2011 at 19:30

7 Answers 7

4

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;
        } 
    }
}
Sign up to request clarification or add additional context in comments.

Comments

2

You have a line you do not need:

            m_HeadNode = null;
            m_HeadNode = aCurrentNode.m_NextNode;

You don't need to set m_HeadNode to null before you set it to something else.

1 Comment

what about the else part, i have used three nodes to remove the data; first i remeber the previous node , then from the previous node i take the current node from the current i get the next node, once the data is matched i remove the current node and establish link between the previous and current node, is there any better way to achieve the same
1
    public bool RemoveNode(int data) {
        Node prev = null;
        for (Node node = head; node != null; node = node.next) {
            if (node.data == data) {
                if (prev == null) head = node.next;
                else prev.next = node.next;
                return true;
            }
            prev = node;
        }
        return false;
    }

1 Comment

you don't really need the return, His implementation removes all the occurrences of data.
0
public void RemoveData(int data)
{
    if(null == m_HeadNode) return;
    if(m_HeadNode.data == data)
    {
       // remove first node
    }
    else
    {
        Node current = m_HeadNode;
        while((null != current.m_NextNode) && (current.m_NextNode.data != data))
            current = current.m_NextNode;
        if(null != current.m_NextNode)
        {
            // do remove node (since this sounds like homework, I'll leave that to you)
        }
    }    
}

Comments

0

with only one local variable.
There is a bug in you code, imagine you have list that has 3 elements with data = 5 and you want to remove 5, you codes stores the head in aCurrentNode and starts the loop. There the condition is true so you move the head to the next. but aCurrentNode is not updated so in the next iteration it's pointing to the previous Head and aCurrentNode.m_NextNod would be your current Head, Hence you got yourself in a never ending loop!

 public void Remove(int data)
    {
      for(var cur = new Node {Next = Head}; cur.Next != null; cur = cur.Next)
      {
        if (cur.Next.Data != data) continue;
        if (cur.Next == Head)
          Head = Head.Next;
        else
          cur.Next = cur.Next.Next;
      }
    }

a trick to make you loop simpler is to start with a fake node that points to head. This way you don't need to place an If to check head differently, however you need an if to set the head. the other trick is to check for next nodes data. that way you don't need to keep a previous Node.

Comments

0
public SLElement Remove(int index)
    {
      SLElement prev = _root;
      if (prev == null) return null; 
      SLElement curr = _root._next;
      for (int i = 1; i < index; i++)
      {
        if (curr == null) return null; 
        prev = curr;
        curr = curr._next;
      }
      prev._next = curr._next; 
      curr._next = null;
      return curr;
    }

This deletes the element with a specific index, not with a specific value.

Comments

0

To Make really simple. Please follow the link. Below is a code snippet to remove item from a single link list.

public void DeleteNode(int nodeIndex)
        {
            int indexCounter = 0;
            Node TempNode = StartNode;
            Node PreviousNode = null;
            while (TempNode.AddressHolder != null)
            {
                if (indexCounter == nodeIndex)
                {
                    PreviousNode.AddressHolder = TempNode.AddressHolder;
                    break;
                }
                indexCounter++;
                PreviousNode = TempNode;
                TempNode = TempNode.AddressHolder;
            }
        }

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.