CODEWITHSUNDEEP
c#linked-list
Failed Scientist
Failed Scientist

Reputation: 2027

C# LinkedList AddAfter

I am trying to implement Insertion Sort using C# in the code below. But its giving me the error that:

The LinkedList node already belongs to a LinkedList

public void Sort(ref LinkedList<int> list)
{
    LinkedListNode<int> tempNode = new LinkedListNode<int>(0); //Contains zero just for initalization

    for(tempNode = list.First; tempNode!=null; tempNode=tempNode.Next)
    {

        LinkedListNode<int> sortedListBoundary = tempNode; //Contains zero just for initalization

        while (sortedListBoundary.Value < sortedListBoundary.Next.Value && sortedListBoundary.Previous!=null)
        {
            sortedListBoundary = sortedListBoundary.Previous;
        }

        list.AddAfter(tempNode, sortedListBoundary); //This line gives error
    }
}

I have even tried to take that node in a temp. Delete the existing node (sortedListBoundary) and then call AddAfter(), but this time error is:

Node doesn't belong to LinkedList()

So how can I overcome this deadlock? Thanks in advance

Upvotes: 1

Views: 1701

Answers (2)

pseudoDust
pseudoDust

Reputation: 1386

AddAfter(node, newNode) requires 2 things, node has to belong to the list, and newNode cannot belong to a list, this is all well and good, and removing sortedListBoundary and adding it after tempNode should have worked if not for the following:

You initialize (in the for loop) tempNode = list.First and then LinkedListNode<int> sortedListBoundary = tempNode; so now sortedListBoundary = tempNode = list.First and sortedListBoundary.Previous == null because it is first, so you do not enter the if. And so, when you get to AddAfter part, sortedListBoundary = tempNode... you are trying to add a node after itself...

Edit: Just to clarify, when you remove sortedListBoundary, because sortedListBoundary = tempNode you are also removing tempNode (as they are the same) therefor, you get the error that it is not in the list... you can't add something after something that is not in the list.

Edit 2: You ask for a solution, the best answer I can give is to not try to place a node after itself, go over the insertion sort algorithm carefully and see where you deviate from it, here is an implementation of insertion sort:

public void Sort(ref LinkedList<int> list)
{
    LinkedListNode<int> tempNode;

    for(tempNode = list.First.Next; tempNode!=null; tempNode=tempNode.Next)
    {

        LinkedListNode<int> sortedListBoundary = tempNode.Previous; 
        list.Remove(tempNode);

        while (sortedListBoundary != null && tempNode.Value < sortedListBoundary.Value)
        {
            sortedListBoundary = sortedListBoundary.Previous;
        }

        if(sortedListBoundary == null)
            list.AddFirst(tempNode);
        else
            list.AddAfter(sortedListBoundary, tempNode); 
    }
}

It is the closest I could make it to your code, but I don't know what you where going for.

Upvotes: 1

Samer Tufail
Samer Tufail

Reputation: 1884

LinkedListNode<int> sortedListBoundary is of type LinkedListNode and tempNode is also of type LinkedListNode<int> LinkedList says:

public LinkedListNode<T> AddAfter(
    LinkedListNode<T> node,
    T value
)

Upvotes: 0

Related Questions