List, Array or what else?

Question

I need a dynamic length data structure with the capability of changing the element values. The order of the elements is not important.

• If I use an array I can modify my elements, but I have problems with the length. The solution is to create a new array of the correct size and copy all the elements into the new one each time. Not a great idea because the number of elements changes often.

• It's better to use a generic list, but the modify process is really complicated: first of all I need to remove the element I want to change- the generic list doesn't seem to have a simple "Remove"/"Delete" method, so I tried the "Filter" one- then add the modified element to the head. It works but it's a bit too complicated for something so easy.

Is there a data structure that allows me to dynamically change the length and modify the elements such as a modifiable list or a dynamically-sized array?

Answer 1

Use ResizeArray. It's an abbreviation for the CLI type List(T) which offers the features you require, like Remove for example.

From MSDN Library:

The List(T) class is the generic equivalent of the ArrayList class. It implements the IList(T) generic interface using an array whose size is dynamically increased as required.

Methods such as Contains, IndexOf, LastIndexOf, and Remove use an equality comparer for the list elements. The default equality comparer for type T is determined as follows. If type T implements the IEquatable(T) generic interface, then the equality comparer is the Equals(T) method of that interface; otherwise, the default equality comparer is Object.Equals(Object).

Methods such as BinarySearch and Sort use an ordering comparer for the list elements. The default comparer for type T is determined as follows. If type T implements the IComparable(T) generic interface, then the default comparer is the CompareTo(T) method of that interface; otherwise, if type T implements the nongeneric IComparable interface, then the default comparer is the CompareTo(Object) method of that interface. If type T implements neither interface, then there is no default comparer, and a comparer or comparison delegate must be provided explicitly.

The List(T) is not guaranteed to be sorted. You must sort the List(T) before performing operations (such as BinarySearch) that require the List(T) to be sorted.

Elements in this collection can be accessed using an integer index. Indexes in this collection are zero-based.

List(T) accepts a null reference (Nothing in Visual Basic) as a valid value for reference types and allows duplicate elements.

An example in F#:

open System

// an integer list
let intList =
    let temp = new ResizeArray<int>() in
    temp.AddRange([| 1; 2; 3 |]);
    temp

// print each int using the ForEach member method
intList.ForEach( fun i -> Console.WriteLine(i) )

// unpack items from the resize array
let itemOne = intList.Item(0)
let itemTwo = intList.[1]

Answer 2

I would recommend to use ResizeArray. It is basically System.Collections.Generic.List<'T> which is perfect to use if number of elements changes frequently.

// Add items to a ResizeArray based on a condition
let filterRange predicate (i, j) =
    let results = ResizeArray(j-i+1) // reserve enough memory
    for k = i to j do
        if predicate k then results.Add(k)
    results

Regarding your second concern, you still can use the syntax arr.[idx] <- e as with Array.

To avoid complicated manipulation of ResizeArray, you could use high-order functions in ResizeArray module from F# PowerPack. These functions create new ResizeArrays so performance is not ideal.

// Use high-order functions to update items
let changeOneToThree (a: ResizeArray<_>) =
   ResizeArray.map (fun x -> if x = 1 then 3 else x) a

However, you can always start from there and optimize by mutating current ResizeArray.