Adding items to a list with List.Insert

Hello, I'm working through a Unity/c# tutorial and the exercise walks through creating an ordered list class, and adding new items to it based on comparing item values. Part of the tutorial states that "the List class doesn't let us add an item to a particular location in the list", and suggests creating a second temporary list, copying items above the "add location" to that list, adding the new item to the end of the first list, and then copying the higher items back from the temporary list to the main list. I have this working, but it seemed overly complicated, and after searching for an alternative, I found "List.Insert".

https://docs.microsoft.com/en-us/do...ctions.generic.list-1.insert?view=netcore-3.1

It seems like List.Insert can just take an index and an item, and add the item at the index location. So my Add() method in my "Sorted List" would then be:

Code (CSharp):

1. public void Add(T item)
2.     {
3.         int addLocation = 0;
4.         while (addLocation < items.Count && items[addLocation].CompareTo(item) < 0)
5.         {
6.             addLocation++;
7.         }
8.         items.Insert(addLocation, item);
9.     }
10.  
11.  

I'm currently working through the rest of the tutorial, so I haven't tested this yet, but is there a reason why this won't work?

 

There's your problem! Create simple datasets that mimic all the conditions you expect to see at runtime, and see if it works. We can take for granted that List.Insert() works, it's your logic and comparisons that need to be proven.

 

Well, I reached the end of the tutorial and tested it with the List.Insert implementation I proposed and it works fine. So was the tutorial wrong to say that "the List class doesn't let us add an item to a particular location in the list"?

The tutorial series is moving on into linked lists and I wonder whether it's worth the effort at this point.

 

I think learning linked lists is worthwhile. It's also worthwhile to learn about why there can be a significant performance difference between inserting an element in an array-backed list like C#'s List, and inserting an element in a Linked List.

 

Basically, the List<> data type in C# is basically just a wrapper over an array (or multiple arrays). While it supports the "Insert" functionality, what that insert method is doing under the hood is essentially what the tutorial has asked you to do... creating another array and copying over the values from the first array (plus the value to be inserted).

I'm guessing they make you write out that implementation on your own so that when you get to linked lists you can see that it's massively more efficient to insert values into a linked list than it is to insert into the array backed List<> class.

 

Thanks for the pointers, yes the tutorial series is going into some basic analysis of how computationally complex it is to perform add/find/remove functions on Lists and LinkedLists. Looking ahead, the series then looks at graphs, stacks, quees, trees, and then "design patterns".

I've been able to follow all the LinkedList examples (basically building a linkedList class), and I'm on to the "graphs" section. I feel like I can understand what's going on, but I'd have real trouble writing out a LinkedList class from scratch if I was asked to do so. Perhaps not surprising as I've only been seriously looking at c# for a couple of months.

I'm surprised that the entire course doesn't seem to mention co-routines, as I've used these in a small Unity game I've started alongside the tutorials to get more experience actually using c#. There was a big section on Unity Events that was a bit of a struggle to get through, and I feel like the tutorial series is approaching a very serious, professional design approach to c#/Unity, whereas the game project I'm working on would probably look very hacky to anyone with experience.

If you're an experienced programmer reading this, I'd be interested to know how often you deal with the above mentioned data structures, and whether it's just a case of gaining experience to know what you might use and when.