Intrusive linked node

Dealing with large number of objects can be tasking, specially in games, traditionally we have our objects living in some sort of collection, and then we traverse this collection to perform a task (like Update() or Draw()).

Collections work amazingly, traditionally I seen that the generic List is used the most, I use them often, but I stopped using them to managed my objects, simply because of how slow and tasking the "Remove()" function was, let me explain this:

when you have a collection of 10 elements in a List, and you decide to remove element 4, you would have to shift the following 6 elements down a slot to keep the list continuous, since the list is just a glorified "array", this can be very expensive, imagine if you were to remove element 1 in a list that contains 10,000 elements, not fun.

Linked list in the other hand do a much nicer job for removing elements, since they know what's next and what was previously, I would suggest to use linked list when you don't need to access an specific element in a collection, linked list do not work nicely when trying to "find" things inside them, because they are not indexed, you would have to check from start to end for an element using some comparison check on every single element, not fun.

Currently in my game, I use my own "collections" which are very specific, I have an "Actor Node" which takes care of the actors, like this:

public class ActorNode
    {
        public IActor Subject;
        public ActorNode SelfReference;
        public ActorNode NextActor;
        public ActorNode PreviousActor;

        public static ActorNode Head;

        public ActorNode(IActor subject)
        {
            SelfReference = this;
            Subject = subject;
        }

        public void Activate()
        {
            if (Head != null)
            {
                Head.PreviousActor = SelfReference;
                NextActor = Head;
            }
            Head = SelfReference;
        }

        public void Deactivate()
        {
            if (PreviousActor == null) //check for head
            {
                if (NextActor != null)
                {
                    Head = NextActor;
                    NextActor.PreviousActor = null;
                }
                else
                {
                    Head = null;
                }
            }
            else
            {
                if (NextActor != null) //check for tail
                {
                    NextActor.PreviousActor = PreviousActor;
                    PreviousActor.NextActor = NextActor;

                    NextActor = null;
                    PreviousActor = null;
                }
                else
                {
                    PreviousActor.NextActor = null;
                }
            }

            PreviousActor = null;
            NextActor = null;
        }
    }

This Node is a "component" of my actors, meaning that they live inside my actor class, using my factory design pattern (check last post for reference) I easily activate them, and using my Recycle method (also last post) I deactivate them before returning them to the pool, like this:

public class AnActor: PooleanNode<AnActor>, IActor, Irecycle
{
    LinkedPoolean<AnActor> Pool = new LinkedPoolean<AnActor>();
    
    ActorNode ActorLink;    

    public AnActor()
    {
        ActorLink = new ActorNode(this);
    }

    public static void Create()
    {   
        AnActor Vessel;
        Pool.Get(out Vessel);
        Vessel.ActorLink.Activate(); //Activates the node so it is in the collection
    }

    public void Recycle()
    {
        ActorLink.Deactivate(); //deactivates the node so it is taken out.
        Pool.ReturnPoolable(this);
    }
}

Now, let's assume that the "IActor" interface contains a method called "Update()", we can use this collection to update all the currently activated actors like this:

public static void UpdateAll() //function that updates all the actors
{
     ActorNode Current = ActorNode.Head; //gets the current head
     if(Current == null) //make sure there are elements in the collection
     {
         return; //if there's nothing, then get out.
     }
     IActor CurrentActor; //container for the current subject that needs to update

     do
     {
          CurrentActor = Current.Subject; //get the first subject
          
          CurrentActor.Update(); //Update it and then

          Current = Current.NextActor; //check for the next node

     } while (Current != null); //and if that node is not null, then repeat.
}

That function will make sure that all the activated nodes will update.

Thanks for reading.