Building an Array List
In the following sample, we will implement an auto-resizable array list. This array list has several methods for adding new items by index and by value, finding the index of an item, and removing an item by index and by value. Through the concept of generics, the array list will hold any data type T.
public class ArrayList<T>
{
private T[] _arr;
public MyList(int capacity = 4)
{
_arr = new T[capacity];
Count = 0;
}
public int Count { get; private set; }
We defined an array to store the data elements. After that, we added the constructor, and we initialized the array based on the initial or default capacity. We defined the count property to keep track of the number of items in the array.
public T this[int index]
{
get
{
if (index > Count || index < 0)
{
throw new ArgumentOutOfRangeException($"Index {index} is outside the bounds of the array!");
}
return _arr[index];
}
set
{
if (index > Count || index < 0)
{
throw new ArgumentOutOfRangeException($"Index {index} is outside the bounds of the array!");
}
_arr[index] = value;
}
}
To allow clients to assign and retrieve items using []
notation, we added the indexer to the class. However, we need to validate the index and make sure it is not out of the array range. Looking up items by index in an array is fast. The runtime complexity of the lookup operation is O(1).
Next, we are going to define a method to add the new item at the specified index. Also, we need to validate the index for the InsertAt()
method.
public void InsertAt(int index, T value)
{
if (index > Count || index < 0)
{
throw new ArgumentOutOfRangeException($"Index {index} is outside the bounds of the array!");
}
if (Count >= _arr.Length)
{
_arr = Resize();
}
Array.Copy(_arr, index, _arr, index + 1, Count - index);
_arr[index] = value;
Count++;
}
If the array is full, we need to resize the array. Inside the Resize()
method, we will create a new array whose size is twice the original array size. Then we will copy all the existing items to the new array. So, we will have a dynamic array that automatically grows as we add new items to it. Note that the runtime complexity of this operation is O(n).
private T[] Resize()
{
var temp = new T[_arr.Length * 2];
Array.Copy(_arr, temp, _arr.Length);
return temp;
}
We can add items to the array list by value. The Add()
method takes a value and inserts the value at the end of the array.
public void Add(T value)
{
InsertAt(Count, value);
}
Now let's implement the search operation. In this method, we want to loop over all the items in the array. If we find the item, we will return the index, otherwise, we will return -1. The runtime complexity of the search operation is O(n).
public int IndexOf(T value)
{
for (var i = 0; i < Count; i++)
{
if (_arr[i].Equals(value))
{
return i;
}
}
return -1;
}
We begin removing items from the array list by index. First, we want to validate the index to make sure it is within the bounds of the array. Then, we need to remove the item and shift the remaining items after it by one position to the left, to fill the empty position. Finally, we set the value of the last position to default(T)
.
public T RemoveAt(int index)
{
if (index >= Count || index < 0)
{
throw new IndexOutOfRangeException($"Index {index} is outside the bounds of the array!");
}
var item = _arr[index];
Array.Copy(_arr, index + 1, _arr, index, Count - index - 1);
_arr[Count - 1] = default;
Count--;
return item;
}
The runtime complexity of removing an item from the array list by index is O(n). Now, let's implement the remove by value method. Inside this method, we use IndexOf()
method to find the index of the value, and after that, we use the RemoveAt()
method to remove the item at the specified index.
public int Remove(T value)
{
var index = IndexOf(value);
if (index != -1)
{
RemoveAt(index);
}
return index;
}
Working with the Array List
Finally, we are going to make an ArrayList<int>
and working with its methods.
class Program
{
static void Main(string[] args)
{
var list = new ArrayList<int>(4);
list.Add(80);
list.Add(90);
list.Add(100);
list.Add(110);
list.InsertAt(2, 95);
for (var i = 0; i < list.Count; i++)
{
Console.WriteLine(list[i]);
}
Console.WriteLine("-------------------------");
Console.WriteLine($"Index of 110: {list.IndexOf(110)}");
Console.WriteLine($"The item with index of {list.Remove(100)} removed from the list");
Console.WriteLine($"The {list.RemoveAt(3)} removed from list");
Console.WriteLine("-------------------------");
for (var i = 0; i < list.Count; i++)
{
Console.WriteLine(list[i]);
}
}
}
You can download the source code on Github.