TECHY360
Everything You Need To Know About Tech

Dynamic Array: Algorithms and data structures for beginners

0 5

Sometimes the collection is required unlimited capacity and ease of use of the list but at the same time constant access time to an arbitrary element, as in an array. In this case, an array-based list is used – a dynamic array (Array List).

Class ArrayList

ArrayListIs a collection that implements the interface IList<T>and uses an array to store the elements. Like a linked list, it ArrayListcan store an arbitrary number of elements (limited only by the amount of available memory), but otherwise behaves like an array.

The interface IList<T>provides all methods ICollection<T>and optionally methods for reading, inserting and deleting items by index. The code below is generated using the “Implement Interface” command in Visual Studio 2010 and, in addition to the automatically generated stubs for methods, also contains:

  • Array of T_items) to store items.
  • The default constructor that creates an empty list.
  • A constructor that takes an integer that creates a list with a given capacity. Note that the capacity of the list and its length are not the same. In practice, there may be a situation when such a constructor will allow the user to avoid a large number of extensions of the internal array.
public class ArrayList : System.Collections.Generic.IList
{
    T[] _items;

    public ArrayList()
        : this(0)
    {
    }

    public ArrayList(int length)
    {
        if (length < 0)
        {
            throw new ArgumentException("length");
        }

        _items = new T[length];
    }

    public int IndexOf(T item)
    {
        throw new NotImplementedException();
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        throw new NotImplementedException();
    }

