ArrayLists, Generic Lists, Is There A Way To Insert Items Faster?

''' <summary>
''' </summary>
''' <remarks>
''' This class seems to behave about as fast as a LinkedArray(of Object)
''' </remarks>
Public Class LinkedArray
    Implements IList

    ' Empirically this seems to be a good compromise and give good results
    Const DEFAULT_ARRAY_SIZE As Integer = 2220
    Private mArraySize As Int32

    Friend mLists As List(Of ArrayList)
    Friend mCount As Integer
    Friend mVersion As Integer

    Sub New(Optional ByVal arraySize As Integer = DEFAULT_ARRAY_SIZE)
        mArraySize = arraySize
        mLists = New List(Of ArrayList)
    End Sub

    Public Sub CopyTo(ByVal array As System.Array, ByVal index As Integer) Implements System.Collections.ICollection.CopyTo
        Throw New Exception("Not implemented")
    End Sub

    Public ReadOnly Property Count() As Integer Implements System.Collections.ICollection.Count
        Get
            Return mCount
        End Get
    End Property

    Public ReadOnly Property IsSynchronized() As Boolean Implements System.Collections.ICollection.IsSynchronized
        Get
            Return False
        End Get
    End Property

    Public ReadOnly Property SyncRoot() As Object Implements System.Collections.ICollection.SyncRoot
        Get
            Return mLists
        End Get
    End Property

    Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
        Return New LinkedArrayEnumerator(Me)
    End Function

    Public Function Add(ByVal value As Object) As Integer Implements System.Collections.IList.Add
        Dim a As ArrayList = Nothing
        If mLists.Count > 0 Then a = mLists(mLists.Count - 1)
        If a Is Nothing OrElse a.Count >= mArraySize Then
            a = New ArrayList
            mLists.Add(a)
        End If
        mVersion += 1
        mCount += 1
        a.Add(value)
    End Function

    Public Sub Clear() Implements System.Collections.IList.Clear
        ' this is not really needed but I think this might help the garbage collector
        For Each a As ArrayList In mLists
            a.Clear()
        Next
        mLists.Clear()
        mVersion += 1
        mCount = 0
    End Sub

    Public Function Contains(ByVal value As Object) As Boolean Implements System.Collections.IList.Contains
        Return IndexOf(value) >= 0
    End Function

    Public Function IndexOf(ByVal value As Object) As Integer Implements System.Collections.IList.IndexOf
        Return InternalSearch(value, Nothing, Nothing, Nothing)
    End Function

    Private Function InternalSearch(ByVal value As Object, ByRef index1 As Integer, ByRef list As ArrayList, ByRef index2 As Integer) As Integer
        Dim base As Integer = 0
        For index1 = 0 To mLists.Count - 1
            list = mLists(index1)
            index2 = list.IndexOf(value)
            If index2 >= 0 Then
                Return base + index2
            End If
            base += list.Count
        Next
        Return -1
    End Function

    Private Function InternalGetIndex(ByVal index As Integer, ByRef index1 As Integer, ByRef list As ArrayList, ByRef index2 As Integer) As Boolean
        If index < 0 OrElse index >= mCount Then Return False
        If index < mCount \ 2 Then
            Dim base As Integer = 0
            Dim newBase As Integer = 0
            For index1 = 0 To mLists.Count - 1
                list = mLists(index1)
                newBase = base + list.Count
                If index < newBase Then
                    index2 = index - base
                    Return True
                End If
                base = newBase
            Next
        Else
            ' Start by the end
            Dim limit As Integer = mCount
            Dim newLimit As Integer = 0
            For index1 = mLists.Count - 1 To 0 Step -1
                list = mLists(index1)
                newLimit = limit - list.Count
                If index >= newLimit Then
                    index2 = index - newLimit
                    Return True
                End If
                limit = newLimit
            Next
        End If
        Return False
    End Function

    Public Sub Insert(ByVal index As Integer, ByVal value As Object) Implements System.Collections.IList.Insert
        Dim a As ArrayList = Nothing
        Dim base As Integer = 0
        Dim newBase As Integer = 0
        For index1 = 0 To mLists.Count - 1
            a = mLists(index1)
            newBase = base + a.Count
            If index = newBase Then
                index = newBase
            End If
            If index < newBase Then
                If a.Count >= mArraySize Then
                    'split in two
                    Dim newList As New ArrayList
                    mLists.Insert(index1 + 1, newList)
                    ' we put the second half in the new list
                    Dim array(a.Count - mArraySize \ 2 - 1) As Object
                    a.CopyTo(a.Count - array.Length, array, 0, array.Length)
                    newList.AddRange(array)
                    ' and we remove the end in the old list
                    a.RemoveRange(mArraySize \ 2, array.Length)

                    newBase = base + a.Count
                    If index > newBase Then
                        base = newBase
                        a = newList
                    End If
                End If
                index -= base
                mVersion += 1
                mCount += 1
                a.Insert(index, value)
                Exit Sub
            End If
            base = newBase
        Next
        If index > base Then
            Throw New ArgumentOutOfRangeException("index", index, "Parameter out of range")
        Else
            Add(value)
        End If
    End Sub

    Public ReadOnly Property IsFixedSize() As Boolean Implements System.Collections.IList.IsFixedSize
        Get
            Return False
        End Get
    End Property

    Public ReadOnly Property IsReadOnly() As Boolean Implements System.Collections.IList.IsReadOnly
        Get
            Return False
        End Get
    End Property

    Default Public Property Item(ByVal index As Integer) As Object Implements System.Collections.IList.Item
        Get
            Dim index2 As Integer
            Dim list As ArrayList = Nothing
            If InternalGetIndex(index, Nothing, list, index2) Then
                Return list(index2)
            Else
                Throw New ArgumentOutOfRangeException("index", index, "Parameter out of range")
            End If
        End Get
        Set(ByVal value As Object)
            Dim index2 As Integer
            Dim list As ArrayList = Nothing
            If InternalGetIndex(index, Nothing, list, index2) Then
                mVersion += 1
                list(index2) = value
            Else
                Throw New ArgumentOutOfRangeException("index", index, "Parameter out of range")
            End If
        End Set
    End Property

    Public Sub Remove(ByVal value As Object) Implements System.Collections.IList.Remove
        Dim index1, index2 As Integer
        Dim list As ArrayList = Nothing
        If InternalSearch(value, index1, list, index2) >= 0 Then
            list.RemoveAt(index2)
            'TODO: More Merging with Next/Previous list when size is small
            If list.Count = 0 Then
                mLists.RemoveAt(index1)
            End If
            mVersion += 1
            mCount -= 1
        End If
    End Sub

    Public Sub RemoveAt(ByVal index As Integer) Implements System.Collections.IList.RemoveAt
        Dim index1, index2 As Integer
        Dim list As ArrayList = Nothing
        If InternalGetIndex(index, index1, list, index2) Then
            list.RemoveAt(index2)
            'TODO: More Merging with Next/Previous list when size is small
            If list.Count = 0 Then
                mLists.RemoveAt(index1)
            End If
            mVersion += 1
            mCount -= 1
        Else
            Throw New ArgumentOutOfRangeException("index", "ArgumentOutOfRange_Index")
        End If
    End Sub
End Class