This is gonna be a hefty tutorial. There’s a lot of subjects to cover with data structures, we’re going to go over generics, recursion, and all sorts of stuff. This might be a longer tutorial than normal. Extra subjects meant to be individually researched will be bolded as per usual.

What is a Data Structure?

You probably already know, you just don’t recognize the term. It’s kinda self explanatory, it is a structure that we use to store data more easily. For example, an array is a data structure; it is a structure that we can use to store multiple variables of the same type. I’ll touch on some other common types of data structures, but there are tons of them out there that you can google and use, such as a stack or a queue.

Now we’re going to be talking about several things here, if you’re rusty on arrays and lists, I suggest you catch up with this tutorial.

Data Handling

There are different ways to handle your data and what you get from them. A list allows you to index into any position and retrieve that data. But there are others ways we could do this. Let’s look at the structure for a queue. A brief explanation of a queue is similar to a real life queue, like a line waiting for a roller coaster at a theme park.

Imagine if the last person in line got to go on the ride first, that’s be pretty messed up right? Luckily that’s not how it works, and it’s what a queue is for. The first person who enters the line is added to our queue, then when it’s time to get on the ride they take from the start of the line, not the end. This is known as a First In, First Out (FIFO) scenario. Here’s a psuedo code example.

Queue<Person> waitingLine = new Queue<Person>();
List<Person> peopleOnRide = new List<Person>();

void PersonJoinsLine(Person newPerson)
{
    //Adds a person to the end of the line
    waitingLine.Enqueue(newPerson); 
}

void StartRide(int numberOfOpenSpots)
{
    peopleOnRide.Clear();
    for(int i = 0; i < numberOfOpenSpots; i++)     
    {         
        if(waitingLine.Count > 0)
        {
            //Add the next person in line to the ride
            //and remove them from the line
            peopleOnRide.Add(waitingLine.Dequeue());
        }
        else
        {
            break;
        }
    }
}

PersonJoinsLine(new Person("Bob"));
PersonJoinsLine(new Person("Dan"));
PersonJoinsLine(new Person("Jim"));
//There are 3 people in line

StartRide(2);
//Now Bob and Dan are on the ride, but Jim is still waiting in line.

Generics

An important part of a lot of data structures is generics. They’re a super useful way to have your data structures work on generic types, the structure doesn’t care what type of data it stores before you make an instance. As per usual, you’ve already used them before. In fact they’re in the example above, generics are noted with using the <>, like above where we have Queue<Person>

Defining

When we make a class or struct, we can optionally add a generic the user can pass in like so:

class MyList<T>
{
     T[] internalArray;
}

In this case I’ve just made a class that you can pass a generic type into, and then we make an array of whatever that type is.
So if we made an instance of this class like MyList<int> bob, internally it would look like:

class MyList<int>
{
    int[] internalArray;
}

You can even define multiple generics class MyList<T1, T2, T3>.

Constraints

You can also make your generics have conditions, so instead of being able to pass in any type to the generic, you could constrain it to only allow certain things. So you can add the where keyword to add these, like so: class MyList<T> where T : [Something].

Replacing that something can be many options. You can put a base class, so only types that are derived or are that class can be passed in. You can use class to force it to be a class, same thing with adding struct. You can do multiple by separating with a comma, like so: class MyList<T> where T : PlayerBaseClass, EnemyBaseClass.

You can find more information about the multiple types of constraints you can have here.

Recursion

Recursion is another thing used plenty in data structures, but can also be used plenty outside of them. You can find plenty of jokes about it online. The idea is really simple, you have a function that calls itself. You can use this to iterate through a tree data structure or do other things that you could also do by looping through it.

Here’s an example, if we have this structure of a tree.

class BinaryTree<T>
{
    class Node
    {
        T data;
        Node left, right;
    }

    Node head;
    //etc
}

This is just the basic setup for a binary tree structure, you can do some googling for more details about it. So with this idea, where we have nodes that can go left or right, we can recursively go down the tree and change the data.

//Inside the Binary Tree class
public void DoFunctionOnAll(System.Action<T> doAction)
{
    DoFunctionRecursive(head, doAction);
}

void DoFunctionRecursive(Node currentNode, System.Action<T> doAction)
{
    //Early exist scenario
    if(currentNode == null)
        return;
    
    //Do our action
    doAction(currentNode.data);
    //Iterate down the tree
    DoFunctionRecursive(currentNode.left);
    DoFunctionRecursive(currentNode.right);
}

A quick explanation of what’s going on here if you’re confused. These functions would be inside the binary tree class. If someone wanted to call a function to happen to the data type passed in to every item in the tree, they’d pass a delegate to do so (Review delegates and lambdas here if you don’t remember).

So that calls the function where it passes our head node (the beginning of the tree) and our action to do. When we first enter the function, we do that action first passing in the nodes data (known as a preorder traversal, where as afterwards would be a postorder traversal). Then we check if the left or right isn’t null, if it isn’t we call the same function, but passing in the node.

This can all be a little tricky to understand initially, especially trying to envision how a tree works.

The danger of recursion is not having an exit condition, something that tells the function to stop calling itself when it’s done what it’s trying to do. That’s how you end up with this.

Making sure you have some way to stop calling the function over and over is important. In our example above, we check if currentNode is null, and if it is we end the function; that’s our early exit condition.

Stack Overflow

No, not the website. When you call a function, that function is added to the call stack, where it stores the information and variable associated with that function. If you do this too much, eventually you’ll get a stack overflow where it no longer has room to store all of this.

This is why you want to be careful about making sure to not have a scenario where you’d call a recursive function forever.

Extra Practice

For this practice, I’m asking a lot. We’re going to be making our own data structure. Nothing incredibly crazy, just a doubly linked list. Similar to our tree example above, we will have a class that has a generic type to pass in, and an internal class with a next and previous instance of that class.

This will essentially allow us to create our list. Here’s a basic setup/format you can use to get started:

class DoublyLinkedList<T>
{
    class Node
    {
        public T data;
        public Node next, previous;
        public Node(T _data) { data = _data; }
    }

    Node head = null; //The beginning of our list
    Node tail = null; //The end of the list
    public int Count = 0;

    public void Add(T data)
    {
        //First, check if head is null. If so, set head to a new node, 
        //set the tail to the head too

        //If it's not null, we need to set the tail's next to a new node, and then
        //set the tail to this new node
    }

    public T Get(int index)
    {
        //If the index is larger than the count, return null

        //From the head, loop through (recursively or not) and count until you
        //reach the correct index.
    }

    //More as you want to add, such as Remove(T data), RemoveAt(int index),   
    //Insert(T data, int index), indexing (Using [] to access)
    //All of this can be googled
}

This can be very tricky stuff to learn how to do, take your time. Do research, figure out how stuff works. If you get really stuck, don’t be afraid to reach out to people for guidance.

Support

Are you having trouble with understanding this tutorial? Please feel free to contact me via email at KoseckCory@gmail.com or message me on discord at 7ark#8194.

I would love to get feedback from people so I can add and improve these tutorials overtime. Letting me know what you’re confused about will let me update the tutorials to be more concise and helpful.

If you’re interested in supporting me personally, you can follow me on Twitter or Instagram. If you want to support me financially, I have a Patreon and a Ko-fi.