This article mainly shows the imitation List source code to achieve a custom List class, to understand C# has some help.
Based on the content
Add() adds the element at the end
Insert() specifies the subscript to Insert the element
The Count attribute indicates the number of elements
The RemoveAt() method specifies the subscript element to be removed
IndexOf() returns the IndexOf the first element
LastIndexOf() returns the index of the last element
Implement a basic List with a generic array
First, define the MyList class
class MyList<T>
{
private T[] array;// Generic arrays are used to store data as the body of the class
private int count = 0;// Store the number of elements
public MyList(int size)
{
array = new T[size];
}
public MyList()
{
array = new T[0]; }}Copy the codeTo complete class initialization, add two constructors here. The constructor with no arguments creates an array of length zero, and the constructor with arguments builds an array of specified length.
// Obtain the capacity
public int Capacity { get => array.Length; }
public int Count { get => count; }
Copy the codeSet the accessor and encapsulate the count field, which the object can use to get the number of list elements by calling the count attribute. The second part implements the Add method
public void Add(T item)
{
if( Count == Capacity)// Whether the maximum capacity is reached
{
if(Capacity == 0)
{
array = new T[4];
}
else
{
EnsureCapacity();
}
}
array[Count] = item;
count++;
}
private void EnsureCapacity()
{
// If the capacity is insufficient, double the capacity each time
var newArray = new T[Capacity * 2];
Array.Copy(array, newArray, Count);
array = newArray;
}
Copy the codeWhen the capacity is insufficient when adding elements to the array, the capacity is expanded by twice the current capacity. Create a new array that is twice the size, and then copy the original array members into the new array. Add indexers If you want list objects to be accessible using [] like arrays, you must add indexers.
// Add indexer
public T this[int index]
{
get { return array[index]; }
set { array[index] = value; }}Copy the codeThe Insert method needs to understand that the subscript is out of bounds, and the capacity is sufficient to Insert the element. We move the elements from the end to index one by one and assign item to the number of elements at index by one
// Insert the element
public void Insert(int index,T item)
{
if (0 <=index && index <= Count)
{
if (Count == Capacity)
{
// The capacity is insufficient
EnsureCapacity();
}
// Iterate from back to front
for (int i = Count- 1; i >= index; i--)
{
array[i+1] = array[i];
}
array[index] = item;
count++;
}
else
{
throw new Exception("Index out of range"); }}Copy the codeImplement the RemoveAt method the RemoveAt method is similar to the Insert method. We’re going to move the elements forward one by one starting at index and we’re going to set the last element to the default and subtract one from the number of elements
// Delete the specified element
public void RemoveAt(int index)
{
if (0 <= index && index < Count)
{
for (int i = index+1; i < Count; i++)
{
array[i- 1] = array[i];
}
array[Count - 1] = default(T);
count--;
}
else
{
throw new Exception("Index out of range"); }}Copy the codeTo find the first identical element, return the index. Generics cannot be compared using the comparison operator. Just use the Equals method of the array.
// Find the first element in order
public int IndexOf(T item)
{
for (int i = 0; i < Count; i++)
{
if (array[i].Equals(item))
{
returni; }}return - 1;
}
// Find the first element in reverse order
public int LastIndexOf(T item)
{
for (int i = Count- 1; i >=0 ; i--)
{
if (array[i].Equals(item))
{
returni; }}return - 1;
}
Copy the codeImplement sorting using bubble sort when comparing two generic elements, you must provide the generic constraints of IComparable if you use the CompaerTo method
class MyList<T> where T:IComparable{}
Copy the code// Sort in ascending order
public void Sort()
{
for (int i = 0; i < Count- 1; i++)
{
for (int j = 0; j < Count- 1-i; j++)
{
if (array[j].CompareTo(array[j + 1) >0)
{
T tempItem = array[j];
array[j] = array[j + 1];
array[j + 1] = tempItem; }}}}Copy the codeYou can use yield to simplify iterators. You can only implement IEnumerable
class MyList<T> :IEnumerable<T> where T:IComparable{}
Copy the code public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < Count; i++)
{
yield return array[i];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
throw newNotImplementedException(); }}Copy the codeClear, so you can forch the list object.
The complete code
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace DotNetStudy
{
class MyList<T> :IEnumerable<T> where T:IComparable
{
private T[] array;
private int count = 0;
public MyList(int size)
{
array = new T[size];
}
public MyList()
{
array = new T[0];
}
// Obtain the capacity
public int Capacity { get => array.Length; }
public int Count { get => count; }
public void Add(T item)
{
if( Count == Capacity)// Whether the maximum capacity is reached
{
if(Capacity == 0)
{
array = new T[4];
}
else
{
EnsureCapacity();
}
}
array[Count] = item;
count++;
}
private void EnsureCapacity()
{
// If the capacity is insufficient, double the capacity each time
var newArray = new T[Capacity * 2];
Array.Copy(array, newArray, Count);
array = newArray;
}
public T GetItem(int index)
{
if(index>0 && index < Count)
{
return array[index];
}
else
{
// console. WriteLine(" index out of range ");
throw new Exception("Index out of range"); }}// Add indexer
public T this[int index]
{
get { return array[index]; }
set { array[index] = value; }}// Insert the element
public void Insert(int index,T item)
{
if (0 <=index && index <= Count)
{
if (Count == Capacity)
{
// The capacity is insufficient
EnsureCapacity();
}
// Iterate from back to front
for (int i = Count- 1; i >= index; i--)
{
array[i+1] = array[i];
}
array[index] = item;
count++;
}
else
{
throw new Exception("Index out of range"); }}// Delete the specified element
public void RemoveAt(int index)
{
if (0 <= index && index < Count)
{
for (int i = index+1; i < Count; i++)
{
array[i- 1] = array[i];
}
array[Count - 1] = default(T);
count--;
}
else
{
throw new Exception("Index out of range"); }}// Find the first element in order
public int IndexOf(T item)
{
for (int i = 0; i < Count; i++)
{
if (array[i].Equals(item))
{
returni; }}return - 1;
}
// Find the first element in reverse order
public int LastIndexOf(T item)
{
for (int i = Count- 1; i >=0 ; i--)
{
if (array[i].Equals(item))
{
returni; }}return - 1;
}
// Sort in ascending order
public void Sort()
{
for (int i = 0; i < Count- 1; i++)
{
for (int j = 0; j < Count- 1-i; j++)
{
if (array[j].CompareTo(array[j + 1) >0)
{
T tempItem = array[j];
array[j] = array[j + 1];
array[j + 1] = tempItem; }}}}public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < Count; i++)
{
yield return array[i];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
throw newNotImplementedException(); }}}Copy the code