    public T this[int index]
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            throw new NotImplementedException();
        }
    }

    public void Add(T item)
    {
        throw new NotImplementedException();
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool Contains(T item)
    {
        throw new NotImplementedException();
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public int Count
    {
        get { throw new NotImplementedException(); }
    }

    public bool IsReadOnly
    {
        get { throw new NotImplementedException(); }
    }

    public bool Remove(T item)
    {
        throw new NotImplementedException();
    }

    public System.Collections.Generic.IEnumerator GetEnumerator()
    {
        throw new NotImplementedException();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

Insert items

Inserting elements into a dynamic array is different from inserting into a linked list. There are two reasons for this. First: a dynamic array supports insertion into the middle of the array, whereas in a linked list you can insert only into the end or the beginning. Second, inserting an item into a linked list is always performed in constant time. Insertion into a dynamic array can take both O (1) and O (n) time.

Array expansion

As elements are added, the internal array may overflow. In this case, you must do the following:

  1. Create a larger array.
  2. Copy items to new array.
  3. Update the link to the internal list array so that it points to the new one.

Now it remains to answer the question of what size the new array should be. This is determined by the dynamic array growth strategy. We will consider two strategies and for both we will see how fast the array grows and how much its growth reduces productivity.

Doubled (approach Mono and Rotor)

There are two implementations ArrayListwhose code can be found on the network: Mono and Rotor. Both use a simple algorithm to increase the size of the array, doubling it if necessary. If the initial size of the array is zero, then the new one will contain 16 elements:

size = size == 0? 16: size * 2;

This algorithm makes less memory allocation, but spends more space than the Java option. In other words, it provides more frequent inserts in constant time at the cost of using more memory. The process of creating a new array and copying elements into it will be less frequent.

Slow growth (java approach)

Java uses a similar approach, but the array grows more slowly. The size of the new array is determined as follows:

size = (size * 3) / 2 + 1;

When using this algorithm, less memory is used.

Let’s look at the growth curves of arrays of up to 200,000 elements when using these two strategies:

Related Posts
1 of 6

As can be seen from the graph, in order to go over the border to 200,000 elements, the doubling of the array variant took 19 memory allocation and copying operations, while the Java variant required 30 operations.

Which strategy is better? There is no right and wrong answer to this question. When using doubling, we will have less insert operations for O (n), but more memory consumption. With slower growth, less memory will be used. In general, both options are valid. If your application has specific requirements, you may need to implement one or another expansion strategy. In any case, the external behavior of the dynamic array will not change.

Our implementation will double the increase (Mono / Rotor approach)

private void GrowArray()
{
    int newLength = _items.Length == 0 ? 16 : _items.Length << 1;

    T[] newArray = new T[newLength];

    _items.CopyTo(newArray, 0);

    _items = newArray;
}

Insert method

  • Behavior: Adds an item at the specified index. If the index is equal to or more than the number of elements, throws an exception.
  • Complexity: O (n).

Inserting at a specific index requires shifting all elements, starting from this index, one position to the right. If the internal array is full, insertion will require an increase in its size.

The following example gives an array with five positions, four of which are filled. The value “3” is inserted into the third position (with the index 2):

Array to shift elements
Array after shifting elements
Array after inserting an element to a free position
public void Insert(int index, T item)
{
    if (index >= Count)
    {
        throw new IndexOutOfRangeException();
    }

    if (_items.Length == this.Count)
    {
        this.GrowArray();
    }

    // Shift all the items following index one slot to the right.
    Array.Copy(_items, index, _items, index + 1, Count - index);

    _items[index] = item;

    Count++;
}

Add method

  • Behavior: Adds an item to the end of the list.
  • Difficulty: O (1) if more than one free space is left; O (n) if array expansion is required.
public void Add (T item)
{
    if (_items.Length == Count)
    {
        GrowArray ();
    }

    _items [Count ++] = item;
}

Deleting items

RemoveAt method

  • Behavior: deletes an item at a given index.
  • Complexity: O (n).

Deleting an item by an index is the opposite of insertion. The specified element is deleted, and the rest are shifted one position to the left.

Array before removing item
Array after deleting an item
Array after shifting elements
public void RemoveAt(int index)
{
    if (index >= Count)
    {
        throw new IndexOutOfRangeException();
    }

    int shiftStart = index + 1;
    if (shiftStart < Count)
    {
        // Shift all the items following index one slot to the left.
        Array.Copy(_items, shiftStart, _items, index, Count - shiftStart);
    }

    Count--;
}

Remove method

  • Behavior: deletes the first element whose value is equal to the one provided. Returns trueif the item has been deleted, or falseotherwise.
  • Complexity: O (n).
public bool Remove(T item)
{
    for (int i = 0; i < Count; i++)
    {
        if (_items[i].Equals(item))
        {
            RemoveAt(i);
            return true;
        }
    }

    return false;
}

Access to items

IndexOf method

  • Behavior: returns the index of the first element whose value is equal to the supplied one, or -1 if there is no such value.
  • Complexity: O (n).
public int IndexOf(T item)
{
    for (int i = 0; i < Count; i++)
    {
        if (_items[i].Equals(item))
        {
            return i;
        }
    }

    return -1;
}

Item method

  • Behavior: allows you to read or change the value of the index.
  • Difficulty: O (1).
public T this[int index]
{
    get
    {
        if(index < Count)
        {
            return _items[index];
        }

        throw new IndexOutOfRangeException();
    }
    set
    {
        if (index < Count)
        {
            _items[index] = value;
        }
        else
        {
            throw new IndexOutOfRangeException();
        }
    }
}

Contains method

  • Behavior: returns trueif the value is in the list, and falseotherwise.
  • Complexity: O (n).
public bool Contains (T item)
{
    return IndexOf (item)! = -1;
}

Bust

GetEnumerator method

  • Behavior: returns an iterator IEnumerator<T>to traverse all items in the list.
  • Complexity: Getting an iterator is O (1), traversing the list is O (n).

Note that we cannot simply walk through the array _items, since it contains not filled cells, so we limit the range over which we will be iterated by the number of elements.

public System.Collections.Generic.IEnumerator GetEnumerator()
{
    for (int i = 0; i < Count; i++)
    {
        yield return _items[i];
    }
}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Remaining IList <T> methods

Clear method

  • Behavior: removes all items from the list.
  • Difficulty: O (1).

There are two options for implementing the method Clear. In the first case, a new empty array is created, in the second, the field is just reset Count. In our implementation, a new zero-length array will be created.

public void Clear ()
{
    _items = new T [0];
    Count = 0;
}

CopyTo method

  • Behavior: copies all elements from the internal array to the specified one, starting from the specified index.
  • Complexity: O (n).

We do not use them CopyToarray method _items, because we want to copy only elements with indices from 0 to Count, and not the entire array. When used, Array.Copywe can specify the number of copied items.

public void CopyTo (T [] array, int arrayIndex)
{
    Array.Copy (_items, 0, array, arrayIndex, Count);
}

Count method

  • Behavior: returns the current number of items in the collection. If the list is empty, returns 0.
  • Difficulty: O (1).

Count– auto-increment field with private setter and public getter. The user can only read it, and the methods for adding and removing elements will change.

public int Count
{
    get;
    private set;
}

IsReadOnly method

  • Behavior: always returns false, since our collection is mutable.
  • Difficulty: O (1).
public bool IsReadOnly
{
    get {return false; }
}

To be continued

This concludes the analysis of dynamic arrays. Next time we go to the stacks and the queues.

Get real time updates directly on you device, subscribe now.

Comments
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More