CODEWITHSUNDEEP
c#
Raghav
Raghav

Reputation: 1

Single Linked List : remove method

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();
    }
}

Upvotes: 0

Views: 6178

Answers (7)

maxspan
maxspan

Reputation: 14177

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;
            }
        }

Upvotes: 0

Tim Kathete Stadler
Tim Kathete Stadler

Reputation: 1069

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.

Upvotes: 0

David Yaw
David Yaw

Reputation: 27864

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;
        } 
    }
}

Upvotes: 4

Mehran
Mehran

Reputation: 2027

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.

Upvotes: 0

Hans Passant
Hans Passant

Reputation: 941635

    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;
    }

Upvotes: 1

Chuck Savage
Chuck Savage

Reputation: 11955

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)
        }
    }    
}

Upvotes: 0

Steve Wellens
Steve Wellens

Reputation: 20620

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.

Upvotes: 2

Related Questions