Tuesday, April 16, 2024 04:42

Table of contents >> Data Structures > List


Dynamic list (List<T>) is one of the most popular data structures used in programming. It does not have fixed size like arrays, and allows direct access through index, unlike linked lists (LinkedList<T>). The dynamic array is also known as “array list”, “resizable array” and “dynamic array”. List<T> holds its elements in an array, which has a bigger size than the count of the stored elements. Usually when we add an element, there is an empty cell in the list’s inner array. Therefore, this operation takes a constant time. Occasionally, the array fills, and it has to expand. This takes linear time, but it rarely happens. If we have a large amount of additions, the average-case complexity of adding an element to List<T> will be a constant. If we sum the steps needed for adding 100,000 elements (for both cases – “fast add” and “add with expand”) and divide by 100,000, we will obtain a constant which will be nearly the same for like adding 1,000,000 elements.

This statistically-averaged complexity calculated for large enough amount of operations is called amortized complexity. Amortized linear complexity means that if we add 10,000 elements consecutively, the overall count of steps will be of the order of 10,000. In most cases add it will execute in a constant time. Searching in List<T> is a slow operation because you have to traverse
through all the elements. Removing by index or value executes in a linear time. It is a slow operation because we have to move all the elements after the deleted one with one position to the left.
The indexed access in List<T> is instant, in a constant time, since the elements are internally stored in an array. Practically, List<T> combines the best of arrays and lists, this being the reason for which it is a preferred data structure in many situations. For example if we have to process a text file and to extract from it all words (with duplicates), which match a regular expression, the most suitable data structure in which we can accumulate them is List<T>, because we need a list, the length of which is unknown in advance and can grow dynamically. The dynamic array (List<T>) is appropriate when we have to add elements frequently, as well as keeping their order of addition and access them through index. If we often need to search or delete elements, List<T> is not the right data structure. Use List<T>, when you have to add elements quickly and access them through index.

The way we declare a List is simple. As we learned from the Generics lesson, <T> actually indicated that we can use any type of data we want, because the method, structure, class, etc, doesn’t care what type of data we are sending to it. In our case, List<T> means that our List can store any kind of elements: int, string, float, etc. This is how we declare and initialize a List<T>:

By replacing <T> with <int>, we told our List that we want to store elements of type integer. The procedure is the same for any other data type. We can even declare a class with methods and members, and then create a List of that classes type:

One thing to notice about the List is the fact that once you declare it of a certain type, you cannot add any other types to it. In other words, if you declare a list of type string, you can only add string variables to it, and no other type.

The most important methods of Lists are:

Add() – This appends a new element object to the end. We can keep adding elements to the collection until memory runs out. Example:

AddRange() – for adding many elements at once, like adding an array to a List, we use the AddRange method. This can simplify code that combines collections. Here is how we use it:

Clear() – You can call the instance method Clear() on your List. Example:

Sort(), Reverse() – these methods do exactly what their name says: they sort a List, or reverse the order of their elements. In case of sorting, for strings it orders alphabetically; for integers (or other numbers) it orders from lowest to highest. Example:

Insert(), Remove(), RemoveAt() – methods used to add or remove elements into a List. RemoveAt() uses a numeric index to specify which element you want to remove. Example:

IndexOf() – This determines the element index of a certain value in the List collection. It searches for the first position (from the start) of the value. IndexOf has two overloads. It works in the same way as string’s IndexOf. It searches by value and returns the location. Example:

Contains(), Exists(), Find(). These methods all provide searching. They vary in arguments accepted. With Predicates, we influence what elements match. We haven’t learn about LinQ and predicates, but they are not the scope of this lesson. Example:

ToArray() – returns an array composed of the list’s elements. Example:

Distinct() – removes duplicates from a list. Example:

Equality() – Sometimes we need to test two Lists for equality, even when their elements are unordered. We can sort and then compare, or use a custom List equality method. Example:

The most important properties of List are:

Capacity – We can use the Capacity property on List, or pass an integer to the constructor (which sets an initial capacity) to improve allocation performance.
Count – To get the number of elements, access the Count property. This is fast – just avoid the Count extension method. Count, on the List type, is equal to Length on arrays.

Tags: ,

Leave a Reply

Follow the white rabbit