CODEWITHSUNDEEP
c#linked-list
Fihii
Fihii

Reputation: 75

C# how to insert a node in LinkedList on a specific index

I have a school assignment and a part of this assignment is to insert a linked list node between two other nodes. This is the method.

public static void insert(LinkedList<Person> list, int index, Person data)
    {

    }

I've read some articles about LinkedList and I've found out that every linked list needs a head and a tail. I'm just not sure how to implement it, as we are only allowed to use LinkedList<T> and LinkedListNode<T> without the majority of functions they offer.

I think I have to use a while loop to get to the given index, but I don't know how to move through the LinkedList.

public static void insert(LinkedList<Person> list, int index, Person data)
    {
        int counter = 0;

        while (counter <= index)
        {
            if (counter == index)
            {

            }

            counter = counter + 1;
        }
    }

So I'd like to know how to insert data in a LinkedList on a specific index and how to create a head and a tail in this scenario. Note: I'm not allowed to change the signature of the method.

Upvotes: 1

Views: 10848

Answers (1)

rweisse
rweisse

Reputation: 830

This is a funny assignment. I wonder if your teacher knows that .Net Frameworks source code is public. Although you are prohibited to use methods like LinkedList<T>.AddAfter you are free to have a look at the source code and see how this method is implemented and lets say... simply copy the code? ;-)

Have a look at: https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs,3fc9552feecc5b5c

There you will see the implementation of this AddAfter-Method:

public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    ValidateNode(node);
    ValidateNewNode(newNode);
    InternalInsertNodeBefore(node.next, newNode);
    newNode.list = this;
}

The part you are interested in is the internal method InternalInsertNodeBefore() that gets called by the AddAfter()-method.

Its located in the same class - you will find it by typing ctrl+f:

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) {
    newNode.next = node;
    newNode.prev = node.prev;
    node.prev.next = newNode;
    node.prev = newNode;            
    version++;
    count++;
}

There you see how it's done and may get some "inspiration". There will be a problem with setting count and version manually. They can only be setted by functions inside your LinkedList. I think you won't be able to set the count-variable. But however adding a new element in this way should work.

EDIT 1: Of course you have to get the current element of the list at the desired index first. You will get it by calling list.ElementAt(index). It will return a LinkedListNode<Person> node. Together with your new Person-node you can call InternalInsertNodeBefore(). As you can see you won't need any loops.

EDIT 2: It seems that I have to apologize. I haven't seen that Next and Previous-Values of LinkedListNode<T> are read only values, too. See: https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs,08181ebdd4cdf907

Additionally Microsoft sealed the class. So it is not possible to inherit it by a new class and overide Next and Previous to add setter methods. It seems that you have to implement a completely new LinkedList- and LinkedListNode-Class by yourself. There is already a question about this topic: Creating a very simple linked list

This is the code I thought about. But IT WON'T WORK because next, prev and head are internal objects. They have got public references like Next, Previous and First but they are read only.

public static void insert(LinkedList<Person> list, int index, Person data)
{
    int currentIndex = 0;
    var currentNode = list.head;
    if (index >= 0)
    {
        while (currentNode != null && currentIndex <= index)
        {
            if (currentIndex == index)
            {
                data.next = currentNode;
                data.prev = currentNode.prev;
                currentNode.prev.next = data;
                currentNode.prev = data; 
            }
            currentIndex++;
            currentNode = currentNode.next;
        }
    }
}

Upvotes: 2

Related Questions